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