![Algoritmul General
Procedure Reluare(k:integer);
begin
if k<=n then
begin
X[k]:=primulelement(k);
if Continuare(k) then Reluare(k+1);
while ExistaSuccesor(k) do
Begin
X[k]:=Succesor(k);
If Continuare(k) then Reluare(k+1)
End;
End
Else PrelucrareaSolutiei;
End;](https://image.slidesharecdn.com/metodabacktracking-140511141037-phpapp01/85/Metoda-backtracking-4-320.jpg){kind=tracking}
![Partiﾈ嬖ile unui numﾄビ natural:
program Partitii_nr_natural; var n, ns: byte;
sol: array[1..20] of byte; procedure afis(l: byte);
var i: byte;
begin
inc(ns); write 'Solutia ', ns, ' : ');
for i:=1 to l do write(sol[i]:3);
writeln;
end;
procedure back(i, sp: byte);
var j: byte;
begin
if sp = n then afis(i-1) else for j:=1 to n-sp do
if (j>=sol[i-1]; then begin
sol[i]:=j;
back(i+1, sp+j) end; end;
begin
read(n); ns:=0;
back(1,0); writeln(ns,'solutii');
end.](https://image.slidesharecdn.com/metodabacktracking-140511141037-phpapp01/85/Metoda-backtracking-7-320.jpg){kind=tracking}
More Related Content
What's hot (20)
Viewers also liked (13)
Similar to Metoda backtracking (20)
More from Balan Veronica (20)
Metoda backtracking
- 1. ELABORAT DE ELEVUL CLASEI XI -A窶截窶 COﾈ僞RU SERGIU Metoda Backtracking
- 2. ｗ Aceastﾄ tehnicﾄ poate fi utilizatﾄ pentru rezolvarea problemelor de cﾄブtare, putﾃ｢nd fi folositﾄ pentru generarea tuturor soluﾅ｣iilor posibile.
- 3. Se foloseﾅ殳e ﾃｮn rezolvarea problemelor care ﾃｮndeplinesc simultan urmﾄフoarele condiﾅ｣ii: ｗ Soluﾅ｣ia lor poate fi pusﾄ sub forma unui vector V = x1x2x3 窶ｦ窶ｦ. xn, cu x1竏A1 窶ｦ. Xn 竏 An ｗ Mulﾅ｣imile A1, A2, 窶ｦ An sunt mulﾅ｣imi finite, iar elementele lor se aflﾄ ﾃｮntr-o ordine bine stabilitﾄ ｗ Nu se dispune de o metodﾄ de rezolvare mai rapidﾄ
- 4. Algoritmul General Procedure Reluare(k:integer); begin if k<=n then begin X[k]:=primulelement(k); if Continuare(k) then Reluare(k+1); while ExistaSuccesor(k) do Begin X[k]:=Succesor(k); If Continuare(k) then Reluare(k+1) End; End Else PrelucrareaSolutiei; End;
- 5. Metoda poate fi folositﾄ la rezolvarea urmatoarelor probleme: ｗ generarea permutﾄビilor unei mulﾅ｣imi ｗ generarea aranjamentelor unei mulﾅ｣imi ｗ generarea submulﾅ｣imilor unei mulﾅ｣imi ｗ generarea submulﾅ｣imilor cu m elemente ale unei mulﾅ｣imi (combinﾄビi) ｗ generarea produsului cartezian a n mulﾅ｣imi ｗ generarea tuturor secvenﾅ｣elor de n (par) paranteze care se ﾃｮnchid corect. ｗ colorarea ﾅ｣ﾄビilor de pe o hartﾄ astfel ﾃｮncﾃ｢t oricare douﾄ ﾅ｣ﾄビi vecine sﾄ aibﾄ culori diferite ｗ aranjarea a n regine pe o tablﾄ de ﾅ歛h de dimensiune n fﾄビﾄ ca ele sﾄ se atace.
- 6. ｗ Partiﾅ｣iile unui numﾄビ natural. Fie n>0, natural. Sﾄ se scrie un program care sﾄ afiﾅ歹ze toate partiﾅ｣iile unui numﾄビ natural n. Numim partiﾅ｣ie a unui numﾄビ natural nenul n o mulﾅ｣ime de numere naturale nenule {p1, p2, 窶ｦ, pk} care ﾃｮndeplinesc condiﾅ｣ia p1+p2+ 窶ｦ+pk = n. Ex: pt n = 4 programul va afiﾅ歛:
- 7. Partiﾈ嬖ile unui numﾄビ natural: program Partitii_nr_natural; var n, ns: byte; sol: array[1..20] of byte; procedure afis(l: byte); var i: byte; begin inc(ns); write 'Solutia ', ns, ' : '); for i:=1 to l do write(sol[i]:3); writeln; end; procedure back(i, sp: byte); var j: byte; begin if sp = n then afis(i-1) else for j:=1 to n-sp do if (j>=sol[i-1]; then begin sol[i]:=j; back(i+1, sp+j) end; end; begin read(n); ns:=0; back(1,0); writeln(ns,'solutii'); end.
- 8. Concluzie ｗ ﾃ始 conlcuzie metoda reluﾄビii este o metodﾄ ce necesitﾄ mult timp de aceea trebuie sﾄ fie folositﾄ ca o ultimﾄ soluﾈ嬖e a problemei .Avantajul metodei este cﾄ nu se genereazﾄ toate soluﾈ嬖ile dar doar cele ce sunt convenabile rezolvﾄビii problemei date.
- 9. Link-uri utile ｗ http://software.ucv.ro/~cstoica/TP/backtracking.pdf ｗ http://info.mcip.ro/?t=back