Задача
Лабиринтом называется клетчатый квадрат 10*10, некоторые пары соседних узлов в котором соединены отрезком - "стеной" таким образом, что переходя из клетки в соседнюю по стороне клетку и не проходя через стены, можно посетить все клетки квадрата. Границу квадрата будем также считать обнесенной стеной. В некоторой клетке некоторого лабиринта стоит робот. Он понимает 4 команды - Л, П, В, Н, по которым соответственно идет влево, вправо, вверх и вниз, а если перед ним "стена", то стоит на месте. Как написать программу для робота, выполняя которую он обойдет все клетки независимо от лабиринта и от своего начального положения?
Решение
Рассмотрим все начальные состояния. Каждое состояние определяется лабиринтом и начальным положением робота в этом лабиринте. Тем самым, состояний всего конечное число. Занумеруем состояния числами 1,2,...,N. Нетрудно написать программу П1обхода лабиринта исходя из начального состояния с номером 1. Далее, посмотрим, как двигался робот под действием программы П1исходя из начального состояния номер 2. Припишем к программе П1в конце несколько команд так, чтобы робот закончил обход лабиринта из начального состояния номер 2. Получим программу П2, выполняя которую, робот обходит лабиринт как из начального состояния номер 1, так и из начального состояния номер 2. Далее действуем таким же образом - приписываем к уже написанной программе Пk(выполняя которую робот обходит лабиринт из первых k начальных состояний), несколько команд так, чтобы робот обходил лабиринт и из (k+1)-го начального состояния. Полученная в конце программа ПN, как нетрудно видеть, будет искомой.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь