Solutia I. Hotul are un rucsac cu care poate cara o greutate maxima G. Exista n obiecte carora li se cunoaste greutatea si valoarea. Sa se determine obiectele de valoare maxima <=G.

#include<iostream>
#include<fstream>
using namespace std;
int n,i,G[100],V[100],S[100],REZ[100];
int greutate,vmax;
void afis(int n, int s, int v)
{int k;
for (k=1;k<=n;k++)
cout<<S[k]<<" ";
cout<<"--"<<s<<"--"<<v<<endl;
}

void afiseaza ()
{
for (i=1;i<=n;i++)
if (REZ[i]!=0)
cout<<REZ[i]<<" ";
cout<<" ->> "<<vmax<<endl;
}

void back(int i, int s, int v)
{
int j,k;
for (j=0;j<=1;j++)
{
S[i]=j;
s=s+j*G[i];
v=v+j*V[i];
if (i==n)
{
afis(i,s,v);
if (s<=greutate)
if (v>vmax)
for (k=1;k<=n;k++)
{
REZ[k]=S[k]*V[k];
vmax=v;
}
}
else
if(s<greutate) back(i+1,s,v);
}
}

int main()
{
ifstream fin("rucsac.in");
fin>>n>>greutate;
vmax=-1;
for (i=1;i<=n;i++)
fin>>G[i]>>V[i];
back(1,0,0);
afiseaza();
return 0;
}

Fisier

6 10
3 7
3 4
1 2
1 9
2 4
1 5

Solutia II. Hotul are un rucsac cu care poate cara o greutate maxima G. Exista n obiecte carora li se cunoaste greutatea si valoarea. Sa se determine obiectele de valoare maxima <=G. 

#include<iostream>
#include<fstream>
using namespace std;
int main()
{
int val=0,gr=0,j,V[100],G[100],i,n,greutate,p;
ifstream fin("rucsac.in");
cin>>n>>greutate;
for(i=1;i<=n;i++)
    cin>>G[i]>>V[i];

for(i=1;i<=n;i++)
{    for(j=i+1;j<=n;j++)
        {if(V[j]>V[i])
            {swap(G[i],G[j]);
            swap(V[i],V[j]);}
        if(V[j]==V[i])
            if(G[j]<G[i])
                {swap(G[i],G[j]);
                swap(V[i],V[j]);}
        }
}
      
for(j=1;j<=n;j++)
{
gr=gr+G[j];
if(gr>greutate)
    p=j;
}

for(i=1;i<p;i++)
{val=val+V[i];
cout<<G[i]<<" "<<V[i]<<endl;
}

cout<<"Valoare maxima: "<<val;
return 0;
}

Fisier

6 10
3 7
3 4
1 2
1 9
2 4
1 5

Suma de bani. (bancnotele trebuie sa fie in ordine crescatoare)

#include<iostream>
using namespace std;
int b[100],x[100],nr=0,n,f[100]={0},minim=INT_MAX,mi;

void afisare(int n)
{int i;
for(i=1;i<=n;i++)
    if(x[i])
        cout<<x[i]<<"*"<<b[i]<<" ";
cout<<endl;
nr++;}

int suma(int x[], int n)
{int i,s=0;
for(i=1;i<=n;i++)
    s=s+x[i];
return s;
}

void back(int i,int s,int nrb)
{int j;
if(i==n)
    {if(s%b[i]==0)
        {x[i]=s/b[i];
        afisare(i);
        if(nrb+j<minim)
            {minim=nrb+j;mi=i;
        for(int k=1;k<=i;k++)
            f[k]=x[k];}}
    }
    else{
        for(j=0;j<=s/b[i];j++)
            {x[i]=j;
            if(s==j*b[i])
                {afisare(i);
                if(nrb+j<minim)
                    {minim=nrb+j;mi=i;
                for(int k=1;k<=i;k++)
                    f[k]=x[k];}}
            else back(i+1,s-j*b[i],nrb+j);
            }
        }
    }

int main()
{int i,j,s,nrb=0;
cin>>s>>n;
for(i=1;i<=n;i++)
    cin>>b[i];
back(1,s,0);
cout<<endl<<nr<<" solutii"<<endl;
for(j=1;j<=mi;j++)
    if(f[j])
        cout<<f[j]<<"*"<<b[j]<<" ";
}

