Игра в Робота
(Часть II)
Рекурсией называется ситуация, когда процедура прямо или косвенно, обращается к самой себе. То есть когда имеется цепочка вызовов P1 -> P2 -> ... -> Pn -> P1.
В пунктах а) задач 1 — 3 нужно написать программы, использующие рекурсию и не использующих проверки закрашено, в пункте б) использующие проверку закрашено и не использующих рекурсии в пункте б) доказать невозможность построить программы без использования как рекурсии так и проверки закрашено)
|
Задачи
1. Дано: Робот находится в n-ой клетке бесконечного в одну сторону (ограниченного слева и неограниченного справа) коридора высотой в одну клетку.
Надо: Робот находится в 2n-ой клетке.
2. Дано: Робот находится в коридоре шириной в 1 клетку.
Надо: Робот находится в клетке, симметричной исходной.
3. Дано: на бесконечном поле есть одна горизонтальная стена неизвестной
ширины, Робот стоит у нее снизу.
Надо: Робот оказался на одну клетку севернее исходного положения
(обойдя стену).
4. Доказать, что любую программу, не содержащую рекурсии, можно заменить
эквивалентной программой с рекурсией, не содержащей циклов.
5. Дано: Робот находится в лабиринте; на поле расставлены стены, так что
число доступных для Робота клеток конечно. Вначале ни одной клетки не
закрашено.
Надо: закрасить все доступные клетки.