Scribd
Încărcați
68 vizualizări4 pagini

Domino Backtracking 1

Documentul descrie o problema de backtracking pentru a gasi toate solutiile de aranjare a unor piese de domino intr-un lant de lungime data, fara a roti piesele. Se citeste un numar n de piese de domino si o lungime a a lantului, apoi se parcurge vectorul cu piesele si se verifica daca fiecare piesa poate fi adaugata in lantul curent.

Încărcat de

Bogdy
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca DOCX, PDF, TXT sau citiți online pe Scribd
68 vizualizări4 pagini

Domino Backtracking 1

Documentul descrie o problema de backtracking pentru a gasi toate solutiile de aranjare a unor piese de domino intr-un lant de lungime data, fara a roti piesele. Se citeste un numar n de piese de domino si o lungime a a lantului, apoi se parcurge vectorul cu piesele si se verifica daca fiecare piesa poate fi adaugata in lantul curent.

Încărcat de

Bogdy
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca DOCX, PDF, TXT sau citiți online pe Scribd

Domino – Metoda Backtracking

Se considera n piese de domino citite ca perechi de numere naturale, fiecare pe cate un rand de
intrare. Se citeste apoi un numar natural a.

Sa se afiseze toate solutiile de aranjare a acestor piese intr-un lant domino de lungime a, fara a
roti piesele.

(Un lant domino se alcatuieste din piese domino astfel incat o piesa este urmata de alta a carei prima
jumatate coincide cu jumatatea a doua a piesei curente.)

Ex: 1,2 2,6 6,8

[Link]:

12

13

34

23

35

45

[Link]:

122334

122335

133445

233445
Codul
problemei
#include <fstream>
using namespace std; void afis()
ifstream fin("[Link]"); {
ofstream fout("[Link]"); int i;
struct piesa {int a,b;}; for(i=1;i<=a;i++)
int p[100], x[100],n,a; fout<<d[x[i]].a<<" "<<d[x[i]].b<<"
piesa d[100]; ";
fout<<endl;
void citire() }
{
int i; void back(int k)
fin>>n; {
for(i=1;i<=n;i++) int i;
fin>>d[i].a>>d[i].b; for(i=1;i<=n;i++)
fin>>a; if(!p[i])
} {
x[k]=i; p[i]=1; int main()
if(k==1 || d[x[k- {
1]].b==d[x[k]].a) if(k==a) afis(); citire();
else back(1);
back(k+1); [Link]();
p[i]=0; [Link]();
} return 0;
} }
Explicație

După citirea celor n piese de domino, se parcurge vectorul format din


aceste piese și pentru fiecare piesă în parte se verifică dacă poate fi adăugat în
lanțul de lungime a ( fie daca fie lanțul este gol, fie primul numărul al piesei este
același ca al doilea număr al ultimului domino din lanț). În momentul în care se
formează un lanț de lungime a, acesta se afișează, iar apoi, pe baza unei stive, se
scoate câte o piesă și se adaugă umrătoarea piesă disponibilă, generându-se astfel
toate lanțurile posibile, în ordine screscătoare.

S-ar putea să vă placă și