Sa se afiseze toate sirurile crescatoare care incep cu n si se termina cu n+k.

#include<iostream>
using namespace std;
int x[100],n,k,nr=0;

int afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;
nr++;}

void back(int i)
{int j;
for(j=x[i-1]+1;j<=n+k;j++)
{x[i]=j;
    if(j==n+k)
    afisare(i);
    else back(i+1);
}
}

int main()
{cin>>n>>k;
x[1]=n;
back(2);
}

Sa se afiseze toate submultimile unei multimi care au suma elementelor egala cu o suma data.

#include <iostream>
#include <ctime>
using namespace std;
int x[100],n,s,a[100];

void afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<a[x[i]]<<"+";
cout<<"\b ";
cout<<endl;
}

void back(int i, int s)
{int j,sr;
for(j=x[i-1]+1;j<=n;j++)
{x[i]=j;
sr=s-a[x[i]];
    if(sr==0)
        afisare(i);
    else if(sr)
        back(i+1,sr);
}
}

int main()
{int i;
cout<<"n=";cin>>n;
cout<<"s=";cin>>s;
for(i=1;i<=n;i++)
    cin>>a[i];
back(1,s);
}

Bancnote

#include<iostream>
using namespace std;
int b[100],x[100],nr=0,n;

void afisare(int n)
{int i;
for(i=1;i<=n;i++)
    if(x[i])
        cout<<x[i]<<"*"<<b[i]<<" ";
cout<<endl;
nr++;}

void back(int i,int s)
{int j;
if(i==n)
    {if(s%b[i]==0)
        {x[i]=s/b[i];
        afisare(i);}
    }
    else{
        for(j=0;j<=s/b[i];j++)
            {x[i]=j;
            if(s==j*b[i])
                afisare(i);
            else back(i+1,s-j*b[i]);
            }
        }
    }


int main()
{int i,j,s;
cin>>s>>n;
for(i=1;i<=n;i++)
    cin>>b[i];
back(1,s);
cout<<endl<<nr<<" solutii";
}

Sa se afiseze toate descompunerile unui numar in suma de cifre nenule distincte (partitiile numarului).

#include<iostream>
using namespace std;
int x[100],n;

int afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<"+";
cout<<"\b ";
cout<<endl;}

int verif(int i)
{if(i>1 && x[i]<x[i-1])
    return 0;
return 1;}

void back(int i,int s)
{int j;
for(j=1;j<=s;j++)
{x[i]=j;
    if(x[i]==s)
        afisare(i);
    else back(i+1,s-x[i]);
}
}
       
int main()
{cin>>n;
back(1,n);
}

Ordonate strict crescator

#include<iostream>
using namespace std;
int x[100]={0},n;

int afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<"+";
cout<<"\b ";
cout<<endl;}

int verif(int i)
{if(i>1 && x[i]<x[i-1])
    return 0;
return 1;}

void back(int i,int s)
{int j;
for(j=x[i-1]+1;j<=s;j++)
{x[i]=j;
    if(x[i]==s)
        afisare(i);
    else back(i+1,s-x[i]);
}
}
       
int main()
{cin>>n;
back(1,n);
}

Ordonate crescator (< sau =)

#include<iostream>
using namespace std;
int x[100]={0},n;

int afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<"+";
cout<<"\b ";
cout<<endl;}

int verif(int i)
{if(i>1 && x[i]<x[i-1])
    return 0;
return 1;}

void back(int i,int s)
{int j;
for(j=x[i-1];j<=s;j++)
{x[i]=j;
    if(x[i]==s)
        afisare(i);
    else back(i+1,s-x[i]);
}
}
       
int main()
{cin>>n;
x[0]=1;
back(1,n);
}

1. Fazan

#include<iostream>
using namespace std;
int n,p,x[10],nr=0,c=0,v[100],Sm[100],mx=0;
char a[100][100];

int afisare(int n)
{for(int i=0;i<=n;i++)
    cout<<a[x[i]]<<" ";
nr++;
cout<<endl;}

