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

Задача с сайта e-olimp №2820Перемещение коня

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

Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

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

Входные данные

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква (ah), задающая столбец и второй – цифра (18), задающая строку на шахматной доске.

Выходные данные

Для каждого теста вывести одну строку следующего содержания: «To get from xx to yy takes n knight moves.» (см. пример выходных данных).

Тесты:

Пример входных данных Пример выходных данных
e2 e4 To get from e2 to e4 takes knight 2 moves.
a1 b2 To get from a1 to b2 takes knight 4 moves.
b2 c3 To get from b2 to c3 takes knight 2 moves.
a1 h8 To get from a1 to h8 takes knight 6 moves.
a1 h7 To get from a1 to h7 takes knight 5 moves.
h8 a1 To get from h8 to a1 takes knight 6 moves.
b1 c3 To get from b1 to c3 takes knight 1 moves.
f6 f6 To get from f6 to f6 takes knight 0 moves.

Код программы:

Данную задачу можно решить с помощью алгоритма поиска в ширину. Из начальной клетки мы ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения (если новое значение меньше того, что записано в клетке — записываем его, а если больше — оставляем предыдущее). Длина в начальной клетке — 0, а длина в каждой последующей — 1.

Ссылка на засчитанное решение и код решения на ideone.

А700в

Задача. Дана квадратная матрица А порядка n. Получить матрицу AB; элементы матрицы B вычисляются по формуле:

[latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex]

 

[latex](i,j=1,\cdots, n)[/latex]

 

Тесты:

Размер матрицы Входные данные Результат Комментарий
n=2 [latex]\begin{pmatrix}1&7\\3&2\end{pmatrix}[/latex] [latex]\begin{pmatrix}-3,5&0,5\\-1&1,5\end{pmatrix}[/latex] Пройден
n=3 [latex]\begin{pmatrix}1&2&3\\7&6&5\\4&8&9\end{pmatrix}[/latex] [latex]\begin{pmatrix}-2&-0,25&0,83333\\-4,66667&2,25&3,83333\\-7&-0,25&3,333\end{pmatrix}[/latex] Пройден

Код программы:

После ввода матрицы A, мы должны найти элементы матрицы B. Из условия задачи:  [latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex] , при [latex](i,j=1,\cdots, n)[/latex].

Для нахождения [latex]b_{ij}[/latex] используется условный оператор if в цикле for. Матрица C — результат умножения матрицы A на матрицу B, которое также производим в цикле for.

Код программы можно посмотреть здесь.

Решение на Java:

Ссылка на решение.

Ю3.35

Задача. [latex]\arctan(x)=x-\frac{x^{3}}{3}+\frac{x^{5}}{5}-\cdots (-1)^{n}\frac{x^{2n+1}}{2n+1}+\cdots[/latex]

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

Тесты:

x [latex]\varepsilon[/latex] left right n Разность Комментарий
1 0.3 0,785398 1 0 0,214602 Пройден
0.6 0.02 0.54042 0.528 1 0.0124195 Пройден
0.7 0.0002 0.610726 0.610631 7 9.52374е-05 Пройден
0.7 0.000002 0.610726 0.610728 12 1.67214е-06 Пройден
0.7 0.00000000001 0.610726 0.610726 28 8.34648е-12 Пройден

Код программы:

 

В начале мы подставляем аргумент x в левую часть равенства и подсчитываем ее. Затем проверяем разность между правой частью и левой, если ее модуль меньше заданного [latex]\varepsilon[/latex], то выводим результат, а если нет, то в цикле while мы считаем последовательность до тех пор пока их разность не будет меньше [latex]\varepsilon[/latex]. Последовательность задается в цикле рекурентно, поэтому т.к. первый член последовательности будет равен x, то заведем переменную s, равную xкоторая будет определять чему равен числитель дроби, домножая предыдущий на [latex](-1)x^{2}[/latex] . После этого программа выводит значение левой и правой части, их разницу и количество итераций для заданной погрешности.

Код можно проверить здесь.

Решение на Java:

Ссылка на решение.

А396

Задача. Дана действительная квадратная матрица порядка n. Построить последовательность действительных чисел [latex]a_{1}\cdots a_{n}[/latex] по правилу: если в i-й строке матрицы элемент, принадлежащий главной диагонали, отрицателен, то [latex]a_{i}[/latex] равно сумме элементов i-й строки, предшествующих первому отрицательному элементу, в противном случае [latex]a_{i}[/latex] равно сумме последних элементов i-й строки, начиная с первого по порядку неотрицательного элемента.

Тесты:

