Probleme 4
Sa se gaseasca toate posibilitatile de a construi un drapel din 3 culori stiind ca:
a) avem la dispozitie culorile galben, portocaliu, rosu, visiniu, verde, albastru;
b) in mijloc nu pot sa apara culorile galben si visiniu
c) culorile nu se repeta.
Exemplu:
Problema nu are date generale de intrale. Problema ruleaza numai pentru datele date.
O parte din solutie este:
galben rosu portocaliu
galben rosu visiniu
galben rosu verde
galben rosu albastru
galben verde portocaliu
galben verde rosu
galben verde visiniu
galben verde albastru
galben albastru portocaliu
galben albastru rosu
galben albastru visiniu
galben albastru verde
portocaliu galben rosu
portocaliu galben visiniu
portocaliu galben verde
portocaliu galben albastru
portocaliu rosu galben
portocaliu rosu visiniu
Numerotam culorile astfel:
1 - galben
2 - portocaliu
3 - rosu
4 - visiniu
5 - verde
6 - albastru.
Observam ca valoarea minima este 1 si valoarea maxima este 6.
Avem solutie cand numarul de culori din drapel este 3.
X[k] poate fi adaugat la solutie daca:
- nu a mai aparut in drapel
- daca k=2 (se completeaza culoarea din mijloc) aceasta trebuie sa fie diferita de galben sau visiniu.
#include<fstream.h>
#include<math.h>
ofstream f("steag.txt");
int x[50],k,valid;
void posibil(int k,int &valid)
{
valid=1;
if(k==2) if(x[k]==2||x[k]==4) valid=0; /*in mijloc nu poate sa apara galben sau visiniu*/
for(int i=1;i<=k-1;i++) if (x[k]==x[i]) valid=0; /*culorile nu se repeta*/
}
int solutie(int k)
{ /*steagul trebuie sa aiba 3 culori*/
if(k==3) return 1;
else return 0;
}
void afisare(int k)
{
for(int i=1;i<=k;i++)
if(x[i]==1)f<<"galben ";
else if(x[i]==2)f<<"portocaliu ";
else if(x[i]==3)f<<"rosu ";
else if(x[i]==4) f<<"visiniu ";
else if(x[i]==5) f<<"verde ";
else f<<"albastru ";
f<<endl;
}
void back()
{
k=1;
x[k]=0;
while(k>0)
{
valid=0;
while(!valid && x[k]<6) /*6 este codul cel mai mare*/
{
x[k]=x[k]+1;
posibil(k,valid);
}
if(!valid)k--;
else if(solutie(k)) afisare(k);
else {
k++;
x[k]=0;
}
}
}
void main()
{
back();
f.close();
}
Se citeste de la tastatura un cuvant. Sa se afiseze toate anagramarile cuvantului.
Pentru backtracking trebuie sa folosim elemente consecutive, prin urmare vom folosii indicii elementelor din vector si vom codifica elementele cu acesti indici.
Prin urmare, x[k] reprezinta elementul aflat pe poztia x[k] in sir si in acelasi timp, elementul aflat pe pozitia k in vectorul solutie.
Problema se rezuma la problema de generare a permutarilor diferenta fiind doar la afisare cand afisam elementele din sir aflate pe pozitiile x[i], i=1..n.
Exemplu:
s="abcd".
Se va afisa:
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
Avem in vedere ca elementele din sir ocupa pozitiile 0...n-1 unde n este lungimea sirului.
Atunci cand lucram cu siruri trebuie sa introducem biblioteca string.h.
Datorita faptului ca primul element din sir se gaseste pe pozitia 0 inseamna ca elementul minim are valoarea 0. Elementul maxim este n-1 deoarece in sirul de caractere ultima pozitie ocupata este n-1.
Observatie: A nu se face confuzie intre vectorul solutie si sirul de caractere.
#include<fstream.h>
#include<string.h>
ofstream f("cuvant.txt");
int x[50],k,valid,n;
char s[50];
void citire() /*citim datele de intrare*/
{cout<<"sir=";cin>>s;
}
void posibil(int k,int &valid) /*elementele nu se repeta*/
{
valid=1;
for(int i=1;i<=k-1;i++) if (x[k]==x[i]) valid=0;
}
int solutie(int k) /*avem solutie cand cuvantul anagramat are un numar de caractere ca si cuvantul de baza*/
{
if(k==n) return 1;
else return 0;
}
void afisare(int k)
{
/*Afisam solutia. s[x[i]] - elementul din sirul de caractere aflat pe pozitia x[i]*/
for(int i=1;i<=k;i++)
f<<s[x[i]];
f<<endl;
}
void back()
{
k=1;
x[k]=-1;/*valoarea minima=0 - 1*/
while(k>0)
{
valid=0;
while(!valid && x[k]<n-1)
{
x[k]=x[k]+1;
posibil(k,valid);
}
if(!valid)k--;
else if(solutie(k)) afisare(k);
else {
k++;
x[k]=-1;/*valoarea minima=0 - 1*/
}
}
}
void main()
{
citire();
n=strlen(s);
back();
f.close();
}
Pe un CD trebuie inscriptionate n melodii numerotate 1...n. Sa se afiseze toate modalitatile de inscriptionare a melodiilor pe CD stiind ca:
- melodiile nu se repeta
- melodia 2 nu este inscriptionata inate de melodia 1.
Exemplu:
pentru n=4 se va afisa:
1234
1243
1324
1342
1423
1432
3124
3142
3412
4123
4132
4312
Observam ca:
- valoarea minima este 1 si valoarea maxima este n.
- trebuie respectate conditiile din enunt. Vom exclude solutiile care nu sunt bune prin conditiile puse in functia posibil.
- avem solutie cand s-au inscriptionat toate cele n melodii.
#include<fstream.h>
#include<string.h>
ofstream f("muzica.txt");
int x[50],k,valid,n;
void citire()
{cout<<"n=";cin>>n;
}
void posibil(int k,int &valid)
{
valid=1;
for(int i=1;i<=k-1;i++) if (x[k]==x[i]) valid=0; /*melodiile nu se repeta*/
if(x[k]==1) for(i=1;i<=k-1;i++) if(x[i]==2) valid=0;/*melodia 2 nu poate sa apara inainte melodii 1*/
}
int solutie(int k)
{ /*avem solutia cand se inscriptioneaza toate cele n melodii*/
if(k==n) return 1;
else return 0;
}
void afisare(int k)
{ /*afisam solutia*/
for(int i=1;i<=k;i++)
f<<x[i];
f<<endl;
}
void back()
{
k=1;
x[k]=0;
while(k>0)
{
valid=0;
while(!valid && x[k]<n)
{
x[k]=x[k]+1;
posibil(k,valid);
}
if(!valid)k--;
else if(solutie(k)) afisare(k);
else {
k++;
x[k]=0;
}
}
}
void main()
{
citire();
back();
f.close();
}
