Приклади рекурсивних програм

 

6.3.1. Алгоритми «Розділяй і пануй»

 

Мабуть, найбільш значущім і найбільш використовуваним методом проектування ефективних алгоритмів є метод, що зветься методом декомпозиції (або метод “ розділяй і пануй”, або метод розподілу). Цей метод пропонує таку декомпозицію (розподіл) задачі розміру Nна більш малі задачі, що на основі їх розв’язання можна одержати рішення вихідної задачі. До алгоритмів цього типу відносяться сортування, з порядоком О(n*log(n)), задачі з комбінаторики, задача про ханойські вежі, що розглядаються далі.

Швидке сортування Хоара.Алгоритм сортування Хоара і його ітераційна реалізація, що вимагала роботу з програмним стеком, були наведені в п. 5. В програмному прикладі 6.4 показана рекурсивна реалізація цього алгоритму.

Елементи масиву зі значеннями елементів менше ключового елемента (того, що поділіть масив на дві частини) розташовуються ліворуч, інші – праворуч. Щоб виконати ці перестановки, введено два індекси і та j, що указують відповідно на лівий і правий кінці тієї частини масиву А, де в даний момент порівнюються елементи А[і] та A[j]. Після кожного порівняння змінюється лише один індекс (і або j), причому і - збільшується, j – зменшується. Проход закінчується, коли індекси зустрінуться.

{===== Програмний приклад 6.4 =====}

Procedure Sort(var a:Seq; L,R:integer);

Var і,j:integer; {поточні індекси в масиві}

flag:boolean; {при flag=true–уменьш. j, інакше–збіл. i}

x:integer;

begin

if R<= L Exit; {підмножина порожня або є 1 эл-т}

і:=L; j:=R; flag:=true; {спочатку буде змінюватися j}

while і<j do

begin if a[і]>a[j] then

begin x:=a[і]; a[і]:=a[j]; a[j]:=x; {перестановка}

flag:= not flag; {після перестановки міняється індекс}

end; {реально змінюється тільки один індекс}

if flag then j:=j–1 else і:=і+1;

end;

Sort(a,L,і – 1); {сортування лівого підмасива}

Sort(a,i + 1,R); {сортування правого підмасива}

end;

Алгоритми сортуваннь на деревах також можуть бути реалізовані рекурсивно.

Комбінаторика: задача про комітети.Дано N і K – цілі позитивні числа. Визначити C(N,K)– кількість сполучень з N по К елементів. Нехай N=5, К=2. Елементи, що складають вихідний набір A, B, C, D, E. Які можуть бути пари неповторюваних елементів?

За принципом «розділяй і пануй» спрощують задачу, розбиваючи її на більш дрібні. Для цього виключають А з набору вихідних елементів. З отриманих елементів можуть бути сформовані такі пари: BC, BD, BE, CD, CE, DE. У той же час А с кожним елементом створює такі пари AB, AC, AD, AE. При цьому А просто додали до кожного елемента в групах (було 4 групи по 1 елементу в групі). Отримані пари разом – це є всі можливі пари.

У такий спосіб від C(N,K) перейшли до C(N – 1,K) і C(N – 1,K – 1), а для визначення загальної кількості сполучень останні варто скласти.

У програмному прикладі 6.5 подана реалізація описаного алгоритму. Умови останова: їх декілька.

1). Якщо К>N – немає достатньої кількості елементів, для формування набору.

2) К=N і К=0 – можливий лише один набір.

{===== Програмний приклад 6.5 =====}

function comm(n,k:byte):byte;

begin

if k>n then comm:= 0 else

if (n=k)or(k=0) then comm:=1 else

comm:=comm(n–1,k-1) + comm(n-1,k);

end;

Для N = 5 і К = 2 кількість комбінацій дорівнює 10, що визначається як (N*K)