Данная матрица Последовательность Комментарий
[latex]\begin{Vmatrix}1 & 2 & -3 & 4\\ 3 & 5 & 6 & 7\\ 1 & 3 & 0 & 6\\ -5 & 7 & 2 & -9\end{Vmatrix}[/latex] 4 21 10 0 Пройден
[latex]\begin{Vmatrix}1 & -2 & 3\\ -7 & -3 & 0\\ 5 & 5 & 2 \end{Vmatrix}[/latex] 2 0 12 Пройден
[latex]\begin{Vmatrix}7 & 7 & 9 & 3\\ 0 & 5 & 0 & 7\\ 4 & 7 & -7 & 2\\ 1 & -4 & 8 & -3\end{Vmatrix}[/latex] 26 12 11 1 Пройден

Код программы:

Для начала мы должны обнулить матрицу [latex]b_{1}\cdots b_{n}[/latex], элементы которой являются суммами элементов i-х строк входной матрицы, которую мы также задаем. А далее, с помощью циклов  for , можно оценить диагональные элементы заданной матрицы. И следуя условию, если они отрицательные, то в [latex]b_{i}[/latex] мы просуммируем все элементы данной строки, если они положительные, до первого отрицательного в строчке, а если они положительные, то [latex]b_{i}[/latex] будет равно сумме последних элементов строки (т.е. после диагонального) начиная с первого по порядку неотрицательного элемента. И в конце выводим конечную последовательность [latex]b_{1}\cdots b_{n}[/latex].

Код можно проверить здесь.

Решение на Java:

Код на Java.

Ю11.3

Задача. Метод Эйткена-Стеффенсона (развитие метода простой итерации). Найти решение уравнения [latex]x=\varphi(x)[/latex] методом Эйткена-Стеффенсона, в котором от заданного начального [latex]x_{0}[/latex] три очередных приближения находятся по формулам: [latex]x_{n+1}=\varphi (x_{n})[/latex]; [latex]x_{n+2}=\varphi (x_{n+1})[/latex]; [latex]x_{n+3}=\frac{x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}[/latex]. Процесс продолжается до достижения одного из условий: [latex]\left | x_{n+3}-x_{n+2} \right |<\varepsilon[/latex] или [latex]x_{n}-2x_{n+1}+x_{n+2}=0[/latex].

Решение. В начале мы задаем начальное приближение  [latex]x=x_{0}[/latex] и [latex]\varepsilon[/latex]. Нам понадобится цикл с постусловием. Далее вычисляем первое приближение [latex]x_{1}=\varphi (x_{0})[/latex] и второе приближение [latex]x_{2}=\varphi (x_{1})[/latex]. Находим по формуле [latex]x=\frac{x_{0}x_{2}-x_{1}^{2}}{x_{0}-2x_{1}+x_{2}}[/latex]. Далее мы проверяем выполнение условия выхода из цикла: если [latex]\left | x-x_{0} \right |>\varepsilon[/latex] (нужно проверять разность [latex]\left | x-x_{0} \right |>\varepsilon[/latex], а не [latex]\left | x-x_{2} \right |>\varepsilon[/latex]) и [latex]x_{0}-2x_{1}+x_{2}\neq 0[/latex] тогда цикл продолжается, но если хотя бы одно из условий выполнено, то мы получаем, что [latex]x[/latex] — решение уравнения [latex]x=\varphi(x)[/latex].

Данная программа написана для функции [latex]9.2x^{3}+3.3x^{2}+4x-1[/latex].

Тесты:

x [latex]\varepsilon[/latex] Корень уравнения Комментарий
2 0.005 1.99889 Пройден
1 0.00002 0.233905 Пройден
-4 0.0005 -3.99981 Пройден

Код программы:

Код программы можно проверить здесь.

Решение на Java:

Ссылка на решение.

А98

Задача. Пусть [latex]a_{1}=b_{1}=1; a_{k}=3b_{k-1}+2a_{k-1}; b_{k}=2a_{k-1}+b_{k-1}[/latex], [latex]k=\overline{2, \infty }[/latex]. Дано натуральное [latex]n[/latex]. Найти [latex]\sum_{i=1}^{n}\frac{2^{k}}{(1+a_{k}^{2}+b_{k}^{2})k!}[/latex].

Тесты:

n [latex]\sum_{i=1}^{n}\frac{2^{k}}{(1+a_{k}^{2}+b_{k}^{2})k!}[/latex] Комментарий
2

0.0596538

Пройден
4

0.0597339

Пройден
20 0.059734 Пройден

Код:

Для решения данной задачи понадобилось ввести переменную [latex]n[/latex], которая показывает какое количество раз нужно повторить операцию сложения. В цикле for вычисляется сумма, по заданной формуле. Далее последовательность можно задать рекурентно: чтобы каждый раз не считать [latex]\frac{2^{k}}{k!}[/latex], мы заводим переменную u, равную изначально двум, потому что k начинается с 2, и u каждый раз мы будем домножать на [latex]\frac{2}{k}[/latex]. Далее остается лишь посчитать a и b (переменная [latex]as[/latex] запоминает переменную [latex]a[/latex] для последующего вычисления переменной [latex]b[/latex]) и поставить в формулу. Для проверки выполнения программы можно воспользоваться ссылкой.

Решение на Java:

Ссылка на решение.