Probleme 1

Se dau n multimi fiecare multime cu cate m elemente. Sa se afiseze elementele produsului cartezian.

Exemplu:

n=3 m=4

solutii

1 1 1

1 1 2

1 1 3

1 1 4

1 2 1

1 2 2

.........

Prin urmare, valoarea minima este 1, valoarea maxima eate 4.

Observam ca avem solutie cand numarul de elemente din vectorul solutie este n.

Putem adauga un element in solutie indiferent ce elemente au fost depuse inainte (valid=1).

#include<fstream.h>
ofstream f("cart.txt");
int x[50],k,valid,n,m;
void citire()//citirea datelor de intrare
{
cout<<"n=";cin>>n;
cout<<"m=";cin>>m;
}
void posibil(int k,int &valid)
{ /*nu exista conditii de continuitate. Orice element din multimea {1...m} poate fi adaugat la solutie*/
valid=1;
}
int solutie(int k)
{ /*avem solutie daca numarul de elemente din solutie este egal cu numarul de multimi*/
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]<m)
    {
    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();
}

Se dau n obiecte numerotate de la 1...n. Sa se afiseze toate posibilitatile de a aseza obiectele. (Permutari)

Exemplu:

n=3

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Observam ca valoarea minima este 1, valoarea maxima este n.

Avem solutie cand numarul de elemente este egal cu numarul de obiecte.

Adaugam un element la solutie daca elementul respectiv nu a mai fost adaugat la solutie (conditia de nerepetitie a elementelor)

#include<fstream.h>
ofstream f("perm.txt");
int x[50],k,valid,n,m;
void citire() /*datele de intrare*/
{
cout<<"n=";cin>>n;
}
void posibil(int k,int &valid)
{
valid=1;

/*verificam daca x[k] a mai fost depus in solutie*/
for(int i=1;i<=k-1;i++)
    if(x[i]==x[k]) valid=0;
}
int solutie(int k)
{

/*avem solutie daca numarul de elemente din solutie este egal cu n*/
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();
}

Se dau n obiecte. Sa se afiseze toate posibilitatile de a aranja cate m dintre cele n obiecte. (Aranjamente)

Exemplu:

n=4; m=3;

Solutie:

1 2 3
1 2 4
1 3 2
1 3 4
1 4 2
1 4 3
2 1 3
2 1 4
2 3 1
2 3 4
2 4 1
2 4 3
3 1 2
3 1 4
3 2 1
3 2 4
3 4 1
3 4 2
4 1 2
4 1 3
4 2 1
4 2 3
4 3 1
4 3 2

Observam ca elementul minim este 1, elementul maxim este n.

Avem solutie cand numarul de elemente din solutie este m.

Elementele din solutie nu se repeta.

#include<fstream.h>
ofstream f("aranj.txt");
int x[50],k,valid,n,m;
void citire()
{/*citim datele de intrare*/
cout<<"n=";cin>>n;
cout<<"m=";cin>>m;
}
void posibil(int k,int &valid)
{ /*elementele din solutie nu trebuie sa se repete*/
valid=1;
for(int i=1;i<=k-1;i++)
    if(x[i]==x[k]) valid=0;
}
int solutie(int k)
{
if(k==m)return 1;
    else return 0;
}
void afisare(int k)
{
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();
}

Sa se afiseze toate solutiile de a aseza m dintre cele n obiecte date astfel incat multimile de obiecte sa nu se repete. (Combinari)

Exemplu:

n=4; m=3;

Solutii:

1 2 3
1 2 4
1 3 4
2 3 4

Observam ca valoarea minima este 1; valoarea maxima este n.

Avem solutie cand numarul de elemente din solutie este m.

Elementele din solutie nu se repeta. Pentru a nu se repeta nici multimile de elemente din solutie, elementele trebuie sa fie puse in ordine crescatoare/descrescatoare.

#include<fstream.h>
ofstream f("comb.txt");
int x[50],k,valid,n,m;
void citire()
{
cout<<"n=";cin>>n;
cout<<"m=";cin>>m;
}
void posibil(int k,int &valid)
{
valid=1;

/*elementele nu se repeta*/
for(int i=1;i<=k-1;i++)
    if(x[i]==x[k]) valid=0;

/*elementele trebuie puse in ordine crescatoare*/
if(k>1) if(x[k]<x[k-1]) valid=0;
}
int solutie(int k)
{ /*avem solutie cand am depus m dintre cele n elemente*/
if(k==m)return 1;
    else return 0;
}
void afisare(int k)
{
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();
}