Metoda backtraking

21
Proiect realizat de: Mascasan Anca; Profesor indrumator: Hozai Silvia.

description

Metoda backtraking. Proiect realizat de: Mascasan Anca; Profesor indrumator: Hozai Silvia. - PowerPoint PPT Presentation

Transcript of Metoda backtraking

Page 1: Metoda backtraking

Proiect realizat de: Mascasan Anca;

Profesor indrumator: Hozai Silvia.

Page 2: Metoda backtraking

Metoda Backtracking se aplică problemelor în care soluţia poate fi reprezentată sub forma unui vector – x = (x1, x2, x3, …xk,… xn) € S, unde S este mulţimea soluţiilor problemei şi S = S1 x S2 x… x Sn, şi Si sunt mulţimi finite având s elemente si xi € si , (¥)i = 1..n.

Metoda construieşte un vector soluţie în mod progresiv începând cu prima componentă a vectorului şi mergând spre ultima cu eventuale reveniri asupra atribuirilor anterioare.

Ea se aplica astfel : 1) se alege prima valoare sin S1 si I se atribuie lui x1 ; 2) se presupun generate elementele x1…x[k-1], cu valori din S1..S[k-1]; pentru generarea lui x[k] se alege primul element din S[k] disponibil si pentru valoarea aleasa se testează îndeplinirea condiţiilor de continuare.

Pot apărea următoarele situaţii :

a) x[k] îndeplineşte condiţiile de continuare. Daca s-a ajuns la soluţia finală (k = n) atunci se afişează soluţia obţinută. Daca nu s-a ajuns la soluţia finală se trece la generarea elementului următor – x [k-1];

b) x[k] nu îndeplineşte condiţiile de continuare. Se încearcă următoarea valoare disponibila din S[k]. Daca nu se găseşte nici o valoare în S[k] care să îndeplinească condiţiile de continuare, se revine la elementul x[k-1] şi se reia algoritmul pentru o nouă valoare a acestuia. Algoritmul se încheie când au fost luate in considerare toate elementele lui S1.

Urmeaza cateva probleme care se rezolva prin aceasta metoda:

Page 3: Metoda backtraking

Generarea permutărilor (interativ) Se citeşte un număr natural n. Să se genereze permutările de n elemente ale mulţimii {1,2,…,n}. Simulaţi executarea algoritmului pentru n=3.P3=3!=6(1,2,3);(1,3,2);(2,1,3);(2,3,1);(3,1,2);(3,2,1) type vector=array [1..100] of integer;var st:vector; n.k:integer; as,ev:boolean; procedure init(k:integer;var st:vector);begin st[k]:=0;end;procedure successor(var as:boolean; var st:vector; k:integer);beginif st[k]<n then begin st[k]:=st[k]+1; as:=true; end else as:= false;end; procedure continuare(var ev:boolean; var st:vector; k:integer);var i :integer;begin ev:=true; for i:=1 to k-1 do if st[k]=st[i] then ev:=falseend;

Page 4: Metoda backtraking

function solutie(k:integer):boolean;begin solutie:=(k=n);end;procedure tipar;var i:integer;begin for i:=1 to n do write (st[i]); writeln;end;Beginwrite(‘n=‘); readln(n);k:=1; init(k,st);while(k>0) do begin repeat successor(as,st,k); if as then continuare(ev,st,k); until (not as) or (as not ev); if as then if solutie(k) then tipar else begin k:=k+1; init(k,st); end; else k:=k-1; end;End.

Page 5: Metoda backtraking

Problema turelor (interativ) Să se determine toate posibilităţile de aranjare a n ture pe o tablă de şah de dimensiune nxn astfel încât turele să nu se atace reciproc. Tura atacă piesele aflate pe aceeaşi linie sau coloană. Obs: x[i] –reprezinta coloana pe care asezam tura de pe linia i.

type vector=array [1..100] of integer;var x:vector; n:integer; procedure solutie ;var i.j :integer; begin for i:=1 to n do begin for j:=1 to n do if x[i]=j then write(‘T’)

else write (‘ ‘); writeln; end; end;

Page 6: Metoda backtraking

