Выполнение действий, как на спуске, так и на возврате

Задача. Вывести на печать введенные символы (например, введенной посимвольно строки 'HELLO') в обратном направлении.

Program Reverse_String;

Procedure Reverse;

Var ch: char;

Begin

If not eoln then

Begin

Read (ch);

Reverse;

Write(ch);

End;

End;

Begin

Reverse;

End.

Ханойские башни

В конце 19-го столетия в Европе появилась игра под названием "Ханойская башня".

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

Предметами игры служили медная платформа с укрепленными на ней тремя алмазными иглами с насажанными на них шестьюдесятью четырьмя золотыми дисками (рис. _).

В современных магазинах эта игра распространяется в комплекте из восьми картонных колец, насажанных на трех деревянных стержнях.

Цель игры состоит в переносе башни из колец с одного стержня на другой. Причем за один раз можно переносить только одно кольцо, и запрещается помещать большее кольцо над меньшим.

Предположим, что иглы пронумерованы (I, II, III) и монахам надо перенести 64 кольца с иглы I на иглу III. обозначим поставленную задачу следующим образом:

Перенести башню (64,I,III) или сокращенно ПБ(64,I,III)

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

К простому решению приводит догадка о том, что основное внимание нужно обратить на нижний диск иглы I, а не на верхний. То есть, если мы сможем снять с иглы I все кольца, кроме самого нижнего, то перенесем его на иглу III.

Приходим к задаче:

Перенести башню (63, 1, 2)

Перенести диск с иглы 1 на иглу 3

Перенести башню (63, 2, 3)

Это маленький, но значительный шаг к решению (маленький, так как все еще надо дважды переносить по 63 диска). Значит, так как мы можем повторить подобный анализ столько раз, сколько будет необходимо.

Например, задача "Перенести башню (63, I ,II)" может быть выражено как:

Перенести башню (62, I, III)

Перенести диск с иглы I на иглу II (или ПД(I, II))

Перенести башню (62, III, II)

Представим последовательность действий в виде схемы:

						ПБ(61, I,II)	→	…
				ПБ(62, I,III)	→	ПД(I,III)
						ПБ(61,II,III)
		ПБ(63, I,II)	→	ПД(I,II)
				ПБ(62, III,II)	→	…
ПБ(64,I,III)	→	ПД(I,III)
				ПБ(62,II,I)	→	…
		ПБ(63, II,III)	→	ПД(II,III)
				ПБ(62, I,II)	→	…

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

Перенести башню (n, a, b, c)

Это означает, что необходимо перенести n дисков с начальной иглы a на конечную иглу b, используя иглу c для временной башни.

Задача перенести башню (n, a, b, c) может быть решена за три шага:

Перенести башню (n-1, a, c, b)

Перенести диск с иглы a на иглу b

Перенести башню (n-1, c, b, a)

Этот алгоритм не имеет смысла для случая n<=1, поэтому добавляем правило:

Ничего не делать, если n<=1.

Представим схематично (выполняем до n ≤ 1):

		ПБ (n-1, a, c, b)
ПБ(n, a, b, c)	→	ПД (a, b)
		ПБ (n-1, c, b, a)

Напишем программу, использующую рекурсивную процедуру, выполняющую эти действия.

Program Hanoy_Tower;

Var Kol_diskov: Integer;

Procedure move_tower (h, s, na, rab: integer);

{h — высота башни, s — номер иглы, с которой нужно снять башню, na — номер иглы, на которую нужно ее перенести, rab — игла, используемая в качестве рабочей}

begin

if h>0 then

begin

move_tower (h-1, s, rab, na);

move_disk (s,na);

move_tower (h-1, rab, na, s);

end;

end;

procedure move_disk (take, place: integer);

{ take — номер иглы, с которой нужно взять диск, place — номер иглы, на которую нужно положить диск}

begin

writeln (take, '->', place);

end;

Begin

write ('Введите число дисков:');

readln (kol_diskov);

move_tower (kol_diskov, 1, 3, 2);

End.

Рассмотрим выполнение программы при задании количества дисков равным трем (Kol_diskov = 3).

									4	ПБ(0,1,2,3)
						3	ПБ(1,1,3,2)	→	5	ПД(1,3)
									6	ПБ(0,2,3,1)
			2	ПБ(2,1,2,3)	→	7	ПД(1,2)
									9	ПБ(0,3,1,2)
						8	ПБ(1,3,2,1)	→	10	ПД(3,2)
1	ПБ(3,1,3,2)	→	12	ПД(1,3)					11	ПБ(0,1,2,3)
									15	ПБ(0,2,3,1)
			13	ПБ(2,2,3,1)	→	14	ПБ(1,2,1,3)	→	16	ПД(2,1)
									17	ПБ(0,3,1,2)
						18	ПД(2,3)
									20	ПБ(0,1,2,3)
						19	ПБ(1,1,3,2)	→	21	ПД(1,2)
									22	ПБ(0,2,3,1)

Выясним, куда необходимо перекладывать кольца (номер в рамке означает порядок вызова действия).

Д ано: Результат:

5 шаг: 7 шаг: 10 шаг: 12 шаг: 16 шаг: 18 шаг:

21 шаг:

На экране после выполнения программы будет выведено:

1->3

1->2

3->2

1->3

2->1

2->3

1->3