int verif(int i)
{if(i>1 && strcmp(a[x[i]],a[x[i-1]])==0)
    return 0;
if(i==1 && (a[x[i]][0]!=a[x[i-1]][strlen(a[x[i-1]])-2] || a[x[i]][1]!=a[x[i-1]][strlen(a[x[i-1]])-1]))
    return 0;
for(int j=1;j<i;j++)
    if(x[i]==x[j])
        return 0;
if(i>1 && (a[x[i]][0]!=a[x[i-1]][strlen(a[x[i-1]])-2] || a[x[i]][1]!=a[x[i-1]][strlen(a[x[i-1]])-1]))
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{
    x[i]=j;
    if(verif(i))
        {afisare(i);
    if(i>mx)
    {mx=i;
    for(int k=1;k<=i;k++)
        Sm[k]=x[k];
    }
    if(i<=n)
        back(i+1);
        }
}
}

int main()
{int i,j,nn,k=0;
cin>>n;
for(i=0;i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<endl<<"Cea mai lunga"<<endl;
for(i=0;i<=mx;i++)
    cout<<a[Sm[i]]<<" ";
cout<<"este formatata din "<<mx<<" cuvinte";
cout<<endl<<nr<<" solutii";
}

1.  La un concurs se prezinta n concurenti din m tari. Sa se stabileasca ordinea intrarii in concurs a celor n concurenti astfel incat doi concurenti din aceeasi tara sa nu urmeze unul dupa altul.

#include<iostream>
using namespace std;
int n,x[10],nr=0;

struct concurent{
    int nr;
    char tara[100];
}a[100];

int afisare(int n)
{for(int i=1;i<=n;i++)
    cout<<a[x[i]].nr<<". "<<a[x[i]].tara<<endl;
nr++;
cout<<endl;}

int verif(int i)
{if(strcmp(a[x[i]].tara,a[x[i-1]].tara)==0)
    return 0;
for(int j=1;j<i;j++)
    if(a[x[i]].nr==a[x[j]].nr)
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare(n);
    else back(i+1);
}
}

int main()
{int i,j;
cin>>n;
for(i=1;i<=n;i++)
{a[i].nr=i;
cin>>a[i].tara;
}
back(1);
cout<<nr<<" solutii";
}

2.  Fiind data o multime de n cuburi, fiecare cub fiind caracterizat de lungimea laturii si culoarea sa, sa se scrie un program care sa genereze toate turnurile care se pot forma cu p cuburi astfel incat doua cuburi vecine sa nu aiba aceeasi culoare iar deasupra unui cub sa nu se poata aseza un cub cu latura mai mare.

 #include<iostream>
using namespace std;
int n,p,x[10],nr=0;

struct cub{
    int l;
    char culoare[100];
}a[100];

int afisare(int n)
{for(int i=1;i<=n;i++)
    cout<<a[x[i]].l<<" "<<a[x[i]].culoare<<endl;
nr++;
cout<<endl;}

int verif(int i)
{if(i>1 && strcmp(a[x[i]].culoare,a[x[i-1]].culoare)==0)
    return 0;
for(int j=1;j<i;j++)
    if(x[i]==x[j])
        return 0;
if(i>1 && a[x[i]].l>a[x[i-1]].l)
    return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==p)
        afisare(p);
    else back(i+1);
}
}

int main()
{int i,j;
cout<<"n=";cin>>n;
cout<<"p=";cin>>p;
for(i=1;i<=n;i++)
{cin>>a[i].l>>a[i].culoare;
}
cout<<endl<<"---------"<<endl;
back(1);
cout<<nr<<" solutii";
}

3. Se doreste memorarea mai usoara a unui numar de telefon. Vom asocia fiecarei cifre din numar una din literele de pe aceeasi tasta, de pe telefonul mobil.

a)Sa se afiseze toate  cuvintele care se pot obtine.

b)Sa se afiseze toate cuvintele in care nu exista 2 litere alaturate identice si nu exista 3 consoane alaturate.

Obs: daca numarul de telefon contine cifrele 0 sau 1 afisam un mesaj sau punem 2 caractere, de exemplu * si  !.

