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