Школа179: /Информатика//Информатика / Архив/2010//Информатика / Архив / 2010 / 7 Б/20091116
 

7Б «Робот». Задание №9: Рекурсия

Что умеет робот?

Алгоритм может вызывать сам себя!
Пример рекурсивного алгоритма, перемещающего робота вправо до стены:


Аналогичный алгоритм, перемещающий робота вправо до стены и закрашивающий клетку у стены:


Алгоритм, перемещающий робота вправо до стены, затем возвращающий его в исходную клетку:


Задание 09-А

Робот находится в горизонтальном коридоре. Напишите алгоритм «к стене вправо закрашивая путь», который перемещает робота до правого конца коридора, закрашивая все клетки на своем пути, включая начальную.
В этой задаче нельзя пользоваться конструкцией цикла нц...кц.
Решение задачи сохраните в файле ~/kumir/09/A.kum
Проверьте свой алгоритм на всех стартовых обстановках робота, находящихся в каталоге /home/pub/kumir/fields/09/A

Задание 09-B

Робот находится в горизонтальном коридоре. Напишите алгоритм «к стене вправо закрашивая путь затем вернуться», который перемещает робота до правого конца коридора, закрашивая все клетки на своем пути, включая начальную, затем возвращает в исходную клетку.
В этой задаче нельзя пользоваться конструкцией цикла нц...кц.
Решение задачи сохраните в файле ~/kumir/09/B.kum
Проверьте свой алгоритм на всех стартовых обстановках робота, находящихся в каталоге /home/pub/kumir/fields/09/B

Задание 09-С

Робот находится в горизонтальном коридоре. Справа от робота есть закрашенная клетка. Напишите алгоритм «вправо симметрично закрашенной клетке», который доводит робота до закрашенной клетки, затем перемещает вправо на такое же расстояние, то есть робот должен остановиться в клетке, симметричной начальной позиции относительно закрашенной клетки.
Решение задачи сохраните в файле ~/kumir/09/C.kum
Проверьте свой алгоритм на всех стартовых обстановках робота, находящихся в каталоге /home/pub/kumir/fields/09/C

Задание 09-D

Выполните задание 09-C при дополнительном условии, что робот должен закрасить все клетки, через которые он проходит.
Решение задачи сохраните в файле ~/kumir/09/D.kum
Проверьте свой алгоритм на всех стартовых обстановках робота, находящихся в каталоге /home/pub/kumir/fields/09/D

Задание 09-E

Выполните задание 09-C при дополнительном условии, что робот должен закрасить все клетки между своим первоначальным расположением и первоначально закрашенной клеткой.
Решение задачи сохраните в файле ~/kumir/09/E.kum
Проверьте свой алгоритм на всех стартовых обстановках робота, находящихся в каталоге /home/pub/kumir/fields/09/E

Задание 09-F

Выполните задание 09-C при дополнительном условии, что робот должен закрасить все клетки между первоначально закрашенной клеткой и своим конечным расположением.
Решение задачи сохраните в файле ~/kumir/09/F.kum
Проверьте свой алгоритм на всех стартовых обстановках робота, находящихся в каталоге /home/pub/kumir/fields/09/F

Задание 09-G

Робот находится в горизонтальном коридоре, где-то справа от робота есть стена. Переместите робота в такую клетку, чтобы расстояние от робота до правой стены было вдвое больше, чем первоначально.
Решение задачи сохраните в файле ~/kumir/09/G.kum
Проверьте свой алгоритм на всех стартовых обстановках робота, находящихся в каталоге /home/pub/kumir/fields/09/G

Задание 09-H

Робот находится в горизонтальном коридоре. Справа от робота есть закрашенная клетка. Робот должен дойти до закрашенной клетки, пройти ее, затем пройти вправо на расстояние, вдвое большее, чем первоначальное.
Решение задачи сохраните в файле ~/kumir/09/H.kum
Проверьте свой алгоритм на всех стартовых обстановках робота, находящихся в каталоге /home/pub/kumir/fields/09/H

Задание 09-I

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

Задание 09-J

Робот находится снизу от бесконечной стены, не обязательно в соседней со стеной клетке. Где-то слева от робота в стене есть проход. Робот должен обойти стену и оказаться в клетке, симметричной начальному положению относительно стены.

Задание 09-K

Робот находится снизу от бесконечной стены, не обязательно в соседней со стеной клетке. Напишите алгоритм, который передвигает робота по диагонали вправо-вверх до стены, затем робот «отражается» от стены и проходит такое же расстояние вправо-вниз. При этом робот должен закрасить все пройденные клетки.

Задание 09-L

Робот находится в левом конце горизонтального коридора. Коридор состоит из нечетного числа клеток. Переведите робота в среднюю клетку коридора.

Задание 09-M

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

Задание 09-N

Робот находится в горизонтальном коридоре, ограниченном с двух сторон. Переместите робота в клетку, симметричную относительно середины коридора.
В этой задаче можно пользоваться циклом.

Задание 09-O

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

Задание 09-P

Робот находится в горизонтальном коридоре, где-то справа от робота есть стена. Переместите робота к стене, закрасив все клетки до стены через одну. Клетка, где первоначально находился робот, должна быть закрашена.
В этой задаче нельзя пользоваться конструкцией цикла нц...кц.

Задание 09-Q

Робот находится в горизонтальном коридоре, где-то справа от робота есть стена. Робот должен закрасить клетки между своим начальным положением и правым концом коридора в шахматном порядке и вернуться в исходную клетку. Самый правый конец коридора должен быть закрашенной клеткой.

Задание 09-R

Робот находится в левом нижнем углу прямоугольного поля. В одной из клеток поля есть клад (закрашенная клетка). Переместите робота в клетку с кладом.
В этой задаче нельзя пользоваться конструкцией цикла нц...кц.

Задание 09-S

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

Задание 09-T

На бесконечном поле имеется бесконечная горизонтальная стена. Робот находится ниже стены в соседней со стеной клетке. Где-то в стене есть проход. Робот должен найти проход и остановиться в клетке над проходом (как в задаче 08-D).

В этой задаче поле и стена предполагаются бесконечными, поэтому решения, использующие внешние стенки поля (например, нц пока слева свободно ... кц), а также решения, содержащие циклы, выполняющиеся фиксированное количество раз (например, нц 1000 раз ... кц) приниматься не будут.

Клетка, в которой находится робот первоначально – закрашена. Закрашивать другие клетки робот не может.

Задание 09-U

Робот находится внутри прямоугольного поля. Робот начинает движение вправо-вверх, отражаясь от всех сторон прямоугольника, подобно биллиардному шару и закрашивая все пройденные клетки. Робот завершает движение, придя в угол или в ранее закрашенную клетку.
В этой задаче нельзя пользоваться конструкцией цикла нц...кц.

Задание 09-V

Робот находится внутри лабиринта, при этом роботу доступно только ограниченное количество клеток. Закрасьте все клетки, доступные роботу.