#include<iostream>
using namespace std;
int n,p,x[10],nr=0,c=0,v[100];
char a[11][5]={"*","!","abc","def","ghi","jkl","mno","pqrs","tuv","xywz"};

int afisare(int n)
{int k=1;
    for(int i=0;i<n;i++)
        {cout<<a[v[i]][x[i]]<<" ";
        k=k*10;}
nr++;
cout<<endl;}

int verif(int i)
{
    if(x[i]>=strlen(a[v[i]]))
        return 0;
else return 1;
}

void back(int i)
{int j;
for(j=0;j<=3;j++)
{
    x[i]=j;
    if(verif(i))
        if(i==n)
            afisare(n);
        else back(i+1);
}
}

int main()
{int i,j,nn;
cin>>n;
for(i=0;i<n;i++)
    cin>>v[i];
back(0);
cout<<nr<<" solutii";
}

Sa se genereze submultimile multimii {1,2,...,n}

#include<iostream>
using namespace std;
int n,x[10],nr=0;
void afisare(int n)
{for(int i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;nr++;
}

void rec(int i)
{int j;
for(j=x[i-1]+1;j<=n;j++)
{x[i]=j;
afisare(i);
rec(i+1);}}

int main()
{cin>>n;rec(1);
cout<<nr<<" solutii";}

Sa se afiseze elementele produsului cartezian a n multimi. Fiecare multime contine litere mici din alfabet.

#include<iostream>
using namespace std;
int n,nr=0;
char a[10][10],x[10];
void back(int i)
{int j;
for(j=0;j<strlen(a[i]);j++)
{x[i]=a[i][j];
if(i==n)
    {cout<<x+1<<endl;nr++;}
else back(i+1);}
}
int main()
{int i;
cin>>n;
for(i=1;i<=n;i++)
    cin>>a[i];
x[n+1]=NULL;
back(1);
cout<<nr<<" solutii";}

1. Să se genereze toate codurile de lungime n morse formate din '.' şi '-' astfel încât să nu existe două puncte alăturate.

#include<iostream>
using namespace std;
char x[100];
int n,nr=0;
int verif(int i)
{if(i>1 && x[i]=='.' && x[i-1]=='.')
    return 0;
else return 1;
}

void back(int i)
{char j;
for(j='-';j<='.';j=j+'.'-'-')
    {x[i]=j;
if(verif(i))
    if(i==n)
    {    cout<<x+1<<endl;nr++;}
    else back(i+1);
    }
}

int main()
{cin>>n;
x[n+1]=NULL;
back(1);
cout<<endl<<nr<<" solutii";
}

2. Sa se aranjeze 8 regine pe tabla de şah astfel încât acestea să nu se atace. Două regine se atacă dacă sunt situate pe aceeaşi coloană, rând sau diagonală.

#include<iostream>
using namespace std;
int r[10],nr=0;

void afisare()
{int i,j;
nr++;
for(i=1;i<9;i++)
{for(j=1;j<9;j++)
    if(r[i]==j)
        cout<<'.';
    else cout<<'X';
    cout<<endl;}
cout<<endl;}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(r[i]==r[j])
        return 0;
for(j=1;j<i;j++)
    if(abs(r[i]-r[j])==abs(i-j))
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<9;j++)
    {r[i]=j;
    if(verif(i))
        if(i==8)
            afisare();
        else back(i+1);
    }
}

int main()
{
back(1);
cout<<endl<<nr<<" solutii";
}

1. Se citesc n nr nat. Sa se afiseze toate posibilitatile de plasare in fata numerelor a semnelor + sau - astfel incat expresia care se obtine sa aiba valoarea s.

#include<iostream>
using namespace std;
int a[100],x[100],n,s,nr=0;
void afisare()
{int i;
for(i=1;i<=n;i++)
    if(x[i]==1)
        cout<<"+"<<x[i]*a[i];
    else cout<<x[i]*a[i];
cout<<endl;
nr++;
}

int verif(int i)
{int ss=0,j;
if(i!=n)
    return 1;
for(j=1;j<=n;j++)
    ss=ss+(x[j]*a[j]);
if(ss!=s)
    return 0;
return 1;
}

