14.3. Ещё пример задания

Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

вправо

вверх

влево

влево

вниз

вниз

вправо

вправо

вправо

вниз

влево

Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.

Решение (способ 1, моделирование движения Робота):

1. отметим, что в условии ничего не говорится о стенках, то есть, молчаливо предполагаем, что их нет

2. можно повторить все движения Робота на бумажке и посмотреть, куда он уйдет; на схеме исходная точка обозначена красной точкой, а конечная – синей, синяя линия показывает путь Робота:

3. поскольку Робот не может ходить по диагонали, для перехода из начальной точки в конечную кратчайшим путем ему нужно выполнить, например, такую программу (см. штриховые линии на рисунке):

   вниз вниз вправо

4. есть и другие варианты (попробуйте их найти!), но все они содержат 3 команды: одну команду вправо и две команды вниз

5. таким образом, ответ – 3.

Решение (способ 2, анализ программы):

1. можно решить задачу без повторения движений Робота

2. обратим внимание, что пары команд «вперед-назад» и «влево-вправо» дают нулевой эффект, то есть, не перемещают Робота, поэтому все такие пары можно выкинуть из программы

3. поскольку стенок нет, все равно где стоят парные команды в программе, вычеркиваем их:

в право

в верх

влево

влево

вниз

вниз

вправо

вправо

в право

вниз

влево

1. смотрим, какие команды остались (они отмечены желтым маркером), их всего 3

2. таким образом, ответ – 3.