A. Considerații teoretice
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;
B. Exemple
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
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;
*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
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
3 2 1 ; ; 3 2 ; ; 1 3 ; 2 ; 1 3 ; 2 1 ; ; 2 1 ; 3 1 ; 2 ; 3 1 ; ; 3 2 ; ; 3 2 1