void back(int i)
{int j;
for(j=-1;j<=1;j+=2)
{x[i]=j;
    if(verif(i))
        if(i==n)
            afisare();
        else back(i+1);
}
}

int main()
{int i;
cout<<"n=";cin>>n;
cout<<"s=";cin>>s;
for(int i=1;i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<nr<<" solutii";
}

2. Sa se genereze produsul cartezian {1,2,...,m}x{1,2,...,m} de n ori.

#include<iostream>
using namespace std;
int a[100],x[100],n,m,nr=0;
void afisare()
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;
nr++;
}
void back(int i)
{int j;
for(j=1;j<=m;j++)
{x[i]=j;
    if(i==n)
        afisare();
    else back(i+1);
}
}

int main()
{int i;
cout<<"n=";cin>>n;
cout<<"m=";cin>>m;
back(1);
cout<<endl<<nr<<" solutii";
}

3. O persoana a uitat nr de tel. Stie doar ca numarul are 6 cifre, incepe cu 4 si contine 3 cifre de 0, dintre care doua sunt alaturate. Afisati toate variantele.

#include<iostream>
using namespace std;
int x[11],nr=0;
void afisare()
{int i;nr++;
for(i=1;i<7;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{int j,s=0,ok=0;

if(i>=4 && x[i]==0 && x[i-1]==0 && x[i-2]==0)
    return 0;

if(i==6)
{for(j=3;j<7;j++)
    if(x[j]==0 && x[j-1]==0)
        ok=1;
if(ok==0)
    return 0;
for(j=2;j<7;j++)
    if(x[j]==0)
        s++;
    if(s!=3)
        return 0;
}
return 1;
}

void back(int i)
{int j;
for(j=0;j<10;j++)
{x[i]=j;
if(verif(i))
    if(i==6)
        afisare();
    else back(i+1);}
}

int main()
{x[1]=4;
back(2);
cout<<nr;
}

4. Sa se genereze toate palindroamele de lungime n.

#include<iostream>
using namespace std;
int x[11],n,nr=0;
void afisare()
{int i;nr++;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{if(i==1 && x[i]==0)
    return 0;
if(n%2==1)
    if(i>n/2)
        if(x[i]!=x[n-i+1])
            return 0;
if(n%2==0)
    if(i>n/2)
        if(x[i]!=x[n-i+1])
            return 0;
return 1;
}

void back(int i)
{int j;
for(j=0;j<10;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare();
    else back(i+1);}
}

int main()
{
cin>>n;
back(1);
cout<<endl<<nr<<" solutii";
}

1. Sa se genereze toate coadele de 5 cifre cu urmatoarele restrictii: cifrele iau valori de la 1 la 9, numar impar pe ultima pozitie, suma a doua cifre alaturate sa fie minim 4, cifrele sa fie distinct

#include<iostream>
using namespace std;
int x[6],nr=0;
void afisare()
{int i;
for(i=1;i<6;i++)
    cout<<x[i]<<" ";
cout<<endl;
nr++;
}

int verif(int i)
{int j,k,v[100]={0};
if(i==5 && x[i]%2==0)
    return 0;
if(i>1 && x[i]+x[i-1]<4)
    return 0;
if(i==5)
    for(j=1;j<6;j++)
        v[x[j]]++;
for(j=0;j<10;j++)
    if(v[j]>1)
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<10;j++)
{x[i]=j;
if(verif(i))
    if(i==5)
        afisare();
    else back(i+1);
}}

int main()
{back(1);
cout<<endl<<nr;}

2. Sa se genereze toate nr de telefon care incep cu 074 sau 075 (10 cifre), nu contin 3 cifre identice alaturate si contin cel putin doua cifre impare pe ultimele 7 pozitii.

#include<iostream>
using namespace std;
int x[11],nr=0;
void afisare()
{int i;nr++;
for(i=1;i<11;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{int j,s=0;
for(j=1;j<i;j++)
    if(x[i]==x[j])
        return 0;
if(i>4 && x[i]==x[i-1] && x[i-1]==x[i-2])
    return 0;
if(i==10)
{for(j=4;j<11;j++)
    if(x[j]%2==1)
        s++;
    if(s<2)
        return 0;
}
return 1;
}

void back(int i)
{int j;
for(j=0;j<10;j++)
{x[i]=j;
if(verif(i))
    if(i==10)
        afisare();
    else back(i+1);}
}

int main()
{x[1]=0;x[2]=7;x[3]=4;
back(4);
cout<<endl<<endl<<"+++++++++++++++++++"<<endl<<endl<<nr<<endl<<endl;
nr=0;
x[3]=5;back(4);
cout<<endl<<endl<<nr;
}

1. A) Sa se genereze in ordine lexico-grafica cuvintele din multimea a-h cu n litere si care nu contin doua vocale alaturate.

#include<iostream>
using namespace std;
int nr=0,n,x[10];
char a[10]=" abcdefgh";

void afisare(int n)
{int i;
nr++;
for(i=1;i<=n;i++)
    cout<<a[x[i]];
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i] || strchr("aeiou",a[x[i]])!=0 && strchr("aeiou",a[x[i-1]])!=0 && i>1)
        return 0;
    return 1;}

void back(int i)
{int j;
for(j=1;j<=8;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare(n);
    else back(i+1);
}
}

int main()
{cin>>n;
back(1);
cout<<endl<<nr;
}

B) Sa se genereze cuvintele de k litere care incep cu o vocala si se termina cu o consoana.