function continuare(k:integer): boolean;var i :integer; ok: boolean; begin ok:=true; if k=1 then continuare:=true

else for i := 1 to k-1 do if x[k]=x[i] then ok :=false; contunuare:= ok; end;

procedure back(k:integer); begin if (k=n+1) then solutie

else begin for i:=1 to n do begin x[k]:=i; if continuare(k) then back(k+1); end; end; end;Begin write(‘n’); readln(n); back(1); readln;End.

Page 7: Metoda backtraking

Problema reginelor (interativ) Să se determine toate posibilităţile de aranjare a n regine pe o tablă de şah de dimensiune

nxn astfel încât reginele să nu se atace reciproc. Regina atacă piesele aflate pe aceeaşi linie, coloană sau diagonală.

Obs: st[i]- reprezinta coloana reginei de pe linia i.

type vector=array [1..100] of integer;var st:vector; n.k:integer; as,ev:boolean; procedure init(k:integer;var st:vector);begin st[k]:=0;end;procedure successor(var as:boolean; var st:vector; k:integer);beginif st[k]<n then begin st[k]:=st[k]+1; as:=true; end else as:= false;end; procedure continuare(var ev:boolean; var st:vector; k:integer);var i :integer;begin ev:=true; for i:=1 to k-1 do if (st[k]=st[i]) or (abs(st[k]-st[i])=abs(k-i)) then ev:false;end;function solutie(k:integer):boolean;begin solutie:=(k=n);end;

Page 8: Metoda backtraking

procedure tipar;var i:integer;begin for i:=1 to n do write (st[i]); writeln;end;Beginwrite(‘n=‘); readln(n);k:=1; init(k,st);while(k>0) do begin repeat successor(as,st,k); if as then

continuare(ev,st,k); until (not as) or (as not

ev); if as then if solutie(k) then

tipar else

begin

k:=k+1;

init(k,st);

end; else

k:=k-1; end;End.

Page 9: Metoda backtraking

Generarea produsului cartezian (interativ)Se citesc numerele naturale n şi p. Să se genereze toate elementele produsului cartezian P=AxAx...xA=Ap, unde A={1,2,…,n}.

type vector =array[1..25] of integer;var st,nr:vector; n:integer;procedure init;var i :integer; begin write (‘nr de multimi n=’);readln(n); for i:=1 to 25 do st[i]:=0; for i:=1 to n do begin write(‘cate elem are multimea’,i,’ : ‘); readln(nr[i]); end; end;procedure tipar(p:integer);var i :integer; begin for i:=1 to p do write(st[i] , ‘ ‘); writeln; end;

Page 10: Metoda backtraking

procedure back;var p:integer;begin p:=1; st[p]:=0; while p>0 do begin if st[p]<nr[p] then

begin st[p]:=st[p]+1; if true then

if p=n then tipar(p)

else beginp:=p+1;

st[p]:=0; end;

end; else p:=p-1;end;

end;Begin init; back; readln;End.

Page 11: Metoda backtraking

Plata unei sume cu bancnote de valori date (recursiv)Se dau suma S şi n tipuri de bancnote având valori a1,a2,…,an lei. Se cer toate modalităţile de plată a sumei S utilizând aceste bancnote. Se presupune că se dispune de un număr suficient din fiecare tip de bancnotă.

type vector =array [1..9] of integer;var sol ,a,b:vector; n,i,s :integer;procedure tipar (k: integer); begin writeln(‘ solutie’); for i:=1 to k do if sol[i]<>0 then writeln(sol[i], ‘bancnote de ‘, a[i]); readln;end;procedure plata(k,s0:integer); begin while (sol[k]<b[k]) and (s0+a[k]<=s) do begin sol[k]:=sol[k]+1; if sol[k]>0 then s0:=s0+a[k]; if s0:=s then tipar(k) else if k<n then plata(k+1,s0); end; sol[k]:= -1; end;Begin write(‘cate tipuri de banknote avem? ‘); readln(n) write(‘suma=’); readln(s); for i:=1 to n do begin write(‘valoarea monedei de tipul ‘,i,’ ‘); readln(a[i]); b[i]:=s div a[i]; sol[i]:= -1; end;plata(1,0);End.

