Probleme 5
Dintr-o cusca trebuie scosi n lei si m tigrii. Sa se afiseze toate posibilitatile de a scoate din cusca animalele astfel incat sa nu iasa 2 tigrii unul dupa altul (numarul de tigrii<=numarul de lei).
Exemplu:
leu leu leu tigru leu tigru
leu leu tigru leu leu tigru
leu leu tigru leu tigru leu
leu tigru leu leu leu tigru
leu tigru leu leu tigru leu
leu tigru leu tigru leu leu
tigru leu leu leu leu tigru
tigru leu leu leu tigru leu
tigru leu leu tigru leu leu
tigru leu tigru leu leu leu
O sa codificam leii cu 0 si tigrii cu 1. Aceasta codificare nu e unica, fiecare programator poate sa-si faca propria-i codificare.
Obsevam ca valoarea minima este 0 si valoarea maxima este 1.
Avem solutie cand am scos din cusca toti leii si toti tigrii.
In functia posbil vom elimina solutiile in care 2 tigrii pot iesii unul dupa altul. Din cusca nu pot iesi mai multi tigrii sau lei decat exista.
#include<fstream.h>
#include<stdlib.h>
ofstream f("leitig.txt");
int x[50],k,valid,n,m;
void citire() /*citim datele de intrare*/
{cout<<"n=";cin>>n;
cout<<"m=";cin>>m;
if(m>n) {cout<<"imposibil";exit(0);}
}
void posibil(int k,int &valid)
{
valid=1;
/*numaram leii si tigrii din solutie*/
int lei=0;
int tig=0;
for (int i=1;i<=k;i++)
if(x[i]==0)lei++;
else tig++;
if(lei>n||tig>m)valid=0; /*nu putem scoate din cusca mai mult de n lei sau mai mult de m tigrii*/
if(x[k]==1&&x[k-1]==1) valid=0; /*nu putem scoate din cusca 2 tigrii unul dupa altul*/
}
int solutie(int k)
{ /*avem solutie daca am scos din cusca n lei si m tigrii*/
int lei=0;
int tig=0;
for (int i=1;i<=k;i++)
if(x[i]==0)lei++;
else tig++;
if(lei==n&&tig==m)return 1;
else return 0;
}
void afisare(int k)
{/*Afisam solutia*/
for(int i=1;i<=k;i++)
if(x[i]==0) f<<"leu ";
else f<<"tigru ";
f<<endl;
}
void back()
{
k=1;
x[k]=-1;/*initializam x[k] cu valoarea minima - 1*/
while(k>0)
{
valid=0;
while(!valid && x[k]<1)
{
x[k]=x[k]+1;
posibil(k,valid);
}
if(!valid)k--;
else if(solutie(k)) afisare(k);
else {
k++;
x[k]=-1;/*initializam pe x[k] cu valoarea minima -1*/
}
}
}
void main()
{
citire();
back();
f.close();
}
Sa se afiseze toate posibilitatile de a inchide n paranteze corect.
Exemplu:
Pentru n=6 se va afisa:
((()))
(()())
(())()
()(())
()()()
Vom codifica cu 0 parantezele deschis si cu 1 parantezele inchise.
Observam ca valoarea minima este 0 si valoarea maxima este 1.
Avem solutie cand am inchis corect cele n/2 paranteze deschise si inchise.
Pentru a adauga un element la solutie avem urmatoarele restrictii:
- sirul de paranteze nu poate sa inceapa cu paranteza inchisa
- numarul de paranteze inchise nu poate fi mai mare ca numarul de paranteze deschise
- nu putem scrie mai multe de n/2 paranteze inchise sau paranteze deschise.
#include<fstream.h>
#include<stdlib.h>
ofstream f("parant.txt");
int x[50],k,valid,n,m;
void citire()
{cout<<"n=";cin>>n;
}
void posibil(int k,int &valid)
{
valid=1;
int pi=0;
int pd=0;
for (int i=1;i<=k;i++)
if(x[i]==0)pd++;
else pi++;
if(pd>n/2||pi>n/2)valid=0;/*nu pot sa apara in solutie mai mult de n/2 paranteze deschise sau inchise*/
if(k==1&&x[k]==1)valid=0; /*prima paranteza din sir nu poate fi paranteza inchisa*/
if(pi>pd)valid=0;/*nu pot sa apara in sir mai multe paranteze inchise decat deschise*/
}
int solutie(int k)
{/*Avem solutie cand avem in sir n/2 paranteze inchise si n/2 paranteze deschise*/
int pd=0;
int pi=0;
for (int i=1;i<=k;i++)
if(x[i]==0)pd++;
else pi++;
if(pd==n/2&&pi==n/2)return 1;
else return 0;
}
void afisare(int k)
{/*afisam solutia*/
for(int i=1;i<=k;i++)
if(x[i]==0) f<<"(";
else f<<")";
f<<endl;
}
void back()
{
k=1;
x[k]=-1;/*initializam x[k] cu valoarea minima-1*/
while(k>0)
{
valid=0;
while(!valid && x[k]<1)
{
x[k]=x[k]+1;
posibil(k,valid);
}
if(!valid)k--;
else if(solutie(k)) afisare(k);
else {
k++;
x[k]=-1;/*initializam elementul curent din solutie cu valoarea minima-1*/
}
}
}
void main()
{
citire();
back();
f.close();
}
Pentru n cuburi se cunosc dimensiunea laturii si culoarea.
Sa se afiseze toate posibilitatile de a construi turnuri din catem cuburi stiind ca:
- doua cuburi de aceasi culoare nu pot fi puse unul langa altul
- un cub cu latura mai mare nu poate fi pus peste un cub cu latura mai mica.
Exemplu:
n=4, m=2
Se vor citi in ordine dimensiunea laturii si culoarea
1: 4 rosu
2: 3 galben
3: 2 rosu
4: 1 verde.
Se va afisa:
1(4 rosu) 2(3 galben)
1(4 rosu) 4(1 verde)
2(3 galben) 3(2 rosu)
2(3 galben) 4(1 verde)
3(2 rosu) 4(1 verde)
Datele afisare au forma:
numarul cubului de la baza(dimensiune culoare) numarul cubului de deasupra (dimensiune culoare)
Observam ca: minimul=1 maximul=n.
Avem solutie cand asezam in turn m cuburi.
In functia posibil tinem cont de conditiile impuse in problema.
#include<fstream.h>
#include<stdio.h>
#include<string.h>
#include<iostream.h>
ofstream f("cuburi.txt");
int x[50],k,valid,n,m;
int dim[50];char cul[50][20];
void citire() /*citim datele de intrare*/
{cout<<"n=";cin>>n;
for(int i=1;i<=n;i++)
{ cout<<"dimensiunea laturii pentru cubul ",i,":";cin>>dim[i];
cout<<"culoarea cubului ",i,":";gets(cul[i]);
}
cout<<"m=";cin>>m;
}
void posibil(int k,int &valid)
{
valid=1;
for (int i=1;i<k;i++) if(x[i]==x[k])valid=0; /*acelasi cub nu poate fi pus in turn de doua ori*/
if(k>1)if(strcmp(cul[x[k-1]],cul[x[k]])==0) valid=0;/*doua cuburi alaturate nu pot avea aceiasi culoare*/
if(k>1)if(dim[x[k-1]]<dim[x[k]]) valid=0;/*un cub cu latura mai mare nu poate fi pus peste un cub cu latura mai mica*/
}
int solutie(int k)
{/*avem solutie cand am reusit sa asezam in turn m cuburi*/
if(k==m)return 1;
else return 0;
}
void afisare(int k)
{/*afisam solutia specificand pentru fiecare cub dimensiunea laturii si culoare*/
for(int i=1;i<=k;i++)
f<<x[i]<<"("<<dim[x[i]]<<" "<<cul[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();
}
Sa se afiseze toate numerele cu cel mult n cifre care indeplinesc conditiile:
- au numai cifre pare
- cifrele nu se repeta.
Exemplu:
Pentru n=4 se va afisa:
2
20
204
2046
2048
206
2064
2068
208
2084
2086
24
240
2406
2408
246
2460
2468
248
2480
2486
26
.....
Observam ca:
- valoarea minima este 0 si valoarea maxima este 8 (pentru cifrele unui numar este 9). Voi alege varianta cu valoarea maxima 9 desi recomand, ca in acest caz sa se tina cont de valoarea maxima;
- dupa afisarea unei solutii adaugarea de elemente la solutia deja construita continua
- elementele care fac parte din solutie respecta conditiile din problema fapt ce se trateaza in functia posibil
- avem solutie daca numarul de elemente din solutie este cel mult n.
#include<fstream.h>
#include<stdio.h>
#include<string.h>
#include<iostream.h>
ofstream f("numere.txt");
int x[50],k,valid,n,m;
int dim[50];char cul[50][20];
void citire() /*citim numarul maxim de cifre pe care trebuie sa-l contina numarul*/
{cout<<"n=";cin>>n;
}
void posibil(int k,int &valid)
{
valid=1;
if(k==1&&x[k]==0)valid=0; /*un numar nu poate incepe cu 0*/
for(int i=1;i<=k-1;i++)if(x[i]==x[k])valid=0; /*cifrele trebuie sa nu se repete*/
if(x[k]%2!=0)valid=0;/*cifrele trebuie sa fie pare*/
}
int solutie(int k)
{/*avem solutie daca am depus in vectorul solutie cel mult n cifre*/
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]=-1;/*cea mai mica cifra este 0; initializam x[k] cu valoarea minima-1*/
while(k>0)
{
valid=0;
while(!valid && x[k]<9) /*cea mai mare cifra este 9 (recomand inlocuirea lui 9, in aceasta problema, cu 8 deoarece 8 este ultima cifra para*/
{
x[k]=x[k]+1;
posibil(k,valid);
}
if(!valid)k--;
else if(solutie(k)) {afisare(k);k++;x[k]=-1;} /*dupa ce se afiseaza o solutie se trece la urmatoarea pastradu-se ca baza solutia precedenta*/
else {
k++;
x[k]=-1;/*initializam valoarea x[k] cu valoarea minima-1*/
}
}
}
void main()
{
citire();
back();
f.close();
}