#include<iostream>
using namespace std;
int nr=0,n,x[10],k;
char a[10]=" abcdefgh";

void afisare(int k)
{int i;
nr++;
for(i=1;i<=k;i++)
    cout<<a[x[i]];
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i])
        return 0;
    if(i==1 && strchr("aeiou",a[x[i]])==0)
        return 0;
    if(i==k && strchr("aeiou",a[x[i]])!=0)
        return 0;
return 1;}

void back(int i)
{int j;
for(j=1;j<=8;j++)
{x[i]=j;
if(verif(i))
    if(i==k)
        afisare(k);
    else back(i+1);
}
}

int main()
{cin>>k;
back(1);
cout<<endl<<nr;
}

2. n copii sunt pregatiti pentru ora de sport. Se cunoaste inaltimea fiecaruia. Trebuie alesi k copii insirati pe un rand astfel incat diferenta dintre oricare 2 elevi sa nu fie mai mare de 10 cm.

#include<iostream>
using namespace std;
int nr=0,n,x[10],k;
int a[100];

void afisare(int k)
{int i;
nr++;
for(i=1;i<=k;i++)
    cout<<a[x[i]]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i])
        return 0;
    if(i>1 && abs(a[x[i]]-a[x[i-1]])>10)
        return 0;
return 1;}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==k)
        afisare(k);
    else back(i+1);
}
}

int main()
{cout<<"n=";cin>>n;
cout<<"k=";cin>>k;
for(int i=1; i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<nr;
}

3. Sa se scrie un algoritm BackTracking care genereaza toate sirurile de 5 cifre 0 si 1 astfel incat sa nu existe mai mult de doua cifre de 0 alaturate.

#include<iostream>
using namespace std;
int nr=0,n,x[10],k;
char a[10]=" 01";

void afisare()
{int i;
nr++;
for(i=1;i<=5;i++)
    cout<<a[x[i]]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(i>1 && a[x[i]]=='0' && a[x[i-1]]=='0')
        return 0;
return 1;}

void back(int i)
{int j;
for(j=1;j<=2;j++)
{x[i]=j;
if(verif(i))
    if(i==5)
        afisare();
    else back(i+1);
}
}

int main()
{back(1);
cout<<endl<<nr;
}

5. n persoane stau pe scaune numerotate de la 1 la n. Oricare doi vecini se ceartă. Să se afişeze toate posibilităţile de a-i reaşeza pe scaune astfel încât să nu fie 2 foşti vecini alăturaţi.

#include<iostream>
using namespace std;
int nr=0,n,x[100],k;
char a[10]=" 01";

void afisare(int n)
{int i;
nr++;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i])
        return 0;
if(i>1 && abs(x[i]-x[i-1])<=1)
    return 0;
return 1;}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare(n);
    else back(i+1);
}
}

int main()
{int i;
cin>>n;
    for(i=1;i<=n;i++)
        x[i]=i;
back(1);
cout<<endl<<nr;
}