Page 12: Metoda backtraking

Problema colorării hărţilor (interativ) Fiind data o hartă cu n ţări, se cere toate soluţiile de colorare a hărţii, utilizând cel mult 4 culori, astfel încât două ţări cu frontieră comună să fie colorate diferit.

Obs: -harta este furnizata programului cu ajutorul unei matrice An,n.

type vector=array[1..100] of integer;var st:vector; i,j,n,k:integer; as,ev:boolean; a:array[1..20,1..20] of integer;procedure init(k:integer; var st:vector); begin st[k]:=0; end;procedure succesor(var as:boolean; var st:vector; k:integer); begin if st[k]<4 then begin st[k]:=st[k]+1; as:=true; end else as:=false; end;procedure continuare(var ev:boolean; st:vector; k:integer);var i:integer; begin ev:=true; for i:=1 to k-1 do if (st[i]=st[k])and(a[i,k]=1) then ev:=false; end;

Page 13: Metoda backtraking

function solutie(k:integer):boolean; begin solutie :=(k=n); end;procedure tipar;var i:integer; begin for i:= 1 to n do writeln(‘tara =’,i,’;’culoarea=’,st[i]); writeln(‘--------------‘); end; Begin write(‘nr. de tari=’); readln(n); for i:=1 to n do for j:=1 to i-1 do begin write(‘a[‘,i,’,’,j,’]=’);readln(a[i,j]); a[j,i]:=a[i,j]; end; k:=1;init(k,st); while k>0 do begin repeat succesor(as,st,k); if as then continuare(ev,st,k); until (not as) or (as and ev); if as then if solutie (k) then tipar else begin k:=k+1; init(k,st); end else k:=k-1; end;End.

Page 14: Metoda backtraking

Generarea aranjamentelor de n elemente luate câte p ale unui vector Se citesc cele n elemente ale unui vector şi numărul natural p. Să se genereze toate aranjamentele de n elemente luate câte p ale mulţimii {a1,a2,…,an}. Simulaţi executarea algoritmului pentru n=4 şi p=2.

=n!/(n-p)!= 4!/2!=24/2=12(1,2); (1,3); (1;4); (2,1); (2,3); (2,4); (3,1); (3,2); (3,4); (4,1); (4,2),(4,3).type vector=array[1..20] of integer;var x:vector; n,p:integer;procedure solutie;var i:integer ; begin for i:=1 to p do write (x[i],’ ‘) ; end;function continuare (k : integer) : boolean ;var i: integer; begin continuare : =true ; for i: =1 to k-1 do if x [i] = x[k] then continuare: = false ; end ; procedure back (k : integer) ;var i: integer ; begin if (k=p+1) then solutie else for i:=1 to n do begin x[k] : = i; if continuare [k] then back (k+1); end; end;Begin write(‘n=’);readln(n); write(‘p=’);readln(p);back(1); End.

pnA

Page 15: Metoda backtraking

Generarea combinărilor de n elemente luate câte p ale unui vector Se citesc cele n elemente ale unui vector şi numărul natural p. Să se genereze toate combinările de n elemente luate câte

p ale mulţimii {a1,a2,…,an}. Simulaţi executarea algoritmului pentru n=4 şi p=2.

=n! /((n-p)!*p!)= 4!/(2!*2!)=(3*4)/2=6(1,2); (1,3); (1,4);(2,3); (2,4); (3,4).

Obs: -functia de continuare lipseste, deoarece luam elementele in ordine crescatoare.

type vector=array[1..20] of integer;var x:vector; n,p:integer;procedure solutie;var i:integer ; begin for i:=1 to p do write (x[i],’ ‘) ; end;procedure back (k : integer) ;var i: integer ; begin if (k=p+1) then solutie else for i:=x[k-1]+1 to n do begin x[k] : = i; back (k+1); end; end;Begin write(‘n=’);readln(n); write(‘p=’);readln(p);back(1); End.

pnC

Page 16: Metoda backtraking
Page 17: Metoda backtraking

