Structuri de date si algoritmi

Previzualizare documentatie:

Extras din documentatie:

Se considera vectorul a cu n componente numere intregi. Sa se sorteze crescator, utilizand 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 gasesc discurile de diametre diferite asezate in ordine descrescatoare a diametrelor privite de jos in sus. Se cere sa se mute discurile respectand regulile:

- la fiecare pas se muta cate un disc

- nu este permis sa se aseze 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 ofera mai multe solutii si are ca rezultat obtinerea tuturor solutiilor problemei. Fiecare solutie se memoreaza intr-o structura de date de tip stiva implementata cu ajutorul unui vector. Deci fiecare solutie poate fi pusa sub forma unui vector.

Intr-un algoritm backtracking ne intereseaza toate solutiile posibile. Pentru a obtine fiecare solutie finala se completeaza stiva nivel cu nivel trecand astfel prin niste solutii partiale. Astfel solutiile finale cat si cele partiale pentru a fi luate in considerare trebuie sa indeplineasca anumite conditii numite conditii de validare. O solutie care indeplineste o astfel de conditie se numeste solutie valida.

Toate configuratiile stivei ce reprezinta solutii finale sunt alcatuite din elementele aceleiasi multimi bine definite pe care o numim multimea solutiilor. Fiecare noua solutie partiala se obtine prin completarea solutiei partiale precedente cu inca o nivel pe stiva. La fiecare nivel se pun valori din multimea solutiilor care nu au fost incercate pana cand se obtine o solutie valida. In acest moment se trece la nivelul urmator in stiva pentru a completa mai departe solutia reluand incercarile pe noul nivel.

La un moment dat pe un anumit nivel nu mai exista nici o valoare neincercata din multimea valorilor problemei. In acest caz se face un pas inapoi in stiva la nivelul anterior si se reia cautarea cu valorile ramase neincercate pe acest nivel anterior.

Respectivul nivel a mai fost vizitat dar l-am abandonat dupa ce am pus o valoare care a generat o solutie valida. Deci este posibil sa fi ramas aici valori neincercate. Daca nici pe acest nivel nu mai avem valori neincercate mai facem un pas inapoi in stiva. Mecanismul revenirilor a determinat denumirea de metoda backtracking.

Plecand de la nivelul 1 si repetand algoritmul pana cand pe toate nivelele au fost incercate toate valorile din multimea valorilor se obtin solutii finale care se tiparesc.

Vom implementa metoda backtracking iterativ folosind o rutina unica aplicabila oricarei probleme. Rutina va apela proceduri si functii care au intotdeauna acelasi nume si parametri si care din punct de vedere al metodei realizeaza acelasi lucru.

Sarcina rezolvatorului este sa scrie explicit - pentru fiecare problema - procedurile si functiile aplicate pe rutina. Astfel gasirea urmatorului element netestat de pe un nivel k al stivei St se face cu procedura succesor (as,St,k)

Odata ales un element testarea conditiilor de validare se face cu procedura valid (ev,St,k).

Testul daca s-a ajuns sau nu la o solutie finala se face cu functia solutie (k)

Solutia se tipareste cu procedura tipar.

De asemenea fiecare nivel al stivei trebuie initializat cu o valoare aflata inaintea tuturor valorilor posibile din multimea solutiilor. Aceasta afisare se face cu procedura init (k,St).

Download gratuit

Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.

Alte informații:
Tipuri fișiere:
doc
Diacritice:
Da
Nota:
9/10 (1 voturi)
Nr fișiere:
1 fisier
Pagini (total):
37 pagini
Imagini extrase:
37 imagini
Nr cuvinte:
5 651 cuvinte
Nr caractere:
28 020 caractere
Marime:
25.09 KB (arhivat)
Nivel studiu:
Facultate
Tip document:
Documentatie
Domeniu:
Calculatoare
Data publicare:
18.09.2017
Structură de fișiere:
  • Structuri de date si algoritmi.doc
Predat:
la facultate

Ai gasit ceva în neregulă cu acest document?

Te-ar putea interesa și:
Stiva este o structura de date in care introducerea (extragerea) de elemente se poate efectua...
Curs 1 Structuri de date Structurile de date erau definite in limbajul C drept organizarea...
1. Conceptul de data In informatica, prin data, se desemneaza un model de reprezentare a...
1 Structuri de date fundamentale 1.1 Introducere - Sistemele de calcul moderne sunt dispozitive...
Un pointer (variabila referinta) este o variabila ce contine adresa unei alte variabile, numite...
Sus!