Задача по информатике (Робот и закрашивание клеток)
Условие: Сколько клеток закрасит Робот, выполнив такой алгоритм:
Алгоритм:
нц пока справа свободно вверх вправо закрасить вниз кц
Стартовая позиция Робота: На рисунке обозначена буквой P.
Рисунок поля:
+---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+ | P | | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+
На рисунке видно, что справа от поля есть стена, а сверху и снизу поле ограничено невидимыми стенами (краями поля). Робот начинает в клетке P, которая находится во втором ряду сверху, в первом столбце.
Решение:
Давайте пошагово проследим за действиями Робота. Робот начинает в клетке P.
Цикл нц пока справа свободно будет выполняться до тех пор, пока справа от Робота не окажется стена.
Начальная позиция: Робот в клетке P (обозначим её как (1,2) – столбец 1, строка 2, если считать с верхнего левого угла).
Шаг 1:
- Условие:
справа свободно? Да, справа от P нет стены. Цикл начинается. - Действие 1:
вверх. Робот перемещается из (1,2) в (1,1). - Действие 2:
вправо. Робот перемещается из (1,1) в (2,1). - Действие 3:
закрасить. Робот закрашивает текущую клетку (2,1). (1-я закрашенная клетка) - Действие 4:
вниз. Робот перемещается из (2,1) в (2,2).
Робот теперь находится в клетке (2,2).
Шаг 2:
- Условие:
справа свободно? Да, справа от (2,2) нет стены. Цикл продолжается. - Действие 1:
вверх. Робот перемещается из (2,2) в (2,1). - Действие 2:
вправо. Робот перемещается из (2,1) в (3,1). - Действие 3:
закрасить. Робот закрашивает текущую клетку (3,1). (2-я закрашенная клетка) - Действие 4:
вниз. Робот перемещается из (3,1) в (3,2).
Робот теперь находится в клетке (3,2).
Этот процесс будет повторяться. Робот будет двигаться по диагонали вверх-вправо, закрашивать клетку, а затем возвращаться на одну клетку вниз, чтобы его "базовая" позиция (от которой проверяется условие "справа свободно") всегда оставалась во втором ряду.
Давайте посчитаем, сколько раз Робот сможет выполнить цикл. Начальная позиция P находится в первом столбце. Поле имеет 8 столбцов. Стена находится после 8-го столбца.
- Когда Робот находится в столбце 1 (P), справа свободно. Он закрашивает клетку в столбце 2.
- Когда Робот находится в столбце 2, справа свободно. Он закрашивает клетку в столбце 3.
- ...
- Когда Робот находится в столбце 7, справа свободно. Он закрашивает клетку в столбце 8.
После того как Робот закрасит клетку в столбце 8 (это будет клетка (8,1)) и вернется в (8,2), он снова проверит условие.
Последний шаг цикла:
- Робот находится в клетке (8,2).
- Условие:
справа свободно? Нет, справа от (8,2) находится стена (край поля).
Цикл завершается.
Сколько раз Робот заходил в цикл и закрашивал клетку?
- Начиная из столбца 1, он закрасил клетку в столбце 2.
- Начиная из столбца 2, он закрасил клетку в столбце 3.
- ...
- Начиная из столбца 7, он закрасил клетку в столбце 8.
Таким образом, Робот закрасил клетки в столбцах 2, 3, 4, 5, 6, 7, 8. Всего 7 клеток.
Визуализация пути Робота и закрашенных клеток (З):
+---+---+---+---+---+---+---+---+ | | З | З | З | З | З | З | З | +---+---+---+---+---+---+---+---+ | P | R | R | R | R | R | R | R | +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+
Где R – это позиция Робота после выполнения всех действий внутри цикла, перед следующей проверкой условия.
Ответ:
Робот закрасит 7 клеток.