1.Utilizând metoda backtracking se generează permutările cuvântului info. Dacă primele trei soluţii generate sunt: fino, fion, fnio care este cea de-a cincea soluţie? a. foin b. fnoi c. foni d. ifoninfo =>1234 fino=>3124 fion=>3142 varianta corecta: b.fnoi fnio=>3214

fnoi=>3241

2.Câte numere cu exact două cifre pot fi construite folosind doar cifre pare distincte? a. 12 b. 14 c. 20 d. 25

A =5!/(5-2)! =5!/3! =4*5=20 varianta corecta: c.20

3.Un algoritm generează în ordine descrescătoare toate numerele de 5 cifre, fiecare dintre ele având cifrele în ordine strict crescătoare. Ştiind că primele 5 soluţii generate sunt 56789, 46789, 45789, 45689, 45679, precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării. raspuns: 12347; 12346; 12345.

4. Un algoritm generează în ordine descrescătoare, toate numerele de n cifre (n<9), cu cifrele în ordine strict crescătoare, care nu au două cifre pare alăturate. Dacă pentru n=5, primele 5 soluţii generate sunt 56789, 45789, 45679, 45678, 36789, precizaţi care sunt următoarele 3 soluţii generate, în ordinea obţinerii lor. raspuns:35789, 35678, 356789.

5.Generând şirurile de maximum 3 caractere distincte din mulţimea {A,B,C,D,E}, ordonate lexicografic, obţinem succesiv: A, AB, ABC, ABD,…. Ce şir va fi generat imediat după BAE? a. BCA b. CAB c. BC d. BEA 215=> BAE 231=> BCA varianta corecta: a.BCA

25

Page 18: Metoda backtraking

6. Un program citeşte o valoare naturală nenulă impară pentru n şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din n cifre care îndeplinesc următoarele proprietăţi:- încep şi se termină cu 0;- modulul diferenţei între oricare două cifre alăturate dintr-o combinaţie este 1.Astfel, pentru n=5, combinaţiile afişate sunt, în ordine, următoarele: 01010, 01210. Dacă se rulează acest program şi se citeşte pentru n valoarea 7, imediat după combinaţia 0101210 va fi afişată combinaţia: 0121210 b. 0123210 c. 0111210 d. 0121010varianta corecta: d.0121010. 7. Pentru generarea numerelor cu n cifre formate cu elementele mulţimii {0,2,9} se utilizează un algoritm backtracking care, pentru n=2, generează, în ordine, numerele 20,22,29,90,92,99. Dacă n=4 şi se utilizează acelaşi algoritm, care este numărul generat imediat după numărul 2009? a. 2002 b. 2020 c. 2090 d. 2010varianta corecta: b.2020. 8. Pentru generarea în ordine crescătoare a numerelor cu n cifre formate cu elementele mulţimii {0,2,8} se utilizează un algoritm backtracking care, pentru n=2, generează, în ordine, numerele 20,22,28,80,82,88. Dacă n=4 şi se utilizează acelaşi algoritm, precizaţi câte numere generate sunt divizibilecu 100? 8 b. 90 c. 6 d. 102000; 8000; 2800; 8200; 2200; 8800. varianta corecta: c.6

9. În câte dintre permutările elementelor mulţimii {‘I’,’N’,’F’,’O’} vocalele apar pe poziţii consecutive? a. 24 b. 6 c. 12 d. 4IOFN; IONF; FION;NIOF; NFIO; FNIO; OIFN; OINF; FOIN; NOIF; FNOI; NFOI. varianta corecta: c.12

10. Pentru generarea numerelor cu n cifre formate cu elementele mulţimii {0,4,8} se utilizează un algoritm backtracking care, pentru n=2, generează, în ordine, numerele 40,44,48,80,84,88. Dacă n=4 şi se utilizează acelaşi algoritm, care este numărul generat imediat după numărul 4008 ? a. 4040 b. 4004 c. 4080 d. 8004 varianta corecta: a.4040

Page 19: Metoda backtraking

