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