test Metoda Backtracking

click aici pentru a incepe testul !

Probleme propuse Metoda Backtracking

1. Se citesc de la tastatura două numere naturale n si p (0<p<n<20).
   Să se genereze toate grupările (aranjamentele) de p elemente
   distincte ale mulțimii {1,2,3,....n}, grupări care diferă fie prin
   valorile elementelor, fie prin ordinea lor (Aranjamente de n luate
   câte p).

2. Se citește un număr natural n (n<100). Să se afișeze toate posibilitățile
   de scriere a numărului n ca suma de numere naturale mai mici sau egale cu
   n (partițiile unui număr).

3. Se citesc de la tastatura doua numere naturale nenule n si S (0<n<10,

0<S<70). Sa se genereze toate numerele formate din n cifre distincte
   cu proprietatea ca suma cifrelor este egala S.

4. Sa se genereze toate numerele de n cifre (0<n<9), formate doar din cifre
   pare, cifre aflate in ordine crescatoare.

5. Într-o mare închisa sunt n porturi. Staționarea într-un port se taxeaza
   printr-un cost c. Sa se stabileasca toate voiajele prin p porturi care să
   nu depașească un cost de staționare dat L.

6. Pentru un n dat să se genereze toate șirurile de 2*n+1 termeni nenegativi
    cu proprietatea că x[1]=0, x[2*n+1]=0 si |x[i]-x[i+1]|=1(1<=i<=2*n) .

7. Dându-se 4 cutii și 8 obiecte să se tiparească toate posibilitățile de repartizare a elementelor în cutii a.î. să fie indeplinite condițiile:
      -în cutia 1 se află 1 obiect
      -în cutia 2 se află 1 sau 2 obiecte
      -în cutia 3 se află 2 sau 3 obiecte
      -în cutia 4 se află 3 obiecte

exercitiu rezolvat Metoda Backtracking

Plata unei sume de bani

ENUNT  : Avand la dispozitie n saculeti cu monede S1, S2, .... Sn,
      fiecare saculet Si continand Nri monede de valoare Vi sa se
      afiseze toate modalitatil de aplati o suma data S folosind numai
      monezi din saculeti

 EXEMPLU: Pentru n=3 , Nr=(10,2,5), V=(1,2,5) si S=5 programul va genera
      5 * 1 leu
      3 * 1 leu + 1 * 2 lei
      1 * 1 leu + 2 * 2 lei
      1 * 5 lei

 SOLUTIE:

   I. Solutia x[1]......x[n]. Elementul x[i] va avea ca valoare numarul
      de monede care s-au folosit din saculetul i
  II. x[k] poate avea ca valoare orice valoare din intervalul [0,Nrk].
 III. Valid
    - daca k<n --> suma platita pana la acel moment sa nu depaseasca S
    - daca k=n --> suma platita sa fie egala cu S

 Implementare

#include<iostream>
using namespace std;

char sp[]="   ";

int x[20], n, nrsol=0, nr[20], val[20], sum[20], S;


int Valid(int k)
{sum[k]=sum[k-1]+val[k]*x[k];
 if (sum[k]>S) return 0;
 if (k==n && sum[k]!=S) return 0;
 return 1;
}

void Afisare()
{int i,j;
 cout<<sp;
 for(i=1;i<=n;i++)
   if (x[i]!=0) cout<<x[i]<<"*"<<val[i]<<" lei + ";
 cout<<char(8)<<char(8)<<"   "<<endl;
 nrsol++;
 if (nrsol%22==0) cin.get();
}

void Back()
{int k=1, cand;
 x[1]=-1;
 while (k>0)
    {cand=0;
     while (cand==0 && x[k]<nr[k])
      {x[k]++;
       cand=Valid(k);
      }
     if (cand==0) k--;
     else if (k==n) Afisare();
          else {k=k+1; x[k]=-1;
               }
    }
}


int main()
{int i;
 cout<<endl<<endl<<sp<<"Plata unei sume de bani"<<endl;
 cout<<endl<<sp<<" Numarul tipuri monezi: "; cin>>n;
 cout<<sp<<" Dati suma de plata: "; cin>>S;
 cout<<endl;
 for (i=1;i<=n;i++)
    {cout<<sp<<" Valoare moneda tip "<<i<<": "; cin>>val[i];
     cout<<sp<<" Numar monezi tip "<<i<<"  : "; cin>>nr[i];
    }
 Back();
 cout<<endl<<sp<<"Numar solutii: "<<nrsol;
 return 0;
}

