Probleme BKT

Probleme BKT

1) Anagramele unui cuvant

#include <iostream>
#include <string.h>
using namespace std;
int n,x[100];
char s[100];
void citire(char s[100],int &n)
{int i;
cout<<"n = "; cin>>n;
for(i=0;i<n;i++)
cin>>s[i];}

int solutie(int k)
{if(k==n  )
return 1;
else
return 0;}

int valid(int k)
{int i;
for(i=1;i<k;i++)
if(x[i]==x[k])
return 0;
return 1;}

void tipar(int k)
{int i;
for(i=1;i<=k;i++)
cout<<s[x[i]-1]<<" ";
cout<<endl;}

void BKT()
{int k;
k=1;
x[k]=0;
while(k!=0)
 if(x[k]<n)
{x[k]=x[k]+1;
 if(valid(k))
  if(solutie(k))
    tipar(k);
   else
  {k++;
   x[k]=0;}}
else
k--;}
int main()
{ citire(s,n);
BKT();
return 0;}

2) Problema parantezelor

#include <iostream>
using namespace std;
int x[100], n;
void citire(int &n)
{
    cout<<"n= "; cin>>n;
}
void numara(int k, int &nr1, int &nr0)
{
    int i;
    for(int i=1; i<=k; i++)
        if(x[i]==1)
          nr1++;
        else
           nr0++;
}
int sol(int k)
{
    if(k==n && x[k]==0)
       return 1;
 return 0;
}
int valid(int k)
{
    int nr1=0,nr0=0;
    numara(k, nr1, nr0);
    if(nr1>n/2)
      return 0;
      if(x[1]==0)
         return 0;
    if(nr1<nr0)
     return 0;
 return 1;

}
void tipar(int k)
{
    cout<<"Solutie: "<<endl;
    for(int i=1; i<=k; i++)
       if(x[i]==1)
          cout<<"(";
        else
           cout<<")";
    cout<<endl;

}
void backt()
{
    int k=1;x[k]=-1;
    while(k!=0)
      if(x[k]<1)
        {
            x[k]=x[k]+1;
            if(valid(k))
              {if(sol(k))
               tipar(k);
               else
               {
                   k++;
                   x[k]=-1;
               }
              }
        }
        else
        k--;

}
int main()
{
    citire(n);
    if(n%2!=0)
    cout<<"nu are solutie ";
    else
     backt();
}

3) Problema turelor

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

int solutie(int k)
{if(k==n)
return 1;
else
return 0;}

int valid(int k)
{int i;
for(i=1;i<k;i++)
if(x[i]==x[k])
return 0;
return 1;}

void tipar(int k)
{int i;
for(i=1;i<=n;i++)
{cout<<endl;
for(j=1;j<=n;j++)
if(j==x[i])
cout<<1;
else
cout<<0;}
cout<<endl;}

void BKT()
{int k;
k=1;
x[k]=0;
while(k!=0)
 if(x[k]<n)
{x[k]=x[k]+1;
 if(valid(k))
  if(solutie(k))
    tipar(k);
   else
  {k++;
   x[k]=0;}}
else
k--;}
int main()
{ cout<<"n = ";
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
BKT();
return 0;}

4) Toate numerele care se pot forma din n cifre citite mai mici sau egale cu d

#include <iostream>
using namespace std;
int v[100], x[100], n, d;
void citire(int v[100], int &n, int &d)
{
    cout<<"Nr. de cifre: "; cin>>n;
    cout<<"d= "; cin>>d;
    cout<<"Cifrele sunt: ";
    for(int i=1; i<=n; i++)
        cin>>v[i];
}
int numar(int k)
{
    int nr=0;
    for(int i=1; i<=k; i++)
        nr=nr*10+v[x[i]];
    return nr;
}
int sol(int k)
{
    if(numar(k)<=d)
        return 1;
    else
        return 0;
}
int valid(int k)
{
    if(numar(k)>d)
        return 0;
    if(k==1 && v[x[k]]==0)
        return 0;
    return 1;
}
void tipar(int k)
{
    cout<<"Solutie: ";
    for(int i=1; i<=k; i++)
        cout<<v[x[i]];
    cout<<endl;
}
void backt()
{
    int k=1; x[k]=0;
    while(k!=0)
        if(x[k]<n)
    {
        x[k]=x[k]+1;
        if(valid(k))
        {
            if(sol(k))
                tipar(k);
         k++;
         x[k]=0;
        }
    }
    else
        k--;
}
int main()
{
    citire(v, n, d);
    backt();
    return 0;
}

