A. Considerații teoretice

Principiul de bază al acestei tehnici este acela de a descompune (divide) o problemă complexă în mai multe subprobleme a căror rezolvare este mai simplă și din soluțiile cărora se poate determina soluția problemei inițiale. Acest mod de lucru se repetă recursiv conform algoritmului prezentat în continuare (în pseudocod):

procedure rezolva(x);
begin
  if  *(x este divizibil in subprobleme)  then
  begin
    * divide pe x in doua sau mai multe partitii x1 ... xk;
    rezolva (x1);
    ...
    rezolva (xk); 
    *combina cele k solutii partiale intr-o solutie pentru x
  end
  else
    *rezolva pe x direct
end;

Dacă recombinarea soluțiilor parțiale este substanțial mai simplă decât rezolvarea întregii probleme, aceasta tehnică va conduce la proiectarea unor algoritmi eficienți.


B. Exemple

O problemă des întâlnită la procesările grafice este găsirea extremelor valorilor componentelor unui vector. Algoritmul cel mai simplu este:

var A: array[1..N] of integer;
...

  MIN := A[1];
  MAX := A[1];
  For i := 2 to N do
  begin       
    if MIN > A[i] then MIN := A[i];
    if MAX < A[i] then MAX := A[i];
  end

Această metodă baleiază întregul vector, fiecare element al lui A se va compara de două ori, o data pentru aflarea maximului și o dată pentru aflarea minimului. Acest algoritm nu ia în considerare faptul că orice element ales ca minim provizoriu nu mai poate fi un candidat potențial pentru maxim (el este deja dovedit mai mic decât alte elemente) și invers. Această risipă se poate evita.

Aplicând tehnica divizării, se împarte tabloul în două părți și se compară valorile minime și maxime ale subtablourilor rezultate, stabilindu-se minimul și maximul absolut. În continuare se procedează în aceeași manieră, reducând de fiecare dată la jumătate dimensiunea subtablourilor. Pentru dimensiunea 1 sau 2 soluția este evidentă. Procedura este următoarea:

type Tab: array[1..N] of integer;
var A: Tab;       {se declara ca si date globale }

procedure min_max(A: Tab; I, J: integer; var MIN, MAX: integer);
var Mijloc, MIN1, MAX1, MIN2, MAX2: integer;
begin
  if J <= I+1 then  {dimensiunea subtabloului <=2}
  begin
    if  A[I] < A[J] then
    begin
      MIN := A[I];
      MAX := A[J] 
    end;    
    else   
    begin
      MIN := A[J];
      MAX := A[I]
    end       
    else 
    begin
      MIJLOC := (I+J) div 2;   {divizare}
      min_max(A, I, MIJLOC, MIN1, MAX1);
      min_max(A, MIJLOC+1, J, MIN2, MAX2);
      if MAX2 > MAX1 then MAX := MAX2
      else MAX := MAX1;
      if MIN2 < MIN1 then MIN := MIN2
      else MIN := MIN1;
    end
  end
end;

Deși acest algoritmul pare mai lung și complicat, pentru anumite valori ale lui N necesită mai puține comparații decât algoritmul clasic.

O altă problemă celebră este "Problema turnurilor din Hanoi": Se dau 3 tije A, B, C. Pe tija A se afla N discuri de dimensiuni diferite, ordonate astfel încât să reprezinte o piramidă circulară. Să se treacă toate discurile pe tija C folosind tija B ca tijă de manevră, astfel incât, tot timpul, nici un disc de dimensiune mai mare să nu fie suprapus peste unul mai mic.
O ilustrare a acestei probleme se poate urmări în următorul applet :

Programul de navigare nu suportă appleturi Java.

Mutarea celor N discuri de pe tija  A pe tija C poate fi gândită astfel: se mută cele N-1 discuri de deasupra discului 1 pe tija de manevră B, după care se mută discul 1 pe tija C. Apoi cele N-1 discuri de pe tija B trebuie aduse pe C. Dar, cele două deplasări ale grupului de N-1 tije înseamnă rezolvarea problemei inițiale, având însă cu un disc mai puțin. Pe de altă parte, tija C se poate folosi ca tijă de manevră, ea fiind liberă în prima fază, iar in a doua fază având la bază discul 1, care este mai mare decât oricare din cele N-1 discuri din pachetul care trebuie mutat. Deci pașii fundamentali ai acestui algoritm se pot exprima astfel:

*mută k-1 discuri de la origine la intermediar
*mută discul rămas de la origine la destinație
*mută k-1 discuri de la intermediar la destinație

O soluție simplă, care nu afișează conținutul tijelor ci doar direcția deplasărilor (considerând că se ia automat discul cel mai de sus) este următoarea:

program Hanoi;

type Tije = (A, B, C);

var discuri: integer;

procedure muta_stiva(inaltime: integer; de_la, la, prin: Tije);

  procedure muta_disc(de_la, la: Tije);
  begin	{muta_disc}
    case de_la of
      A: write('A --> ');
      B: write('B --> ');
      C: write('C --> ');
    end;
    case la of
      A: writeln('A ');
      B: writeln('B ');
      C: writeln('C ');
    end;
  end;	{muta_disc}

begin	{muta_stiva}
  if  inaltime > 0 then begin
    muta_stiva(inaltime-1, de_la, prin, la);
    muta_disc(de_la, la);
    muta_stiva(inaltime-1, prin, la, de_la);
  end;    
end;

begin	{programul principal}
  write('Numarul de discuri: ');
  readln(discuri);
  muta_stiva(discuri, A, C, B);
  readln;
end.

C. Teme

  1. Să se scrie un program care caută minimul și maximul într-un vector folosind ambele metode prezentate. Pentru N=16 să se ruleze programul pas cu pas și să se numere câte comparații (if-uri) se fac cu fiecare metodă. Remarcă: instrucțiunea for efectueză, în mod intrinsec, o comparație la fiecare iterație.

  2. Să se rezolve problema turnurilor din Hanoi afișând în mod explicit conținutul tijelor. Situația după fiecare mutare va fi exprimată prin câte o linie de text. Tijele vor fi separate prin ";" (punct și virgulă), iar discurile vor fi reprezentate printr-un număr egal cu dimensiunea discului. Discurile se separă cu " " (spațiu). De exemplu, pentru 3 discuri vom avea soluția:

    3 2 1 ; ;
    3 2 ; ; 1
    3 ; 2 ; 1
    3 ; 2 1 ;
    ; 2 1 ; 3
    1 ; 2 ; 3
    1 ; ; 3 2
    ; ; 3 2 1
    

  3. * Să se genereze toate șirurile rezultate din combinările Cnm ale unui șir de numere întregi, fiecare număr cu o singură apariție, de lungime N.