Generarea partitiilor unei multimi

Generarea partitiilor unei multimi

ENUNT  : Fie n numar natural nenul. Scrieti un program de generare a
      tuturor partitiilor multimii {1, 2, 3,..., n}.

 EXEMPLU: Pentru n=3 programul va genera
      {1} {2} {3}
      {1} {2,3}
      {2} {1,3}
      {3} {1,2}
      {1,2,3}


 SOLUTIE: Prin partitie se intelege o descompunere a multimii initiale
      intr-o reuniune de multimi nevide si disjuncte.
      Pentru o multime cu n elemente vor exista maxim n multimi in
      cadrul unei partitii.


   I. Solutia x[1]......x[n]. Fiecare multime din cadrul partitiei va fi
      codificata cu numere de la 1 la n. Elementul x[i] va avea ca valoare
      numarul asociat multimii din care face parte.

      Solutia             Codificare
      {1,2,3}               1 1 1
      {1,2}    {3}        1 1 2
      {1,3} {2}           1 2 1
      {1} {2,3}           1 2 2
      {1} {2} {3}       1 2 3


  II. x[k] poate avea ca valoare orice valoare din intervalul [1,k]. Dar
      cele mai mari doua elemente din cadrul codificarii unei partitii nu
      pot sa difere decat printr-o unitate.

 III. Valid - nu este necesar

 Implementare
#include<iostream>
using namespace std;

char sp[]="   ";

int x[20], n, nrsol=0, max[20], maxim;

int DeterminareMaxim(int k)
{int maxim=0,i;
   for(i=1;i<=k;i++)
     if (x[i]>maxim) maxim=x[i];
 return maxim;
}


void Afisare()
{int i,j;
 cout<<sp;
 maxim=DeterminareMaxim(n);
 for(j=1;j<=maxim;j++)
   {cout<<"{";
    for(i=1;i<=n;i++)
    if (x[i]==j) cout<<i<<" ";
       cout<<"}  ";
   }
 cout<<endl;
 nrsol++;
 if (nrsol%22==0) cin.get();
}

void BackRec(int k)
{int i;
   for(i=1;i<=DeterminareMaxim(k-1)+1;i++)
      { x[k]=i;
       if (k==n) Afisare();
       else BackRec(k+1);
      }
}


int main()
{cout<<endl<<endl<<sp<<"Partiile multimii {1,2,3.....,n}"<<endl;
 cout<<endl<<sp<<" Dati valoarea lui n: "; cin>>n;
 cout<<endl;
 BackRec(1);
 cout<<endl<<sp<<"Numar solutii: "<<nrsol;
 return 0;
}

Aplicatii Metoda Backtracking

PRODUS CARTEZIAN
Se dau n mulţimi, ca cele de mai jos:
 S1={1,2,3,...,w1}
 S2={1,2,3,...,w2}
 ......................... 
Sn={1,2,3,...,wn} 
Se cere să se gnereze produsul lor cartezian.  
Exemplu: pemtru n=3 şi urmăroarele mulţimi 
S1={1,2} w1=2 
S2={1,2,3} w2=3
 S3={1,2} w3=2 
produsul cartezian este: 
S1 xS2 xS3 ={ (1,1,1),(1,1,2),(1,2,1),(1,2,2),(1,3,1),(1,3,2), (2,2,1),(2,1,2),(2,2,1),(2,2,2),(2,3,1),(2,3,2)} 
Prin urmare o soluţie este un şir de n elemente, fiecare element iєSi, cu i=1,n 
Să analizăm exemplul de mai sus: 
1. La pasul k selectăm un element din mulţimea Sk ={1,2,3,...,wk}.
 2. Elementele unei soluţii a produsului cartezian, pot să se repete, pot fi în orice ordine, iar valori străine nu pot apare, deoarece le selectăm doar dintre elementele mulţimii Sk . Prin urmare nu trebuie să impunem condiţii de continuare. 
