Олимпиадная задача про ладью в шахматном лабиринте и алгоритмы, 9–11 класс
Задача
Назовём лабиринтом шахматную доску 8×8, на которой между некоторыми полями поставлены перегородки. По команде ВПРАВО ладья смещается на одно поле вправо или, если справа находится край доски или перегородка, остаётся на месте; аналогично выполняются команды ВЛЕВО, ВВЕРХ и ВНИЗ. Программист пишет программу – конечную последовательность указанных команд, и даёт её пользователю, после чего пользователь выбирает лабиринт и помещает в него ладью на любое поле. Верно ли, что программист может написать такую программу, что ладья обойдёт все доступные поля в лабиринте при любом выборе пользователя?
Решение
Занумеруем всевозможные начальные положения, то есть пары (лабиринт, положение ладьи) – их конечное число. Составим программу П1 обхода всех полей для первого начального положения. Предположим теперь, что начальным было положение №2. Применим программу П1 и, если ладья обошла не все поля, допишем в конце несколько команд, чтобы обойти оставшиеся поля. Получим программу П2. Применим программу П2 к ладье в 3-м начальном положении, снова допишем программу и т.д.
Ответ
Верно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь