Download - METODA BACKTRACKING
METODA BACKTRACKING
1.PROBLEME
1. Problema reginelorSă 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ă.
o Recursiv
type vector=array [1..30] of integer;
var x: vector;
n: integer;
procedure solutie;
var i,j : integer;
begin writeln
for i:=1 to n do
begin
for j:=1 to n do
if x[i]=j then write (‘*’)
else write (‘_’);
writeln;
end;
end;
function continuare (k:integer):boolean;
var i:integer;
ok:boolean;
begin
ok:=true;
for i:=1 to k-1 do
if (x[k]=x[i]) or ( abs(x[k] – x[i]) = (k-1)) then ok:=false
continuare:=ok;
end;
procedure back(k:integer);
var i: 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;.
o Iterativ
var solutie: array [1..9] of integer;
n:integer;
function valid (k: integer): boolean;
var i: integer;
begin
valid:=true;
for i:= 1 to k-1 do
if (sol [k] = sol [i]) or (abs(sol [k] – sol [i])=abs(k-1)) then valid:=false
end;
procedure back(k:integer);
var i:integer;
begin
if k=n+1 then begin
for i:=1 to n do
write (sol [i]);writeln;
end
else begin
sol[k]:=0;
while sol [k] < n do
begin
sol [k] :=sol [k] +1;
if valid (k) then back (k+1)
end;
end;
end;
begin
write(‘n’); readln(n);
back(1)
end.
2.Plata unei sume cu bancnote de valori dateSe 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ă.
o Recursiv
const=7;
const a: array[1..n] of integer=(1,5,10,50,100,200,500);
type vector= array [1..n] of integer;
var x:integer;
suma, s: integer;
procedure solutie;
var i: integer;
begin
for i:=1 to n do
if x[i] >0 then write (x[i], ‘bacnote de’, a [i], ‘lei’);
writeln (‘============‘);
end;
function continuare (k:integer): boolean;
begin
continuare:=(x [k]* a [k] + s < suma) and (k<=n);
end;
procedure back (k:integer): integer;
begin
if ( s= suma) then solutie
else begin
x[k]:=1;
while continuare(k) do
begin
x[k]:=x [k]+1
s:=s+x[k]*a[k];
back(k+1);
s:=s-x [k] *a [k];
end;
end;
end;
begin
write (‘suma=‘); readln (suma);
back(1);
readln(1);
end.
3.Problema colorării hărţilorFiind 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.
o Recursiv
const c: array [1..4] of char= (‘G’,’R’,’A’,’V’);
type vector=array [1..50] of integer;
matrice=array [1..50,1..50] of integer;
var a:matrice; x:vector; n:integer;
procedure citire (var n: integer; var a:matrice);
var i,j:integer;
begin
write(‘n=‘);readln(n);
for i:=1 to n do
for j:=1 to n do
begin
write (‘a[‘, i, ‘,’ , j, ‘]=‘); readln (a[i,j] )
end;
end;
procedure solutie;
var i: integer;
begin
for i:=1 to n do
writeln (‘tara’, I, ‘:’, c [x [i]]);
end;
funtion continuare (k: integer): boolean;
var i: integer;
begin
continuare:= true;
for i:=1 to k-1 do
if (a[i,k]=1) and (x[i]=x [k]) then continuare :=false’
end;
procedure back (k:integer);
var i:integer;
begin
if (k=n+1) then solutie
else for i:= 1 to 4 do
begin
x[k]:=1;
if continuare (k) then back (k+1);
end;
end;
begin
citire (n,a);
back(1);
end;.
4.Săritura caluluiSe consideră o tablă de şah nxn şi un cal plasa tî ncolţul din stânga, sus. Se cere să se afişeze un drum al calului pe table de şah, astfel încât să treacă o singură dată prin fiecare pătrat al tablei.
o Recursiv
type vector=array [1..400] of integer;
matrice=array [1..20,1..20] of integer;
coust dx:array [1..8] of integer=(-2,-1,1,2,2,1,-1,-2);
dy:array[1..8] of integer=(-1,-2,-2,-1,1,2,2,1);
var a:matrice; x,y: vector; n:integer;
procedure solutie
var i,j: integer;
begin writeln
for i:=1 to n do
begin
for i:=1 to n do
write (a[I,j], ‘ ‘); writeln;
end;
end;
function continuare (k:integer):boolean;
var ok: boolean;
begin
ok::=true;
if (x [k]<1) or (x [k]>n) or (y [k]<1) or (y [k]k>n) or (a[x[k], y[k]]>0) then ok:= false;
continuare:=ok;
end;
procedure back (k:integer);
var i:integer;
begin
if (k= n*n+1) then solutie
else begin
for i:= 1 to 8 do
begin
x [k]:= x [k-1] +dx [i];
y [k]:= y [k-1] +dy [i] ;
a [x [k],y [k] ]:=k;
if contiuare (k) then begin
back(k+1);
a [x [k], y [k] ]:=0;
end;
end;
end;
end;
begin
write(‘n=‘); readln(n);
x[i]:=1; y[1]:=1; a[1,1]:=1;
back (2);
end.
5.Generarea permutărilor unui vectorSe citesc cele n elemente ale unui vector a de numere întregi. Să se genereze permutările de n elemente ale mulţimii {a1,a2,…,an}. Simulaţi executarea algoritmului pentru n=3.
Recursiv
type vactor=array [1..20] of integer;
var a,x: vector; n:integer;
procedure citire(var n: integer; var a: integer);
var i: integer;
begin
write (‘n=‘); readln(n);
for i:= 1 to n do
begin
write(‘a[‘, i, ‘]=‘); readln (a[i]);
end;
end;
procedure solutie;
var I :integer;
begin
for i := 1 to n do
write (a [x [i] ], ’ ‘); writeln;
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=n+1) then solutie
else for i:= 1 to n do
begin
x[k]:=I;
if continuare (k) then back ( k+1);
end;
end;
begin
citire(n,a);
back(1);
end.
Rezolvare pentru n=3
= 3! = 2 * 3= 6
(1,2,3) (2,1,3) (3,1,2)
(1,3,2) (2,3,1) (3,2,1)
6.Generarea aranjamentelor de n elemente luate câte p ale unui vectorSe 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.
o Recursiv
type vector=array [1..20] of integer;
var x: integer;
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.
Rezolvare pentru n=4 si p=2
= = = = = 12
(1,2) (2,1) (3,1) (4,1)
(1,3) (2,3) (3,2) (4,2)
(1,4) (2,4) (3,4) (4,3)
7.Generarea combinărilor de n elemente luate câte p ale unui vectorSe 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.
o Recursiv
type vector=array [0..20] of integer;var x:vector; n,p: integer;
procedure solutie;var i: integer; begin for i:= 1 to p do write (x[i], ‘ ‘); writeln; 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.
Rezolvare pentru n=4 si p=2
= = = = 6
(1,2) (2,3)
(1,3) (2,4)
(1,4) (3,4)
8.Generarea partiţiilorFie mulţimea A={1,2,…,n}. Se numeşte partiţie a mulţimii A, un set de kn mulţimi care îndeplines ccondiţiile de mai jos:a) A1UA2U…UAk=Ab) AiAj=, i,j{1,2,…,n}
o Iterativ
var sol: array [0..10] of integer;
n,i, j,max: integer;
procedure tipar;
begin
max:=1;
for i:=2 to n do
if max< sol[i] then max:= sol[i];
writeln(‘Partitie’);
for i:=1 to max do
begin
for j:=1 to n do
if sol[j]=1 then write(j, ’ ‘);
writeln;
end;
end;
procedure back (k:integer);
var i, j, maxprec: integer;
begin
if k=n+1 then tipar
else begin
maxprec:=0;
for j:=1 to k-1 do
if maxprec< sol[j] then maxprec:= sol[j];
for i:=1 to maxprec+1 do
begin
sol [k]:=i;
back(k+1)
end;
end;
end;
begin
write(‘n=‘); readln(n);
back(1);
end.
2.GRILE
Varianta 16
Un algoritm generează în ordine crescătoare toate numerele de n cifre, folosind doar cifrele3, 5 şi 7. Dacă pentru n=5, primele 5 soluţii generate sunt 33333, 33335, 33337,33353, 33355, precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării.
Rezolvare:
Ultimele trei solutii generate in ordinea generarii sunt: 77773, 77775, 77777.
Varianta 17
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.
Rezolvare:
Ultimele trei solutii generate in ordinea generarii sunt: 12347, 12346, 12345.
Varianta 19
Un algoritm generează în ordine
crescătoare, toate numerele de n cifre
(n<9), cu cifre distincte,care nu au două cifre pare alăturate. Dacă pentru n=5, primele 5 soluţii generate sunt 10325, 10327, 10329, 10345, 10347, precizaţi care sunt următoarele 3 soluţii generate,în ordinea obţinerii lor.
Rezolvare:
Următoarele 3 soluţii generate în ordinea obţinerii lor sunt: 10349, 10352, 10354.
Varianta 20
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.
Rezolvare:
Următoarele 3 soluţii generate,în ordinea obţinerii lor sunt: 35789, 35689, 35679.
Varianta 21
Următoarele probleme se referă la mulţimea de numere reale M={x1, x2, …, xn} (n>1000).Care dintre acestea, comparativ cu celelalte, admite un algoritm care se încheie după un număr minim de paşi?
Rezolvare:
c. determinarea elementului minim al mulţimii M
Varianta 22
In timpul procesului de generare a permutărilor mulţimii {1,2,…,n} prin metoda backtracking, în tabloul unidimensional x este plasat un element xk (1≤k≤n). Acesta este considerat valid dacă este îndeplinită condiţia:
Rezolvare:
a. xk {x1, x2, …, xk-1}∉
Varianta 32
Î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
Rezolvare:
= = 15
c) 15
Varianta 34
Completarea unui bilet de LOTO presupune colorarea a 6 numere dintre cele 49, înscrise pe bilet. O situaţie statistică pe o anumită perioadă de timp arată că cele mai frecvente
numere care au fost extrase la LOTO sunt: 2, 20, 18, 38, 36, 42, 46, 48. Câte bilete de 6 numere se pot completa folosind doar aceste valori, ştiind că numărul 42 va fi colorat pe fiecare bilet?
a. 21 b. 6! c. 42 d. 56
Rezolvare:
= = 21
a) 21
Varianta 38
Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 9 ca sumă a cel puţin două numere naturale nenule distincte. Termenii fiecărei sume sunt în ordine strict crescătoare. Soluţiile se generează în ordinea: 1+2+6, 1+3+5, 1+8, 2+3+4, 2+7, 3+6 şi 4+5.Se aplică exact aceeaşi metodă pentru scrierea lui 8.Câte soluţii vor fi generate?
a. 3 b. 4 c. 6 d. 5
Rezolvare:
1+2+5
1+3+4
1+7 d) 5
2+6
3+5
Varianta 40
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? (4p.)
a. 2 b. 3 c. 4 d. 5
Rezolvare:
2+2+2+3
2+2+5
2+3+4 c) 4
2+7
Varianta 45
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
Rezolvare:
5. abb
6. abc
7. aca
8. acb
a) acb
Varianta 49
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ă me-todă au prima cifră 1 şi ultima cifră 2?
a. 1 b. 3 c. 4 d. 8
Rezolvare:
123332
132332
133232
133322
c) 4
Variante 54
Utilizând metoda backtracking se generează în ordine lexicografică toate anagramele cuvântului caiet ( cuvinte formate din aceleaşi litere, eventual în altă ordine). Care este a şasea soluţie?
a. catei b. actie c. actei d. catie
Rezolvare:
caiet -> 12345
1. 12345
2. 12354
3. 12435
4. 12453
5. 12534
6. 12543
a) catei
Varianta 74
Prin metoda backtracking se gene-rează toate anagramele (cuvintele obţi-nute prin permutarea literelor )unui cuvânt dat.Ştiind că se aplică această metodă pentru cuvântul solar,precizaţi câte cuvinte se vor genera astfel încât prima şi ultima literă din fiecare cu-vânt generat să fie vocală(sunt consi-derate vocale caracterele a, e, i , o, u)?
a. 24 b. 6 c. 10 d. 12
Rezolvare:
aslro asrlo
arslo arlso
alrso alsro
6*2=12 d) 12
Varianta 69
Construim anagramele unui cuvânt c1c2c3c4 prin generarea în ordine lexicografică a permutărilor indicilor literelor cuvântului şi obţinem c1c2c3c4 c1c2c4c3 c1c3c2c4 … c4c3c1c2 c4c3c2c1. Pentru anagra-mele cuvântului pateu, după şirul paetu, paeut, paute cuvintele imediat următoare sunt:
a. pauet şi ptaeu b. ptaeu şi ptaue
c. pauet şi ptaue d. ptaeu şi patue
Rezolvare:
paute -> 12534
12543 -> paute
13245 -> ptaeu
a) pauet şi ptaeu
Varianta 57
Se utilizează metoda backtracking pentru a genera în ordine lexicografică toate cuvintele de câte patru litere din mulţimea {d,a,n,s}, astfel încât în niciun cuvânt să nu existe două litere alăturate identice. Ştiind că primele trei cuvinte generate sunt, în ordine, adad, adan şi adas, care va fi ultimul cuvânt obţinut?
a. snns b. nsns c. snsn d. dans
Rezolvare:
adad, adam, adas,..., snsn
c) snsn
Varianta 63
Se generează, prin metoda backtracking, toate partiţiile mulţimii A={1,2,3} obţinându-se următoarele soluţii:{1}{2}{3};{1}{2,3};{1,3}{2};{1,2}{3};{1,2,3}. Se observă că dintre acestea prima soluţie e alcătuită din exact trei submulţimi.Dacă se folo-seşte aceeaşi metodă pentru a ge-nera partiţiile mulţimii {1,2,3,4} sta-biliţi câte dintre soluţiile generate vor fi alcătuite din exact trei submulţimi.
a.3 b.12 c. 6 d.5
Rezolvati:
{1,2}{3}{4}; {1}{2,3}{4}; {1}{2}{3,4}
a) 3
Varianta 70
Pentru rezolvarea cărei probleme dintre cele enumerate mai jos se poate utiliza metoda backtracking ?
a. determinarea reuniunii a 3 mulţimi
b. determinarea tuturor divizorilor unui număr din 3 cifre
c. determinarea tuturor elementelor mai mici decât 30000 din şirul lui Fibonacci
d. determinarea tuturor variantelor în care se pot genera steagurile cu 3 culori (din mulţimea:”roşu”, ”galben”, ”albastru” şi ”alb”), având la mijloc culoarea ”galben”
Rezolvare:
d. determinarea tuturor variantelor în care se pot genera steagurile cu 3 culori (din mulţimea:”roşu”, ”galben”, ”albastru” şi ”alb”), având la mijloc culoarea ”galben”
Varianta 58
Se utilizează metoda backtracking pentru a genera în ordine lexicografică toate cuvintele de câte trei litere distincte din mulţimea {d,a,n,s}. Care este cel de-al treilea cuvânt obţinut?
a. ads b. ans c. dan d. and
Rezolare:
1. adn
2. ads
3. ans
b) ans
Varianta 55
Se generează în ordine crescătoare, toate numerele naturale de 5 cifre distincte, care se pot forma cu cifrele 2,3,4,5 şi 6. Să se precizeze numărul generat imediat înaintea şi numărul generat imediat după secvenţa urmă-toare : 34256, 34265, 34526, 34562.
a. 32645 şi 34625 b. 32654 şi 34655
c. 32654 şi 34625 d. 32645 şi 34655
Rezolvare:
34256 -> 23145 => 32654, 34256
34562 -> 23451 => 34561, 34625
c) 32654 si 34625
Realizator: ALBU DANIELA
Clasa : a XI-a B