3. Obţinem o soluţie în momentul în care am completat n elemente în vectorul v. Vom memora numărul de elemente al fiecăerei mulţimi Sk , într-un vector w. Soluţiile le vom construi pe rând în vectorul v

Generarea mulţimilor

                                        A.Generarea produsului cartezian


             Se consideră n mulţimi A1, A2, ... , An de forma {1,2..,an}. Să se genereze produsul  cartezian al acestor mulţimi.
Am considerat mulţimile de forma {1,2..,an} pentru a simplifica problema, în special la partea de citire si afişare, algoritmul de generare rămânând nemodificat.
             Identificăm următoarele particularităţi şi condiţii:

             Fiecare element Xk din vectorul soluţie aparţine unei mulţimi {1,2..,ak}. Aici este o diferenţă faţă de algoritmii anteriori în care fiecare element din soluţie era luat din aceeaşi mulţime şi trebuie să avem grijă la acest fapt când scriem programul.
             Nu există condiţii între elementele vectorului soluţie.
             Obţinem soluţia când s-au generat n valori.


                                       B.Generarea submulţimilor unei mulţimi


              Generarea submulţimilor unei mulţimi A cu n elemente se poate face cu ajutorul algoritmului de generare  a combinărilor, apelându-l repetat cu valorile 1, 2, ..., n pentru a genera submulţimile cu un element, apoi cele cu două elemente, apoi cu 3 elemente etc. 
             Această modalitate de rezolvare este şi mai complicată şi mai puţin eficientă decât următoarea, care se bazează pe generarea produsului cartezian {0,1}n. Această a doua metodă este eficientă deoarece generează 2n soluţii, adică exact atâtea câte submulţimi are o mulţime cu n elemente.
             Aşadar, generăm toate combinaţiile de lungime n cu valorile 0 şi 1. Pentru fiecare combinaţie parcurgem soluţia X şi afişăm elementele din mulţimea A cărora le corespund valori 1 în X.  Astfel, pentru combinaţia 001011 vom afişa elementele de pe poziţiile 3, 5 şi 6 din mulţimea iniţială.


                                      C. Generarea partiţiilor unei mulţimi


             Generăm partiţiilor unei mulţimi presupune împărţirea mulţimii în mulţimi nevide şi disjuncte care reunite să dea întreaga mulţime. Putem, ca şi în cazurile anterioare, să considerăm mulţimea {1,2,…,n}. Construim un vector soluţie în care pentru fiecare element vom trece submulţimea în care îl vom include. Această submulţime mai este numită şi clasă. 
             Algoritmul generează pe rând toate modalităţile de a împărţi elementele mulţimii {1,2,…,n} folosind mai întâi o singură clasă, apoi două, ş.a.m.d. până la n clase.

Generarea aranjamentelor şi a combinărilor

                                                     A.Generarea aranjamentelor
        Generăm aranjamentele unei mulţimi atunci când ne se cer toate modurile de a alege m elemente distincte dintre cele n ale mulţimii (m<n).
        Această problemă se rezolvă foarte uşor folosind metodele de generarea permutărilor. Singurele modificări presupun citirea numărului m, modificarea condiţiei de soluţie, care va fi k=m în loc de k=n şi a numărului de elemente afişate.

                                                     B.Generarea combinărilor
        Generăm combinărilor unei mulţimi presupune o condiţie suplimentară faţă de permutări sau aranjamente. Acest lucru se datorează  faptului că generarea combinărilor presupune alegerea în ordine strict crescătoare a elementelor care compun vectorul soluţie. 
        Astfel, condiţia de continuare, sau de validare a unui element este aceea că el trebuie să fie strict mai mare decât cel plasat anterior. În acest mod asigurăm faptul că elementele nu se vor repeta şi că vor fi generate în ordine strict crescătoare. Trebuie, însă, să avem grijă să nu punem această condiţie si asupra primului element din vectorul soluţie, deoarece el nu are cu cine să fie comparat.  
        O optimizare a algoritmului de generare a combinărilor se poate obţine pornind instrucţiunea for pentru plasarea unui element de la valoare următoare valorii generate anterior. Trebuie să avem grijă la prima poziţie, care nu are element anterior. Am putea iniţializa X0 cu 0.   Astfel nu mai trebuie să verificăm dacă elementul Xk este mai mare ca Xk-1.