Текст задания звучит следующим образом. Жирным шрифтом выделены ключевые моменты:
На бесконечном поле имеется лестница. Сначала лестница спускается вниз справа налево, затем спускается вниз слева направо. Высота каждой ступени — одна клетка, ширина — две клетки. Робот находится справа от верхней ступени лестницы. Количество ступенек, ведущих влево, и количество ступенек, ведущих вправо, неизвестно. На рисунке указан один из возможных способов расположения лестницы и Робота (Робот обозначен буквой «Р»).
Напишите для Робота алгоритм, закрашивающий все клетки, расположенные непосредственно над ступенями лестницы, спускающейся слева направо. Требуется закрасить только клетки, удовлетворяющие данному условию. Например, для приведённого выше рисунка Робот должен закрасить следующие клетки (см. рисунок).
Конечное расположение Робота может быть произвольным. Алгоритм должен решать задачу для произвольного размера поля и любого допустимого расположения стен внутри прямоугольного поля. При исполнении алгоритма Робот не должен разрушиться, выполнение алгоритма должно завершиться. Алгоритм может быть выполнен в среде формального исполнителя или записан в текстовом редакторе. Сохраните алгоритм в текстовом файле.
Источник: inf-oge.sdamgia.ru
⠀
Данная задача интересна тем, что её программирование зависит от правильности определения повторяющихся отрезков пути и их кодирования.
Итак, задача из примера. Её можно разбить на две подзадачи:
⠀
1) спуск робота по лестнице вниз влево без закрашивания лестницы
2) спуск робота по лестнице вниз вправо с закрашиванием лестниц
Приступим к рассмотрению первой подзадачи более детально.
Подзадача 1 : спуск робота по лестнице вниз влево без закрашивания лестницы
Ключевой момент задачи - это выделение повторяющихся отрезков пути.
При выделении отрезов нужно помнить, что удачной разбивкой считается та, в которой удалось пройти весь путь используя одну повторяющуюся структуру.
Нашу первую подзадачу можно представить в виде отрезков следующим образом:
Окей, разбили. Но как робот поймет, что нужно остановиться?
Если внимательно посмотреть на рисунок сверху, можно увидеть, что в конце оранжевого и желтого участков не было преграды (стены), а вот в конец розового участка стена появляется (эта стена является началом второй лестницы, которая ведет вниз). Это и будет нашим условием цикла: робот будет двигаться по отрезкам “ пока снизу свободно” . Сами же отрезки кодируются с помощью последовательности команд вниз и влево.
код для первой подзадачи представлен ниже:
нц пока снизу свободно
вниз
влево
влево
кц
Отлично, вниз спустились, а значит с первой подзадачей мы справились. Осталось разобраться со второй.
Подзадача 2 : спуск робота по лестнице вниз вправо с закрашиванием лестницы
Скажу сразу. Для кодирования второй подзадачи будем действовать аналогично:
1) выделим повторяющиеся участки пути
2) определимся с условием окончания цикла
3) пропишем код внутри цикла
Приступим. Наш робот поменял позицию и теперь находится в середине пути.
Отрезки получились очень похожими на отрезки из первой подзадачи, вот только они немного перевернуты)))
Как робот поймёт, что нужно остановиться? А вот тут задача противоположная первой: если в первой подзадаче в конце каждого отрезка пути, кроме последнего, стены не было, то здесь стена присутствует в конце каждого отрезка пути, кроме последнего. Поэтому воспользуемся отрицанием нашего условия из первой подзадачи: робот будет двигаться по отрезкам “ пока снизу не свободно” . Тело цикла закодируем с помощью последовательности команд вниз, вправо и команды закрасить.
⠀
код для второй подзадачи представлен ниже:
нц пока снизу не свободно
закрасить
вправо
закрасить
вправо
вниз
кц
Заключение:
Объединив код обеих подзадач получим программу следующего вида:
Описанный алгоритм благодаря циклам получился универсальным, он будет работать на лестнице любой длины.
Спасибо за внимание!
Удачи на экзаменах!