Metoda Backtracking

Previzualizare referat:

Extras din referat:

clrscr; write (n=); readln (n); end; procedure init (k: integer); begin x[k]: =0; end; function exista (k: integer): Boolean; begin exista: = (x[k]0 do if exista (k) then begin x[k]: =x[k]+1; if cont (k) then if solutie (k) then tipar (k); else begin k: =k+1; init (k); end; end; else k: =k-1; end; begin citire; bkt; readln end. Algoritmul utilizat pentru generarea acestor combinari are in vedere faptul ca orice permutare este alcatuita din toate elementele multimii, care sunt distincte.

Pentru a scrie programul, stabilim urmatoarele repere: Vectorul solutie are n componente: x[k]=v are semnificatia ca valoarea v este asezata pe pozitia k in combinatie; Pentru orice k din {1, k-1} multimea valorilor posibile pentru x[k] este Ak={1, 2, k-1}; initializare se va face cu x[k]=0; Conditia de continuare pentru ca o valoare x[k] sa fie acceptata trebuie ca pentru orice I apartine {1, 2, k-1}, x[k] diferit x[i] (elementele nmultimii nu trebuie sa se repete); Am gasit o solutie finala daca an completat toate componentele vectorului (deci k=n). Pentru exemplul considerat, initial k=1, x[k]=0; (se incepe cu prima componenta si nu s-a testat nici o valoare). Vectorul solutie se va completa astfel; Stabilim prima valoare posibila pentru componenta k=1; aceasta convine si trecem la urmatoarea comoonenta; k=2. Stabilim prima valoare posubila pemtru componenta; k=2, x[2]=1; Conditiile de continuare nu sunt indeplinite, deoarece valoare 1 mai apare in aceasta combinatie.

De aceea ramanem la k=2. Testam urmatoarea valoarea posibila pentru x[2], care este 2 convine si se trece la urmatoarea componenta, k=3. Incepem cu prima valoare posibila pentru aceasta componenta, x[3]=1; nu Convine, deci ramanem la k=3. Urmatoarea valoare posibila pentru x[k] este 2 si din nounu convine.

Valoarea x[3]=3 corespunde; cum am completat toate cele n=3 componente, tiparim solutia (1, 2, 3); valoarea 3 este ultima valoare posibila si ca urmare revenim la componenta anterioara, k=2. Ultima valoare testate pentru x[2] era 2, de aceea trecem la urmatoarea valoare, x[2]=3, care convine si deci trecem la k=3. Testam urmatoarea valoare posibila pentru x[3], care este 2 convine cum am completat vectorul x, tiparim solutia (1, 3, 2) si urmatoarea la k=3. Testam ultima valoare posibila pentru aceasta componenta, x[3]=3; nu convine, deci revenim la k=2; Pentru x[2] am testat toate valorile posibile si ca urmare revenim la k=1. Ultima valoare testate pentru x[1] este 1; deci verificam ...

Download referat

Primești referatul în câteva minute,
cu sau fără cont

Alte informații:
Tipuri fișiere:
doc
Diacritice:
Nu
Nr fișiere:
1 fisier
Pagini (total):
4 pagini
Imagini extrase:
4 imagini
Nr cuvinte:
492 cuvinte
Nr caractere:
2 888 caractere
Marime:
8.70 KB (arhivat)
Nivel studiu:
Liceu
Tip document:
Referat
Materie:
Informatica
Tag-uri:
backtracking, algoritmi
Data publicare:
26.12.2009
Structură de fișiere:
  • Metoda Backtracking - Varianta 4
    • Referat.doc
Predat:
la liceu
Te-ar putea interesa și:
Academia Franceza definea informatica: Stiinta tratarii rationale prin masini automate a...
Prezentarea tehnicii Backtracking Aceasta tehnica se foloseste in rezolvarea problemelor care...
Stiva este acea forma de organizare a datelor (structura de date) cu proprietatea ca operatiile...
Deseori in practica trebuie sa rezolvam probleme care au un numar foarte mare de solutii...
Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele...
Sus!