11. Având la dispoziţie cifrele 0, 1 şi 2 putem genera, în ordine crescătoare, numere care au suma cifrelor egală cu 2 astfel încât primele 6 numere generate sunt, în această ordine: 2, 11, 20, 101, 110, 200. Folosind acelaşi algoritm se generează numere cu cifrele 0, 1, 2 şi 3 care au suma cifrelor egală cu 4. Care va fi al 7-lea număr din această generare ? a. 103 b. 301 c. 220 d. 130Sc=4 =>13; 22; 31; 103; 112; 121; 130. varianta corecta: d.130

12. În vederea participării la un concurs, elevii de la liceul sportiv au dat o probă de selecţie, în urma căreia primii 6 au obţinut punctaje egale. În câte moduri poate fi formată echipa selecţionată ştiind că poate avea doar 4 membri, aleşi dintre cei 6, şi că ordinea acestora în cadrul echipei nu contează? a. 24 b. 30 c. 15 d. 4

C = 6!/(4!*2!)= (5*6)/2=15 varianta corecta: c.15.

13. Folosind un algoritm de generare putem obţine numere naturale de k cifre care au suma cifrelor egală cu un număr natural s. Astfel, pentru valorile k=2 şi s=6 se generează, în ordine, numerele: 15, 24, 33, 42, 51, 60. Care va fi al treilea număr generat pentru k=4 şi s=5? a. 1301 b. 1022 c. 2201 d. 10311013; 1031; 1022 varianta corecta: b.1022.

14. Se utilizează un algoritm pentru a genera în ordine lexicografică inversă toate permutările mulţimii {1,2,3,4,5}. Primele patru permutări generate sunt: 54321, 54312, 54231, 54213. A cincea permutare este: a. 53421 b. 54321 c. 54132 d. 54123

varianta corecta: a.53421.

15. Utilizând metoda backtracking se generează toate permutările mulţimii {1,2,3,4}. Dacă primele trei permutări generate sunt, în acestă ordine: 1234, 1243, 1324 precizaţi care este permutarea generată imediat după 3412. a. 3214 b. 3413 c. 4123 d. 3421. varianta corecta: d.3421.

46

Page 20: Metoda backtraking

16. Utilizând metoda backtracking se generează numerele formate din câte 3 cifre distincte din mulţimea {1,3,5,7}. Dacă primele trei numere generate sunt, în acestă ordine: 135, 137, 153 care este cel de-al patrulea număr generat? a. 315 b. 173 c. 157 d. 357.

varianta corecta: c.157.

17. Utilizând metoda backtracking se generează toate cuvintele de câte 3 litere din mulţimea {a,b,c}. Dacă primele patru cuvinte generate sunt, în acestă ordine: aaa, aab, aac, aba, care este cel de-al optulea cuvânt generat? a. acb b. acc c. aca d. bca.aaa, aab, aac, aba, abb, abc, aca, acb.

varianta corecta: a.acb.

18. Se generează în ordine strict crescătoare numerele de câte şase cifre care conţin: cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei ori. Se obţin, în această ordine, numerele: 122333, 123233, 123323, …, 333221. Câte numere generate prin această metodă au prima cifră 1 şi ultima cifră 2? a. 1 b. 3 c. 4 d. 8123332; 132332; 133232; 133322

varianta corecta: c.4.

19. Utilizând metoda backtracking, se generează în ordine lexicografică toate anagramele cuvântului caiet (cuvinte formate din aceleaşi litere, eventual în altă ordine). Câte cuvinte care încep cu litera t vor fi generate? a. 1 b. 6 c. 12 d. 24c a i e t => 1 2 3 4 551234; 51243; 51324; 51342; 51432; 51423 => sunt 6 numere care dupa 5 au cifra 1 =>6*4(cate nr. pot fi puse dupa 5)=24

varianta corecta: d.24.

20. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 6 ca sumă a cel puţin două numere naturale nenule. Termenii fiecărei sume sunt în ordine crescătoare. Soluţiile se generează în ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3, 1+1+4, 1+5, 2+2+2, 2+4 şi 3+3. Se aplică exact aceeaşi metodă pentru scrierea lui 9.Câte soluţii de forma 2+... vor fi generate? a. 2 b. 3 c. 4 d. 5.n=9 => 2+2+2+2+1 2+2+2+3 2+2+5 2+7 varianta corecta : c.4.

Page 21: Metoda backtraking