Рекурсивное программирование (стр. 2 )

Примеры рекурсивных алгоритмов

Задача 1 «О ханойских башнях»

В центре мира в вершинах равностороннего треугольника в землю вбиты три алмазных шпиля. На одном из них надето 64 золотых диска убывающих радиусов( самый большой – нижний). Трудолюбивые буддийские монахи день и ночь переносят диски с одного шпиля на другой. При этом диски надо переносить по одному и нельзя класть большой диск на меньший. Когда все диски перенесут на другой шпиль, наступит конец света( задачу и рассказ придумал математик Э. Люка в 1883 году).

Оставляя временно вопрос о конце света поищем алгоритм для перенесения (всех) дисков с одного шпиля на другой.

Т. е. Задача: Даны три столбика - A,B,C. На столбике А один на другом находятся четыре диска разного диаметра, пронумерованные сверху вниз. Причём они располагаются так, что каждый меньший диск находится на большем. Требуется переместить эти четыре диска на столбик B, сократив их взаиморасположением. Столбик С разрешается использовать как вспомогательный. При решении за один шаг допускается перемещать только один из верних дисков какого-либо столбика. Кроме того, больший диск никогда не разрешается класть на диск меньшего размера.

Идея рекурсивного алгоритма: если алгоритм Р( m, a, b, c) должен перенести верхние m дисков со шпиля а на шпиль b, то легко пишем алгоритм

P(m, a, b, c)

Если m=1, то перенести верхний диск со шпиля А на шпиль В

Иначе Р(m-1,a, c, b);

P(1, a, b, c);

P(m-1,c, b, a);

«По человечески» этот алгоритм очень понятен если m=1, то перенести один диск с А на В.

Если же m>1, то перенесём временно m-1 верхних дисков с А на С.

Потом перенесём один оставшийся диск с А на В и, наконец, перенесём m-1 дисков, хранящихся на С, на шпиль В.

Что касается перенесения m-1 дисков, то для этого подойдёт тот же алгоритм, но переносимых дисков.

Т. о., мы перейдём от m к m-1

от m-1 к m-2

от m-2 к m-3 и т. д.

и дойдём до единицы.

Чтобы записать этот алгоритм на каком-либо языке программирования обозначим шпили А, В, С цифрами 0, 1, 2 и будем печатать нужные переносы дисков.

Перенос со шпиля А на В будет изображаться надписью 0®1, с В на С – надписью 1®2 и т. п.

Program HANOJ;

var n:integer;

procedure P(m, a, b, c:integer);

begin

if m=1 then write(a, ‘®’, b, ‘ ‘)

else begin

P(m-1, a, c, b);

P(1, a, b, c);

P(m-1, c, b, a)

end

end;

Begin

readln(n); write(‘n=’, n); P(n, 0, 1, 2);

End.

При n=4 эта программа напечатает

0®2 0®1 2®1 0® 2 1®0 1 ®2

0®2 0®1 2®1 2®0 1®0 2 ®1

0®2 0®1 2®1

При n=3 эта программа напечатает :

0®1 0®2 1®2 0®1 2®1 2®0 2®1 0®1

1.	P1(3,0,1,2)
2.		P1(2,0,2,1)
3.			P1(1,0,1,2)
4.			P2(1,0,2,1)
5.			P3(1,1,2,0)
6.
7.		P2(1,0,1,2)
8.		P3(2,2,1,0)	P1(1,2,0,1)
9.			P2(1,2,1,0)
10.			P3(1,0,1,2)

Для нечетного n диски перекладываются на соседний шпиль по часовой стрелке, а для четного – против.

Задача 2

Написать рекурсивную программу вычисления n-й степени числа А.

Воспользуемся определением n-й степени числа х:

Аn=A*A*A*…..*A=An-1*A

Из определения следует, что для того, чтобы вычислить n-ю степень числа, необходимо знать значение (n-1)-й степени этого числа. Если же значение показателя степени 0, то значение степени равно 1.

Опишем рекурсивную функцию St, параметрами которой являются значения m и х.

Роль “заглушки” будет играть отношение m=0.

Program Z2;

Var A, n: integer;

Function St(x, m: integer): integer;

begin

if m=0 then St:=1

else St:=St(x, m-1)*x;

end;

Begin

writeln(‘ ввод основания А’);

writeln(‘ввод показателя n’);

writeln (n, ‘-я степень числа, А, ’равна’ , St(A, n))

End.

Текущий Уровень рекурсии	Рекурсивный спуск
0	ввод(а=2, n=3), STEP(2, 3)	Вывод Аn=23=8
1	m=3, STEP:= STEP(2, 2)*2	STEP:=4*2
2	m=2, STEP:= STEP(2, 1)*2	STEP:=2*2
3	m=1, STEP:= STEP(2, 0)*2	STEP:=1*2
4	m=0, STEP:=1

Задача 3

Написать рекурсивную программу вычисления n- го члена арифметической прогрессии.

Для вычисления n-го члена арифметической прогрессии необходимо знать значение ее первого члена и значение разности d:

an=an-1+d.

Т. е., чтобы найти n-й член, нужно последовательно вычислить все предыдущие члены от (n-1)-го до 2-го. Опишем функцию ar_pr, (параметром которой является номер вычисляемого лена арифметической прогрессии), принимающую значения вещественного типа.

Program Z3;

var a1, d: real;

n: integer;

Function ar_pr (l: integer): real;

begin

if l=1 then ar_pr:=a1

else ar_pr:=ar_pr(l-1)+d;

end;

Begin

writeln(‘ввод 1-го члена арифметической прогрессии а1’);

readln(a1);

writeln(‘ввод разности арифметической прогрессии d’);

readln(d);

writeln (‘ввод номера члена прогрессии n’);

readln(n);

writeln(n, ‘-й член арифметической прогрессии равен’, ar_pr(n), ‘.’)

End.

Текущий Уровень рекурсии	Рекурсивный спуск
0	ввод (a1=5, d=10, n=6) ar_pr(6)	Bывод ar_pr(6)=55
1	l=6 ar_pr:= ar_pr(5)+10	ar_pr:=45+10
2	l=5 ar_pr( 4)+10	ar_pr:=35+10
3	l=4 ar_pr:= ar_pr(3)+10	ar_pr:=25+10
4	l=3 ar_pr:= ar_pr(2)+10	ar_pr:=15=10
5	l=2 ar_pr:= ar_pr(1)+10	ar_pr:=5+10
6	l=1 ar_pr:= a1	ar_pr:=5