5) toate numerele de m cifre care se pot forma cu toate cele n cifre citite ( m>=n )

#include <iostream>
using namespace std;
int n,x[100],m,a[100];
void citire(int &n,int &m,int a[100])
{cout<<"n=";
cin>>n;
cout<<"m= ";
cin>>m;
cout<<"Cifrele ";
for(int i=1;i<=n;i++)
   cin>>a[i];
}
int nr(int k,int n,int m)
{int OK=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{if(a[i]==x[j])
    {OK=OK+1;
        j=m+1;
    }
}
    return OK;
}
int valid(int k)
{for(int i=1;i<k;i++)
if(x[i]==x[k])
return 0;
return 1;}
int sol(int k)
{if(k==m && nr(k,n,m)==n)
return 1;
return 0;}
void tipar(int k)
{for(int i=1;i<=k;i++)
cout<<x[i]<<" ";
cout<<endl;
}
void bkt()
{int k=1;
x[k]=0;
while(k!=0)
if(x[k]<9)
{x[k]=x[k]+1;
if(valid(k))
if(sol(k))
tipar(k);
else
{k++;
x[k]=0;}}
else k--;}
int main()
{citire(n,m,a);
bkt();
    return 0;
}

6) Toate posibilitatile distribuirii a n obiecte intre 2 persoane

#include <iostream>
using namespace std;
int n,p,x[100],A[100];
void citire(int &n,int &p,int A[100])
{ cout<<"n = ";
cin>>n;
cout<<"p = ";
cin>>p;
for(int i=1;i<=n;i++)
A[i]=i;}

int valid(int k)
{
if(k>1&&(x[k-1]>=x[k]))
return 0;
return 1;}

int sol(int k)
{if(k==p)
return 1;
    return 0;
}

void tipar(int k)
{int i,j,OK;
cout<<"Persoana 1 : ";
for(i=1;i<=k;i++)
cout<<A[x[i]]<<" ";
cout<<"   Persoana 2 : ";
for(j=1;j<=n;j++)
{
    OK=1;
    for(i=1;i<=k;i++)
           if(A[x[i]]==j)
           OK=0;
    if(OK)
        cout<<j<<" ";
}
cout<<endl;}

void BKT()
{int k;
k=1;
x[k]=0;
while(k!=0)
if(x[k]<n)
{x[k]=x[k]+1;
if(valid(k))
if(sol(k))
tipar(k);
else
{k++;
x[k]=0;}}
else
k--;}

int main()
{ citire(n,p,A);
BKT();
return 0;}

7) Exemplu generare ( a nr pare , cel mult n cifre )

#include <iostream>
#include <cmath>
using namespace std;
int a[100], x[100], n, y;
void citire( int a[100], int &n, int &y)
{
    cout<<"n= "; cin>>n; y=pow(10, n);
    cout<<"Pare: ";
   a[1]=0;
   a[2]=2;
   a[3]=4;
   a[4]=6;
   a[5]=8;
}
int numar(int k)
{
    int nr=0;
    for(int i=1; i<=k; i++)
        nr=nr*10+a[x[i]];
    return nr;
}
int sol(int k)
{
    if(numar(k) <= y )
        return 1;
    else
        return 0;
}
int valid(int k)
{
    if(numar(k) > y)
        return 0;
    if( (k==1) && (a[x[k]]==0) )
        return 0;
    return 1;
}
void tipar(int k)
{
    cout<<"Solutie: ";
    for(int i=1; i<=k; i++)
        cout<<a[x[i]];
    cout<<endl;
}
void backt()
{
    int k=1; x[k]=0;
    while(k!=0)
        if(x[k]<5)
    {
        x[k]=x[k]+1;
        if(valid(k))
        {
            if(sol(k))
              tipar(k);
            k++;
            x[k]=0;
        }
    }
    else
        k--;
}
int main()
{
   citire(a, n, y);
   backt();
   return 0;
}

8) Partitii cu m submultimi

