20 баллов. Задача 3. Робот
Петя увлекается робототехникой. Сегодня он тренируется в написании программ для Робота в лабиринте. Он написал такую программу:
ПОКА сверху стена или снизу стена:
ПОКА сверху стена:
сдвинься на 1 шаг вправо
ПОКА снизу стена:
сдвинься на 1 шаг влево
Теперь его интересует такой вопрос: сколько клеток в данном лабиринте (см. рисунок) таковы, что начав в них движение Робот будет двигаться вечно и никогда не разобьется? (При этом он именно движется, то есть, клетки, из которых Робот не сделает ни одного шага, нас не интересуют.) Тонкая линия разделяет клетки; стена — толстая черная линия.
Normalized 24.02
В качестве ответа выведите одно целое число — искомое количество клеток.
Комментарий.
1. Робот занимает ровно одну клетку лабиринта и может за один шаг переместиться на одну клетку влево, вправо, вниз или вверх, при условии, что на его пути нет стены. Если он врежется в стену, то Робот разобьется.
2. Условие ПОКА соответствует циклу while в языках программирования.
При этом есть один внешний цикл ПОКА и два внутренних (если верно условие у внешнего цикла, то на этой его итерации выполняются оба внутренних).
3. В лабиринте
нет ни одной клетки, начав движение в которой, Робот будет двигаться вечно (стартовав из любой клетки, он в итоге врежется в стену).
Петя увлекается робототехникой. Сегодня он тренируется в написании программ для Робота в лабиринте. Он написал такую программу:
ПОКА сверху стена или снизу стена:
ПОКА сверху стена:
сдвинься на 1 шаг вправо
ПОКА снизу стена:
сдвинься на 1 шаг влево
Теперь его интересует такой вопрос: сколько клеток в данном лабиринте (см. рисунок) таковы, что начав в них движение Робот будет двигаться вечно и никогда не разобьется? (При этом он именно движется, то есть, клетки, из которых Робот не сделает ни одного шага, нас не интересуют.) Тонкая линия разделяет клетки; стена — толстая черная линия.
Normalized 24.02
В качестве ответа выведите одно целое число — искомое количество клеток.
Комментарий.
1. Робот занимает ровно одну клетку лабиринта и может за один шаг переместиться на одну клетку влево, вправо, вниз или вверх, при условии, что на его пути нет стены. Если он врежется в стену, то Робот разобьется.
2. Условие ПОКА соответствует циклу while в языках программирования.
При этом есть один внешний цикл ПОКА и два внутренних (если верно условие у внешнего цикла, то на этой его итерации выполняются оба внутренних).
3. В лабиринте
нет ни одной клетки, начав движение в которой, Робот будет двигаться вечно (стартовав из любой клетки, он в итоге врежется в стену).
Answers & Comments
Verified answer
Просто выполняем алгоритм для каждой из клеток.Например, 4 клетка в пятом ряду: у неё сверху стенка, поэтому она двигается вправо, оттуда опять вправо, оттуда еще раз вправо и врезается в стенку после 6-й клетки.
4 клетка в третьем ряду: у ней сверху нет стенки, снизу есть, поэтому робот движется влево. Затем снизу нет стенки, а сверху есть, поэтому робот возвращается обратно, и всё повторяется.
6 клетка во втором ряду: у неё ни сверху, ни снизу нет стенок, поэтому она стоит на месте.
Клетки, начав с которых, робот разбивается помечены персиковым цветом, в них указано, о какую стенку он разбивается. Клетки, начав с которых, робот делает конечное число шагов, отмечены бледно-оранжевым цветом, в них указано, в какой клетке остановится робот. Зелёные клетки удовлетворяют условию, их на рисунке 6.