e-olymp 2820. Перемещение коня

Условие

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче. Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток [latex]a[/latex] и [latex]b[/latex] в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из [latex]a[/latex] в [latex]b[/latex].

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]\text{a}[/latex]–[latex]\text{h}[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]–[latex]8[/latex]), задающая строку на шахматной доске.

Для каждого теста вывести одну строку следующего содержания: «To get from [latex]\text{xx}[/latex] to [latex]\text{yy}[/latex] takes [latex]n[/latex] knight moves.»

Тестирование

Входные данные Выходные данные
1 1 -1
2 0.25 -0.75
3 0.1 -0.861111
4 0.01 -0.827962
5 0.0000001 -0.822467

Код

Решение

Вычисление суммы ряда с точностью [latex]\varepsilon[/latex] представляет собой процесс нахождения членов ряда и их суммирования до тех пор, пока значение очередного члена по модулю не окажется меньше указанной точности.

Прежде всего найдем зависимость [latex]a_{n+1}[/latex] от [latex]a_n[/latex] и выведем рекуррентную формулу для очередного члена:

[latex]a_{n+1} = a_n \cdot \frac {a_{n+1}}{a_n} = a_n \cdot \frac {\frac {(-1)^{i+1}}{(i+1)^2}}{\frac {(-1)^i}{i^2}} = a_n \cdot -(\frac {i}{i+1})^2[/latex]

Для вычислений мы используем рекуррентное соотношение, поэтому до выполнения цикла, накапливающего сумму, переменным члена ряда a и суммы sum потребуется присвоить значение [latex]a_1 = \frac {(-1)^1}{1^2} = -1[/latex]:

Теперь опишем, каким образом будет работать цикл:

  • Цикл будет начинаться со счетчиком [latex]i = 1[/latex], который будет инкрементироваться в конце каждой итерации.
  • Цикл будет выполняться до тех пор, пока абсолютное значение очередного члена ряда [latex]a_i[/latex] будет не меньше, чем заданная точность [latex]\varepsilon[/latex].
  • В каждой итерации цикла значение суммы будет увеличиваться на [latex]a_i[/latex].

Реализуем описанный алгоритм с помощью цикла for. Чтобы сократить количество операций в теле цикла до одной, вычислять очередной член ряда будем при проверке выполнения условия продолжения. При присвоении переменной a нового значения воспользуемся кастингом (double) ; в противном случае уже второй член ряда будет обнуляться из-за умножения на дробь с целой частью [latex]0[/latex]:

Наконец, выведем требуемое значение — сумму ряда:

Ссылки

Условие задачи на E-Olymp;

Код программы на Ideone.com;

Подтверждение решения на E-Olymp.

Молоканов Юрий
Молоканов Юрий

Latest posts by Молоканов Юрий (see all)

Добавить комментарий