Робот 2

Игра в Робота

(Часть II)

Рекурсией называется ситуация, когда процедура прямо или косвенно, обращается к самой себе. То есть когда имеется цепочка вызовов P1 --> P2 --> ... --> Pn --> P1.


Внимание! Каждая из задач 1 — 3 разбивается на три подзадачи (a), (b), ©. В пунктах (a) нужно написать программы, использующие рекурсию и не использующих проверки закрашено, в пункте (b) использующие проверку закрашено, и не использующих рекурсии; в пункте © доказать невозможность, построить программы без использования рекурсии или проверки закрашено (т. е. невозможно решить эти задачи так, как в I-м листочке.)


Задачи


0.

Дано: Робот находится в бесконечном в одну сторону (ограниченного слева и неограниченного справа) коридоре высотой в одну клетку, ни одна из клеток которого не закрашена.
Надо: Робот находится в исходной клетке, начальная клетка коридора закрашена.
Примечание: Использовать проверку закрашено запрещено!

1.

Дано: Робот находится на расстоянии n от начала бесконечного в одну сторону (ограниченного слева и неограниченного справа) коридора высотой в одну клетку, ни одна из клеток которого не закрашена.
Надо: Робот находится на расстоянии 2n от начала коридора.

2.

Дано: Робот находится в коридоре шириной в 1 клетку, ни одна из клеток которого не закрашена.
Надо: Робот находится в клетке, симметричной исходной.

3.

Дано: На бесконечном поле ни одна из клеток которого не закрашена, есть одна горизонтальная стена неизвестной ширины, Робот стоит у нее снизу.
Надо: Надо: Робот оказался на одну клетку севернее исходного положения (обойдя стену).

4.

Доказать, что любой цикл в программе можно заменить на рекурсивную функцию, не содержащую циклов.

5.

Дано: Робот находится в лабиринте ни одной клетки которого не закрашено; на поле расставлены стены, так, что число доступных для Робота клеток конечно.
Надо: Закрасить все доступные клетки.