Probleme 3

Variabila nr din programele de mai jos nu are nici o finalitate (nu se afiseaza si nu influenteaza executia programului). Modificati programele astfel incat sa o folositi intr-un mod util. Ce utilitate i-ati dat?

Sa se scrie un numar n ca suma de numere naturale.

Exemplu:

pentru n=7 se va afisa

1 1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 2 1
1 1 1 1 3
1 1 1 2 1 1
1 1 1 2 2
1 1 1 3 1
1 1 1 4
1 1 2 1 1 1
1 1 2 1 2
1 1 2 2 1
1 1 2 3
1 1 3 1 1
1 1 3 2
1 1 4 1
1 1 5
1 2 1 1 1 1
1 2 1 1 2
1 2 1 2 1
1 2 1 3
1 2 2 1 1
1 2 2 2
1 2 3 1
1 2 4
......

Observam ca numarul minim este 1 si numarul maxim este n.
Problema poate fi imbunatatita astfel incat multimile de solutii sa nu se repete.
Avem solutie daca suma numerelor din vectorul solutie este egal cu n.
Putem adauga o valoare in vectorul solutie daca si numai daca prin adaugare suma valorilor din vectorul solutie nu depaseste n.

#include<fstream.h>
#include<math.h>
ofstream f("suma.txt");
int x[50],k,valid,n,m,nr;
void citire()
{
cout<<"n=";cin>>n;
}
void posibil(int k,int &valid)
{ /*x[k] poate fi adaugata in vectorul solutie daca prin adaugarea ei nu suma elementelor din vectorul solutie nu depaseste n*/
valid=1;
int s=0;
for(int i=1;i<=k;i++) s=s+x[i];
if(s>n) valid=0;
}
int solutie(int k) /*avem solutie daca suma elementelor din vectorul solutie este egala cu n*/
{int s=0;
for(int i=1;i<=k;i++) s=s+x[i];
if(s==n) return 1;
    else return 0;
}
void afisare(int k) /*afisam elementele din vectorul solutie*/
{nr++;
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();
nr=0;
back();
f.close();
}

Sa se afiseze un numar n ca suma de m numere naturale.

Exemplu:

pentru n=6 si m=3 se afiseaza:

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

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

X[k] poate fi adaugat la solutie daca suma elementelor din vectorul solutie nu depaseste n.

Avem solutie daca suma elementelor din vecotorul solutie este n si numarul de elemente din solutie este m.

#include<fstream.h>
#include<math.h>
ofstream f("suma1.txt");
int x[50],k,valid,n,m,nr;
void citire()
{/*citim datele de intrare*/
cout<<"n=";cin>>n;
cout<<"m=";cin>>m;
}
void posibil(int k,int &valid)
{ /*x[k] poate face parte din vectorul solutie daca prin adaugarea lui suma elementelor din vector nu depaseste n*/
valid=1;
int s=0;
for(int i=1;i<=k;i++) s=s+x[i];
if(s>n) valid=0;
}
int solutie(int k)
{int s=0; /*avem solutie daca suma elementelor din vectorul solutie este n si numaul de elemente din vectorul solutie este m*/
for(int i=1;i<=k;i++) s=s+x[i];
if(s==n&&k==m) return 1;
    else return 0;
}
void afisare(int k)
{nr++;
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();
nr=0;
back();
f.close();
}