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

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 

  1  2  3  4  5  6  7  8  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

  1  2  3  4  5  6  7  8  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 сигнализирует

  об окончании генерации.

  Алгоритм генерации, по сути, есть последовательное

  увеличение на 1 четверичного числа, хранящегося в иве-

  ивее (см. действия с многозначными числами).

}

program Signs;

uses

  Crt;

const

  N = 6;

  S = 35;

var

  I, p: Integer;

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

procedure WriteOneSign(Sgn: Integer);

begin

  case Sgn of

  0: Write(‘+’);

  1: Write(‘-‘);

  2: Write(‘*’);

  3: Write(‘/’);

  end;

end;

procedure OutputSigns;

var

  i: Integer;

begin

  for I := 1 to N-2 do

  Write(‘(‘);

  Write(‘1’);

  for I := 1 to N-2 do

  begin

  WriteOneSign(c[i]);

  Write(i+1, ‘)’);

  end;

  WriteOneSign(c[N-1]);

  Writeln(N, ‘=’, S);

end;

begin

  ClrScr;