Structuri de date și algoritmi

Se considera vectorul a cu n componente numere întregi. Să se sorteze crescător, utilizând sortarea prin interclasare.

program sort;

type vector=array[1 10] of integer;

var a:vector;

n,i:integer;

procedure sort(p,q:integer;var a:vector);

var m:integer;

begin

if a[p]>a[q] then begin m:=a[p]; a[p]:=a[q]; a[q]:=m end;

end;

procedure interc(p,q,m:integer;var a:vector);

var b:vector;

i,j,k:integer;

begin

i:=p;

j:=m+1;

k:=1;

while (i<=m) and (j<=q) do

if a[i]<=a[j] then begin b[k]:=a[i]; i:=i+1; k:=k+1 end else begin b[k]:=a[j];j:=j+1;k:=k+1 end;

if i<=m then

for j:=i to m do begin b[k]:=a[j]; k:=k+1; end else

for i:=j to q do begin b[k]:=a[j]; k:=k+1; end;

k:=1;

for i:=p to q do begin a[i]:=b[k]; k:=k+1; end

end;

procedure divimp(p,q:integer; var a:vector);

var m:integer;

begin

if (q-p)<=1 then sort(p,q,a) else begin m:=(p+q) div 2; divimp(p,m,a); divimp(m+1,q,a); interc(p.q.m.a); end

end;

write(‘n= ‘);read(n);

for i:=1 to n do

begin

write(‘a[‘,i,’]=’);readln(a[i]);

end;

divimp(1,n,a);

for i:=1 to n do

writeln(a[i]);

end.

Turnurile din Hanoi

Se dau 3 tije simbolizate prin a,b,c. Pe tija a se găsesc discurile de diametre diferite aşezate in ordine descrescătoare a diametrelor privite de jos in sus. Se cere sa se mute discurile respectând regulile:

- la fiecare pas se muta cate un disc

- nu este permis sa se aşeze un disc cu diametru mai mare peste un disc cu diametru mai mic.

program p2;

var a,b,c:char;

n:integer;

procedure hanoi(n:integer;a,b,c:char);

begin

if n=1 then writeln(a,b)

else begin hanoi(n-1,a,c,b); writeln(a,b); hanoi(n-1,c,b,a); end;

end;

begin

write('n=');readln(n);

a:='a';b:='b';c:='c';

hanoi(n,a,b,c);

readln;

end.

Metoda backtracking Created by Iorga Codrin

Metoda BACKTRACKING

Este o tehnica de programare aplicabila algoritmilor care oferă mai multe soluţii şi are ca rezultat obţinerea tuturor soluţiilor problemei. Fiecare soluţie se memorează într-o structura de date de tip stivă implementată cu ajutorul unui vector. Deci fiecare soluţie poate fi pusă sub forma unui vector.

Într-un algoritm backtracking ne interesează toate soluţiile posibile. Pentru a obţine fiecare soluţie finală se completează stiva nivel cu nivel trecând astfel prin nişte soluţii parţiale. Astfel soluţiile finale cât şi cele parţiale pentru a fi luate în considerare trebuie să îndeplinească anumite condiţii numite condiţii de validare. O soluţie care îndeplineşte o astfel de condiţie se numeşte soluţie validă.

Toate configuraţiile stivei ce reprezintă soluţii finale sunt alcătuite din elementele aceleiaşi mulţimi bine definite pe care o numim mulţimea soluţiilor. Fiecare nouă soluţie parţială se obţine prin completarea soluţiei parţiale precedente cu încă o nivel pe stivă. La fiecare nivel se pun valori din mulţimea soluţiilor care nu au fost încercate până când se obţine o soluţie validă. În acest moment se trece la nivelul următor în stivă pentru a completa mai departe soluţia reluând încercările pe noul nivel.

La un moment dat pe un anumit nivel nu mai există nici o valoare neîncercată din mulţimea valorilor problemei. În acest caz se face un pas înapoi în stivă la nivelul anterior şi se reia căutarea cu valorile rămase neîncercate pe acest nivel anterior.

Respectivul nivel a mai fost vizitat dar l-am abandonat după ce am pus o valoare care a generat o soluţie validă. Deci este posibil să fi rămas aici valori neîncercate. Dacă nici pe acest nivel nu mai avem valori neîncercate mai facem un pas înapoi în stivă. Mecanismul revenirilor a determinat denumirea de metoda backtracking.

Plecând de la nivelul 1 şi repetând algoritmul până când pe toate nivelele au fost încercate toate valorile din mulţimea valorilor se obţin soluţii finale care se tipăresc.

Vom implementa metoda backtracking iterativ folosind o rutină unică aplicabilă oricărei probleme. Rutina va apela proceduri şi funcţii care au întotdeauna acelaşi nume şi parametri şi care din punct de vedere al metodei realizează acelaşi lucru.

Sarcina rezolvatorului este să scrie explicit - pentru fiecare problemă - procedurile şi funcţiile aplicate pe rutină. Astfel găsirea următorului element netestat de pe un nivel k al stivei St se face cu procedura succesor (as,St,k)

Odată ales un element testarea condiţiilor de validare se face cu procedura valid (ev,St,k).

Testul dacă s-a ajuns sau nu la o soluţie finală se face cu funcţia soluţie (k)

Soluţia se tipăreşte cu procedura tipar.

De asemenea fiecare nivel al stivei trebuie iniţializat cu o valoare aflată înaintea tuturor valorilor posibile din mulţimea soluţiilor. Această afişare se face cu procedura init (k,St).