Исполнитель Робот ходит по клеткам бесконечной вертикальной
клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:
влево вверх вверх влево вниз вправо вправо вправо
Укажите наименьшее возможное число команд в программе,
которая вернет Робота в начальную точку.
Ответы
Ответ:
2 команды
Нужны две команды: влево вниз (в любом порядке их расположения)
Объяснение:
Берём исходную программу:
влево вверх вверх влево вниз вправо вправо вправо
Сначала в исходной программе сокращаете (зачёркиваете) все пары взаимно противоположных команд (влево-вправо и вверх-вниз):
влево вверх вверх влево вниз вправо вправо вправо
влево вверх вверх влево вниз вправо вправо вправо
влево вверх вверх влево вниз вправо вправо вправо
В результате останутся только непарные команды, которые представляют из себя минимальную программу, дающую перемещение в ту же конечную точку, что и исходная программа:
вверх вправо
Чтобы из конечной точки теперь переместиться в начальную, нужно выполнить ту же минимальную программу, заменив в ней каждую команду движения на противоположную ей (т.е. на движение в противоположную сторону). Получим вот что:
вниз влево
Это и есть минимальная программа, которая вернёт робота в начальную точку. Её длина- две команды.