Шахматный конь находится в левом верхнем углу

Задача 1. Шахматному коню разрешено перемещаться только одним из четырех способов: на две клетки вправо и на клетку вверх, на две клетки влево и на клетку вверх, на две клетки вверх и на клетку вправо, на две клетки вверх и на клетку влево. Конь находится в левом нижнем углу доски 8*8. Сколькими различными способами он может переместиться на верхнюю горизонталь? Ответ обоснуйте.

задан 30 Окт ’13 22:32

1 ответ

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

Далее заполняем вторую горизонталь, следя за тем, из каких клеток мы можем добраться в заполняемую клетку, и сколькими способами. Числа на второй горизонтали получаются такие: 0, 0, 1, 0, . 0. Только третье из чисел равно 1, так как на вторую горизонталь мы можем добраться только одним способом, и только в эту клетку.

Заполняем следующую, третью (снизу) горизонталь. На ней возникают три единицы: на первом, втором и пятом месте слева. Остальные числа равны нулю.

Дальнейший принцип заполнения должен быть понятен: для каждой очередной клетки просматриваем все клетки двух предыдущих горизонталей, с которых на неё мог попасть конь одним ходом. Таких клеток может быть максимум четыре. Все они уже заполнены числами, которые надо просуммировать, вписав итог в просматриваемую клетку. Это будет в точности число способов, сколькими можно в данную клетку добраться из начальной позиции коня.

Читайте также:  1С запрос отбор по типу регистратора

После того, как вся таблица окажется заполнена, надо найти сумму всех чисел в клетках верхней горизонтали. У меня получилось 205, что желательно перепроверить.

Примечание:
шахматный конь своим ходом передвигается на 2 клетки вперед и одну клетку в
сторону, образуя букву «Г».

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.

В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 15).

В выходной файл выведите единственное число количество способов добраться конём до правого нижнего угла доски.

Оцените статью
Добавить комментарий

Adblock detector