#include <iostream>
using namespace std;
int x[100],m,n,a[100],v[100];
void citire(int &n,int &m)
{cout<<"n= ";
cin>>n;
cout<<"m= ";
cin>>m;
for(int i=1;i<=n;i++)
{cin>>a[i];
}
}
int valid(int k)
{return 1;}
int cautare(int b,int k)
{
    for(int i=1;i<=k;i++)
    if(x[i]==b)
    return 1;
    return 0;
}
int sol(int k)
{if(k!=n)
return 0;
for(int i=1;i<=m;i++)
if(cautare(i,k)==0)
return 0;
return 1;}
void tipar(int k)
{for(int i=1;i<=m;i++)
    {cout<<"{";
    for(int j=1;j<=n;j++)
       if(x[j]==i)
    cout<<j<<" ";
    cout<<"} ";}
    cout<<endl;
    }
void bkt()
{int k=1;
    x[k]=0;
    while(k!=0)
    if(x[k]<m && k<=n)
    {x[k]=x[k]+1;
    if(valid(k))
        if(sol(k))
    tipar(k);
        else {k++;
        x[k]=0;}}
        else k--;
    }
int main()
{citire(n,m);
bkt();
    return 0;
}

9) Bila care trebuie sa ajunga la marginea terenului

#include <iostream>
#include <fstream>
using namespace std;
int Traseu[100][100],iini,jini,ifin,jfin,A[100][100],n,m;
int pas=1,ic,jc,oriz[8]={-1,0,1,0,-1,1,1,-1},vert[8]={0,1,0,-1,1,1,-1,-1};
ifstream f("in.txt");
ofstream g("out.txt");
void citire(int &n,int &m,int &iini,int &jini, int A[100][100])
{
f >> n >> m >> iini >> jini;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f >> A[i][j];
}
void tipar()
{
g << "Solutie: "<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
g << Traseu[i][j]<< " ";
g << endl;
}
g <<endl;
}
void backplan(int ic,int jc,int pas)
{
int k,inou,jnou;
for(k=0;k<8;k++)
{
inou=ic+oriz[k];
jnou=jc+vert[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
if(A[inou][jnou]<A[ic][jc] && Traseu[inou][jnou]==0)
{ Traseu[inou][jnou]=pas;
if(jnou==1 || jnou==m || inou==1 || inou==n)
tipar();
else
backplan(inou,jnou,pas+1);
Traseu[inou][jnou]=0;
}
}
}
int main()
{
citire(n,m,iini,jini,A);
Traseu[iini][jini]=1;
backplan(iini,jini,2);
return 0;
}
int main()
{
citire(n,m,iini,jini,ifin,jfin,A);
Traseu[iini][jini]=1;
backplan(iini,jini,2);
return 0;
}

10) Paritii ( submultimi cu sume egale )
#include <iostream>
using namespace std;
int x[100],n,a[100],S=0;
void citire(int &n)
{cout<<"n= ";
cin>>n;
for(int i=1;i<=n;i++)
{cin>>a[i];S+=a[i];
}
}
int suma1(int k)
{int s=0;
 for(int i=1;i<=k;i++)
 if(x[i]==1)
 s=s+a[i];
return s;
}
int suma2(int k)
{int s=0;
 for(int i=1;i<=k;i++)
 if(x[i]==2)
 s=s+a[i];
return s;
}
int suma3(int k)
{int s=0;
 for(int i=1;i<=k;i++)
 s=s+x[i];
return s;
}
int valid(int k)
{if(suma1(k)<=S/2 && suma2(k)<=S/2)
return 1;
return 0;   }
int sol(int k)
{if(k==n && suma1(k)==suma2(k))
return 1;
return 0;}
void tipar(int k)
{for(int i=1;i<=2;i++)
    {cout<<"{";
    for(int j=1;j<=n;j++)
       if(x[j]==i)
    cout<<j<<" ";
    cout<<"}";}
    cout<<endl;
    }
void bkt()
{int k=1;
    x[k]=0;
    while(k!=0)
    if(x[k]<2&& k<=n)
    {x[k]=x[k]+1;
    if(valid(k))
        if(sol(k))
    tipar(k);
        else {k++;
        x[k]=0;}}
        else k--;
    }
int main()
{citire(n);
bkt();
    return 0;
}