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

Задача 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, параметрами которой являются эти числа.

Program Example_5;

Const n=10;

a: ar=(4, 2, -1, 5, 2, 9, 4, 8, 5, 3);

type ar=array[1..n] of integer;

Function min(a, b:integer):integer;

begin

if a>b then min:=b

else min:=a;

end;

Function P_min(n, b: integer):integer;

begin

if n=2 then P_min:=min(a[2], a[1])

else P_min:=min(a[n], P_min(n-1, a[n]));

end;

Begin

writeln(‘минимальный элемент массива-‘, P_min(n, a[n])

End.

Задача 6 «Лабиринт»

Может ли путник выйти из лабиринта? Если может, то напечатать путь от выхода до начального положения путника.

Лабиринт задан массивом А размером 40х40, в котором:

А[k,m]=0, если клетка [k,m] «проходима»

А[k,m]=1, если клетка [k,m] «непроходима».

Начальное положение путника задаётся в проходимой клетке [i,j]. Путник может перемещаться из одной проходимой клетки в другую, если они имеют общую сторону. Путник выходит из лабиринта, когда попадает в граничную клетку (т. е. клетку [k,m], где k или m равны 1 или 40.

Решение распадается на 2 части: поиск пути для выхода и печать обратного пути – от выхода до начального положения путника.

Простейшее решение первой части такое:

- Запишем в клетку A[i,j], где вначале находится путник, число 2 и положим k=2.

- Просмотрим все клетки А лабиринта. Для каждой из них, если в ней записан 0, прочтём четырех из её соседей. Если хоть в одной из соседних клеток записано число k (сейчас ещё равное 2), то в рассматриваемую клетку А впишем число k+1/

- Теперь увеличим k:=k+1 и снова рассмотрим все клетки А. Этот процесс закончится когда-либо число будет вписано в граничную клетку ( выхода нет). Просмотров всего массива будет столько, сколько клеток окажется в кратчайшей дорожке.

Предыдущий алгоритм легко улучшить. На каждом шаге будем по-прежнему рассматривать все клетки А лабиринта. Если в клетке записан 0, а в какой-либо соседней находится число k>=2, то впишем в клетку А число k+1. Ясно, что это тоже решение задачи. Но если повезет, то здесь решение найдётся быстрее.

Заведомо эффективнее будет программа, которая начиная с исходной клетки, (куда вначале записывается число 2), ищет первого же свободного ( т. е. с числом 0) соседа. Вписывает в него 3 и ищет его свободного соседа, чтобы вписать в него 4 и т. д.

Процесс прервется либо при достижении границы (выход найден), либо оттого, что свободных соседей не будет (тупик).

Если тупик возникает в соседней клетке (где записано число 2), то выхода нет. Если же тупиковая клетка иная и в неё вписано число k>2, то следует вписать в неё число 1 (сделать её непроходимой) и перейти к её соседней клетке с числом k-1. такая клетка есть и единственна.

!!! Программу для решения задачи о лабиринте можно сильно сократить. Если записать её рекурсивно.

Program labirint;

Const m=15;

N=15;

Var i, j: integer;

otvet: oolean;

A: array [1..m, 1..n] of byte.

Procedure L (i, j: integer);

begin

if not( otvet) then

if a[i, j]=0 then begin

if (i=1) or (i=m) or (j=1) or (j=m) then otvet:=true;

A[i, j]:=1; L(i, j-1); L(i, j+1); L(i-1, j); L(i+1, j);

If otvet then writeln (i, ‘ ‘ ,j)

end;

end;

Begin

For i:=1 to m do

For j:=1 to n do begin

Write(‘A[‘ , i, ’,’ ,j, ’]:=’);

Readln (a[i, j])

end;

writeln;

writeln(‘i, j:=’);

readln(i, j);

writeln;

otvet:= false;

L(i, j);

If not( otvet) then writeln(‘нет выхода’)

End.

Задача 7 «Быстрая сортировка»

Реализация метода быстрой сортировки массива является прекрасным примером использования рекурсии. Этот метод был разработан в 1962 году профессором Оксфордского университета К. Хоаром.

Принцип метода:

Выбираем центральный элемент массива А и записываем его в переменную В. Затем элементы массива просматриваем поочередно слева-направо и справа-налево. При движении слева-направо ищем элемент А[i], который будет больше или равен В, и запоминаем его позицию. При движении справа-налево ищем элемент A[i], который будет меньше или равен В, и также запоминаем его позицию.

Найденные элементы меняем местами и т. д., пока при очередной итерации поиска встречные индексы i и j не пересекутся.

A В=7 n=10

9 10

9

4

12

1

7

6

9

4

2

10

L=1 i=1 j=9 R=n

9 2

i=3 j=8

12 4

i=5 j=6

7 6

`

5=j i=6

9 10

2

4

4

1

6

7

8

12

9

10

<=В >=В

После этого первый этап считается законченным, после чего элементы исходного массива окажутся разделёнными на 2 части относительно значения В – все элементы, которые <=В, будут располагаться слева от границы пересечения индексов i и j, а все элементы, которые >=В, будут располагаться справа от границы. Т. о., относительно значения В массив получается отсортированным, но левая и правая его части ещё не упорядочены.

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

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

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

Program QuickSort;

Uses Crt;

Const n=20;

Var A:array [1..n] of integer;

i: word;

Procedure QSort (L, R: word);

Var B, x : integer;

i, j: word;

begin

B:=A[(L+R) div 2];

i:=L; j:=R;

while i<=j do begin

while A[i]<B do i:=i+1;

while A[i]>B do j:=j-1;

if i<=j then begin

x:=A[i];

A[i]:=A[j];

A[j]:=x;

i:=i+1;

j:=j-1

end;

if L<R then QSort(L, j);

if i<R then QSort(i, R);

end;

Begin

ClrScr;

Writeln(‘ ведите элементы массива’);

For i:=1 to n do read (A[i]);

Readln;

QSort(1,n);

Writeln (‘ Отсортированный массив:’);

For i:=1 to n do write (A[i]:8);

End.

­­

Задача 8

В написанном выражении ((((1?2)?3)?4)?5)?6)….?N вместо каждого знака? вставить знак одной из четырёх операций: + - * / так, чтобы результат вычислений равнялся S (при делении дробная часть в частном отбрасывается). Найти все решения.

Обобщим задачу. Пусть требуется так расставить знаки

'+', '-', '*', '/' в выражении ((1?2)?3)...?N,

чтобы в результате выполнения получилось значение S.

Алгоритм.

Конкретную расстановку знаков будем кодировать массивом

c: array [0..(N-1)] of Integer

('+' -> 0,

'-' -> 1,

'*' -> 2,

'/' -> 3).

Чтобы сгенерировать все возможные комбинации знаков,

требуется, фактически, построить все четверичные числа

длины N-1. Будем строить их от 00..0 до 33..3. Элемент

c[0] будет фиктивным и условие c[0] <> 0 сигнализирует