Problema magazinului cu 10 raioane

Negru Alin

clasa a XI-a B

Enuntul problemei

• Mixt este numele unui magazin cu urmatoarele caracteristici:

-la etajul unu are 10 raioane cu pantofi-la etajul doi are 10 raioane cu ciorapi-la etajul trei are 10 raioane cu pantaloni-la etajul patru are 10 raioane cu camasi-la etajul cinci are 10 raioane cu cravate

Exemplu Presupunand ca dorim sa

ne imbracam de la acest magazin astfel incat hainele sa se asorteze, avem mai multe modalitati de a ne imbraca.

et.1 1 2 3 4 5 6 7 8 9 10 et.2 1 2 3 4 5 6 7 8 9 10 et.3 1 2 3 4 5 6 7 8 9 10 et.4 1 2 3 4 5 6 7 8 9 10 et.5 1 2 3 4 5 6 7 8 9 10 Se va afisa intr-o stiva

numarul raionului de la fiecare etaj de la care am cumparat pentru a ne asorta;

. 2 4 6 8 2

et.1 et.2 et.3 et.4 et.5

Algoritmul de rezolvare

Deoarece solutia are mai multe componente, magazinul are mai multe etaje, putem folosi metoda BACKTRACKING.

Pentru rezolvare vom folosi variabilele: k - va reprezenta o variabila intreaga care reprezinta etajul la care

ne gasim; st – un vector care are nu mai mult de 5 componente intregi, adica

numarul de etaje pe care il are magazinul cu proprietatea ca st[k] este numarul raionului;

as- primeste valoarea “true” daca pe etajul K mai sunt raioane nevizitate si “false” in caz contrar;

ev – o variabila booleana care primeste valoarea “true” daca ce este la raionul st[k] ne convine si “false” daca nu ne convine;

Programul in Pascalprogram raioane;type stiva=array[1..100] of integer;var st:stiva; k,n,e:integer; {n-repr. numarul raioanelor iar “e”-repr. numarul etajelor} ev,as:boolean; procedure init(k:integer;var st:stiva);begin st[k]:=0;end;procedure succ(var as:boolean; var st:stiva; k:integer);begin if st[k]<n then begin as:=true; st[k]:=st[k]+1; end else as:=false;end;procedure valid(var ev:boolean; st:stiva; k:integer);begin ev:=true;end;

Continuare function solutie(k:integer):boolean; begin solutie:=(k=e); end; procedure tipar; var i:integer; begin for i:=1 to e do write(st[i]:4); end; BEGIN write(‘cate raioane avem?’);readln(n); write(‘cate etaje avem?’);readln(e); k:=1; init(k,st); while k>0 do begin repeat succesor(as,st,k); if as then valid(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; END.