ALG"7

9.1. Programowanie typu „dziel-i-rzgdź 227

Przypadek ogólny:

• jeśli tablica ma rozmiar > 2, to:

-    podziel ją na dwie części;

-    wylicz wartości (mini. maxl) i (min2, max2) dla obu tych części;

-    zwróć jako wynik min-min(minl, mini) i max=max(maxl. max2).

Odpowiadająca temu opisowi procedura rekurencyjna ma następującą postać: void min max2(int. left-, int right, int t f ] , int& nin, int& nax)

i

if (left==right)

min=max=t[left];    // jeden element

else

if {left==right-l)    fi dwa elementy

if(t[left]<t ; right])

{

min=t[left‘; max=t[right];

} else

{

min=t[right]; max=t[left];

else

(

int temp mini,temp_maxl,tenp_min2,tcmp_max2,mid; mi d=(left+right)/2;

min_max2(left,mid,t,tcmp_minl,temp_maxl); min_max2(mid+l,right,t,temp min2,temp_max2); if (tcmp_minl<temp_min2) //    (1)

min=emp_minl;

else

mi n= tempami n2;

if (teTnp_maxl>temp_max2 )    // (2)

nicłx=temp_maxl ;

else

max-temp_max2;

Porównując powyższe ze schematem ogólnym metody, można zauważyć, że:

•    „wystarczająco mały” oznacza rozmiar tablicy I lub 2;

•    mamy dwa przypadki elementarne;

•    dzielimy tablicę na 2 równe egzemplarze NI i N2\

•    wynikami cząstkowymi są pary: (tempminl. tempjnaxl) oraz (temp mini, temp_max2);