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