Рекурсивное программирование (стр. 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

P1(3,0,1,2)
P1(2,0,2,1)
P1(1,0,1,2)
P2(1,0,2,1)
P3(1,1,2,0)
P2(1,0,1,2)
P3(2,2,1,0)	P1(1,2,0,1)
P2(1,2,1,0)
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

Задача 4

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

Для вычисления суммы n первых членов нужно знать сумму (n-1) первых членов и значение n-го члена:

Sn=Sn-1+an

Опишем рекурсивную функцию SUM, принимающую вещественные значения, решающую поставленную задачу. В ней для вычисления n - го члена арифметической прогрессии используется функция, описанная в предыдущем примере.

Program V;

Var a1, d, s :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;

Function SUM(p: integer):real;

  begin

        if p=1 then SUM:=a1

  else SUM:=SUM(p-1)+ ar_pr(p)

  end;

Begin

  writeln(‘a1’);  readln(a1);

  writeln(‘d’);  readln(d);

  writeln(‘n’);  readln(n);

  writeln(SUM(n))

End.

Приведем таблицу трассировки по уровням рекурсии при a1=2

                                                                d=5

                                                                n=5

Текущий Уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
0	ввод (a1=2, d=5, n=5)  SUM(5)	Bывод SUM(5)=60
1	n=5  SUM := SUM(4)+ ar_pr(5)	SUM:=38+ar_pr(4)+5=60
2	n=4  SUM:= SUM(3)+ ar_pr( 4)	SUM:=21+ar_pr(3)+5=38
3	n=3  SUM:= SUM(2)+ ar_pr(3)	SUM:=9+ar_pr(2)+5=21
4	n=2  SUM:= SUM(1)+ar_pr(2)	SUM:=2+ar_pr(1)+5=9
5	n=1  SUM:=2	SUM:=2

Задача 5

Написать рекурсивную программу поиска минимального элемента массива.

Опишем функцию P_min, которая определяет минимум среди первых n элементов массива. Параметрами этой функции является количество элементов в рассматриваемой части массива n и значение последнего элемента этой части массива – a[n]. При этом если n>2 то результатом является минимальное из двух чисел – a[n] и минимального числа из первых (n-1) элементов массива. Чтобы найти минимум всех элементов массива, нужно обратиться к функции P_min, указав  в качестве параметров значение последнего его элемента. Минимальное из 2-х чисел определяется с помощью функции min, параметрами которой являются эти числа.