vineri, 24 aprilie 2015

Aplicaţii Backtracking

PROBLEME:


TABLA DE SAH:

       Fiind dată o tablă de sah de dimensiunea nxn şi un cal în colţul stânga sus al acesteia, se cere să se afişeze toate posibilităţile de mutare a acestei piese de sah astfel încât să treacă o singură dată prin fiecare pătrat al tablei. O soluţie va fi afişată ca o matrice nxn în care sunt numerotate săriturile calului.
Exemplu, pentru n=5, o soluţie este :
1 14 9 20 23
10 19 22 15 8
5 2 13 24 21
18 11 4 7 16
3 6 17 12 25 

#include<fstream.h>
const int dx[8]={-1,1,2,2,1,-1,-2,-2};
const int dy[8]={-2,-2,-1,1,2,2,1,-1};
int a[10][10],n;
ofstream f("cal.out");

void afis()
{ int i,j;
  for(i=1;i<=n;i++)
  { for(j=1;j<=n;j++) f<<a[i][j]<<" ";
    f<<endl;
  }
 f<<endl;
}

int inside(int i,int j)
{
   return i>=1 && i<=n && j>=1 && j<=n;
}

void back(int i, int j, int pas)
{ int k,inou,jnou;
  a[i][j]=pas;
  if (pas==n*n)  afis();
  else for(k=0;k<8;k++)
             { inou=i+dx[k];
               jnou=j+dy[k];
               if (inside(inou,jnou) && a[inou][jnou]==0)
                   back(inou,jnou,pas+1);
             }
  a[i][j]=0;
}

void main()
{  cin>>n;;
   back(1,1,1);
}


CUVINTE FORMATE DIN N VOCALE MICI: 
Să se scrie un program care generează şi scrie într-un fişier toate cuvintele formate din n vocale mici (n număr natural citit de la tastatură, n<10), ordonate alfabetic. De exemplu, pentru n=3 se vor scrie în fisier:
aaa
aae
aai
aao
aau
aea
.....
uuo
uuu 


#include<iostream.h>
int x[10],n;
char v[]="aeiou";
void scriesol()
{ int j;
  cout<<endl;
  for(j=1;j<=n;j++) cout<<v[x[j]];
}
void back(int k)
{
  int i;
  for(i=0;i<=4;i++)
   {
       x[k]=i;
       if (k==n) scriesol();
       else back(k+1);
   }
}
void main()
{
  cin>>n;
  back(1);
}

CUBURI:
Din fişierul cub.in se citesc de pe prima linie 2 numere naturale n şi m şi de pe următoarele n linii n perechi l şi c unde l este lungimea laturii, iar c culoarea pentru n cuburi. l este numar natural, iar c este şir de caractere de lungime maxim 20. Să se construiască toate turnurile formate din cel putin m cuburi care se pot forma din cuburile citite din fişier ştiind că un cub se poate pune peste un altul doar dacă are latura strict mai mică si culoarea diferită de a celui peste care vrem sa îl punem. Să se afişeze turnurile obţinute şi turnul format din cele mai multe cuburi. Un turn se afisează începând cu cel mai de sus cub.
Exemplu:
3 2
3 verde
4 roşu
1 roşu
Se obţin turnurile:
1 roşu
3 verde

3 verde
4 roşu
si
1 roşu
3 verde
4 roşu 










#include<fstream.h>



#include<string.h>



struct cub{



     int l;



     char c[20];



   };



cub c[100];



int x[100],mx[100],max=0,n,m;



ifstream f("cub.in");



void citire()



{ int i;



  f>>n>>m;



  for(i=1;i<=n;i++)
f>>c[i].l>>c[i].c;



}



void scriesol(int k)



{ int j;



  if(k>max) {
max=k;



      
for(j=1;j<=max;j++) mx[j]=x[j];



       }



  for(j=k;j>=1;j--)



    cout<<c[x[j]].l<<"
"<<c[x[j]].c<<endl;



  cout<<endl;



}



int cond(int k)



{



  if(k>1)



    
if(c[x[k-1]].l>c[x[k]].l)



 if(strcmp(c[x[k-1]].c,c[x[k]].c)!=0) return 1;



 else return 0;



     else return 0;



  else return 1;



}



void back(int k)



{



  int i;



  for(i=1;i<=n;i++)



   {



       x[k]=i;



       if (cond(k))



     { if (k>=m)
scriesol(k);



       back(k+1);



     }



   }



}







void main()



{



 citire();



 back(1);



 cout<<"Cel
mai inalt turn:";



 for(int
j=max;j>=1;j--)



   
cout<<c[mx[j]].l<<"
"<<c[mx[j]].c<<endl;



}


LABIRINTUL :







Un labirint se
codifică printr-o matrice NxM în care 0 sunt poziţii libere, iar -1 reprezintă
zidurile. In poziţia io,jo se află un  şoricel
care se poate deplasa pe patru direcţii paralele cu liniile si coloanele
matricii.

Afisaţi toate drumurile prin care şoricelul poate parăsi labirintul.

Exemplu:

5 7

-1 -1 0 -1 -1 -1 -1

0 0 0 0 0 0 0

-1 -1 -1 -1 -1 0 -1

-1 0 0 0 0 0 0

-1 -1 -1 -1 -1 -1 -1

4 2

O soluţie este:

-1 -1 0 -1 -1 -1 -1

0 0 0 0 0 7 8

-1 -1 -1 -1 -1 6 -1

-1 1 2 3 4 5 0

-1 -1 -1 -1 -1 -1 -1

4,2 4,3 4,4 4,5 4,6 3,6 2,6 2,7 







#include<fstream>



#include<iomanip>



using namespace std;



  fstream
f("date.in", ios::in);



  fstream
g("date.out",ios::out);



  int
a[100][100],n,io,jo,b[100][3],m;



  int
di[8]={0,0,-1,1};



  int
dj[8]={-1,1,0,0};



  int inside(int i,int
j)



      { return i>=1
&& j>=1 && i<=n && j<=m;



      }        



  void citire()



     {
f>>n>>m;



       for(int
i=1;i<=n;i++)



                 for(int j=1;j<=m;j++)



                   f>>a[i][j];



             f>>io>>jo;



     }



  void afis(int k)



    { for(int
i=1;i<=n;i++)



            {  g<<endl;



                 for(int j=1;j<=m;j++)



                   g<<setw(3)<<a[i][j];



            }



     g<<endl;



     for(int
i=0;i<=k; i++)



    
g<<b[i][1]<<","<<b[i][2]<<"  ";



     g<<endl;



   }      



 int sol(int i,int j)



 {



             return i==1 || j==1 || i==n || j==m;



 }



 void back(int i,int
j,int k)



   { if(sol(i,j))
afis(k-1);



            else
for(int p=0;p<=3;p++)



                        {int inou,jnou;



                         inou=i+di[p];



                         jnou=j+dj[p];



                         if(inside(inou,jnou) &&
a[inou][jnou]==0)



                             {



                               b[k][1]=inou;



                               b[k][2]=jnou;



                               a[inou][jnou]=k+1;



                                       back(inou,jnou,k+1);



                                       a[inou][jnou]=0;



                                     }



                             



                        }



   }



 int main()



   { citire();



     a[io][jo]=1;



     b[0][1]=io;



     b[0][2]=jo;



     back(io,jo,1);



             return 0;



   }



















































































































































 REGELE ARTHUR: 





La curtea regelui
Arthur s-au adunat n cavaleri numerotaţi de la 1 la n.

Despre ei se cunosc relaţii de dusmanie de forma (x,y) cu semnificaţi că x şi y
se dusmănesc.

Afişaţi toate modurile în  care Arthur îi
poate aranja la o masă rotundă cu n scaune astfel încât sa nu stea unul langă
altul 2 cavaleri care duşmănesc. 















#include <fstream>



using namespace std;



ifstream fin("date.in");



ofstream fout("date.out");



int a[50][50],x[50],p[50],n;







void citire()



{



    int i,j;



    fin>>n;



    while(fin>>i>>j)
a[i][j]=a[j][i]=1;



}



void afis()



{



   int i;



  
for(i=1;i<=n;i++) fout<<x[i]<<" ";



   fout<<endl;



}



int bun(int k)



{



   if(k>1)
if(a[x[k]][x[k-1]]==1) return 0;



   if(k==n)
if(a[x[1]][x[n]]==1) return 0;



   return 1;



}



void back(int k)



{



    for(int
i=1;i<=n;i++)



      if(!p[i])



      {



          x[k]=i;
p[i]=1;



          if(bun(k))
if(k==n) afis();



                    
else back(k+1);



          p[i]=0;



      }



}



int main()



{



    citire();



    back(1);



    fin.close();



    fout.close();



    return 0;



}









BANCNOTELE:





       Se citeşte un
număr natural n şi apoi n numere naturale ordonate strict cresător reprezentând
 valorile a n bancnote.




Se citeşte apoi o suma de bani s şi se cere să se plătească în toate modurile
posibile suma s cu bancnote de valorile precizate. Se presupune că avem la
dispozitie oricâte bancnote de fiecare valoare.

Ex:

n=4

valorile bancnotelor: 1 5 10 50

s=100

Se vor obţine soluţii de forma:

2*50

5*10 1*50

10*10

2*5 4*10 1*50

...

35*1 1*5 1*10 1*50

...

95*1 1*5

100*1











#include <fstream>



using namespace std;



ifstream fin("date.in");



ofstream fout("date.out");



int x[100], a[100], n,s;



void citire()



{



    fin>>n;



    for(int i=1;i<=n;i++) fin>>a[i];



    fin>>s;



}



void afis()



{



    for(int
i=1;i<=n;i++)



        if(x[i]!=0)
fout<<x[i]<<"*"<<a[i]<<" ";



    fout<<endl;



}



void back(int k,int sp)



{



   int i;



   for(i=0;i<=(s-sp)/a[k];i++)



   {



       x[k]=i;



      
sp=sp+x[k]*a[k];



       if(sp<=s
&& k<=n) if(k==n && sp==s) afis();



                 else
if(k<n) back(k+1,sp);



      
sp=sp-x[k]*a[k];



   }



}







int main()



{



    citire();



    back(1,0);



    fin.close();



    fout.close();



    return 0;





}

















EXAMENELE :











Un student are in
sesiune n examene fiecare având asociat un numar de credite. Pentru a
promova sesiunea el trebuie să acumuleze cel putin s credite.

Găsiţi toate nodurile in care poate el să îşi aleagă examenele pentru a promova
sesiunea astfel încat sa facă un efort minim, adică sa nu meargă la examene
fară de care oricum promovează.

Ordinea examenelor nu este importantă, iar dacă studentul îşi aleage un examen
se consideră ca il promovează.

Ex:

n=6

creditele: 7 8 10 10 2 6

s=30

Solutii:

10 10 8 7

10 10 8 6

10 10 8 2

10 10 7 6

10 8 7 6

10 8 7 6 (se repetă deoarece poate alege oricare din cele 2 examene cu 10
credite) 

















#include <fstream>



using namespace std;



ifstream fin("date.in");



ofstream fout("date.out");



int x[100], a[100], n,s;



void citire(int a[], int &n)



{



    fin>>n;



    for(int i=1;i<=n;i++) fin>>a[i];



    fin>>s;



}



void ordonare(int a[], int n)



{



    int i,j,aux;



   
for(i=1;i<n;i++)



       
for(j=i+1;j<=n;j++)



       
if(a[i]<a[j])



        {



            aux=a[i]; a[i]=a[j]; a[j]=aux;



        }



}



void afis(int n)



{



    for(int
i=1;i<=n;i++)



        if(x[i]!=0)
fout<<a[x[i]]<<" ";



    fout<<endl;



}



int bun(int k)



{



    if(k>1)



   
if(a[x[k]]>a[x[k-1]]) return 0;



    return 1;



}



void back(int x[],int k,int sp)



{



   int i;



  
for(i=x[k-1]+1;i<=n;i++)



   {



       x[k]=i;



       sp=sp+a[x[k]];



       if(bun(k))



           
if(sp>=s) afis(k);



       else
back(x,k+1,sp);



       sp=sp-a[x[k]];



   }



}



int main()



{



    citire(a,n);



    ordonare(a,n);



    back(x,1,0);



    fin.close();



    fout.close();



    return 0;



}











DOMINO:





Se consideră n piese de domino citite ca perechi
de numere naturale, fiecare pe câte un rand de intrare. Se citşte apoi un numar
natural a.

Să se afişeze toate soluţiile de aranjare a acestor piese intr-un lant domino
de lungime a, fară a roti piesele.

(Un lant domino se alcătuieşte din piese domino astfel încat o piesa este
urmată de altă a cărei prima jumatate coincide cu jumatatea a doua a piesei
curente.)

Ex: 1,2 2,6 6,8

date.in:

6

1 2

1 3

3 4

2 3

3 5

4 5

3

date.out:

1 2 2 3 3 4

1 2 2 3 3 5

1 3 3 4 4 5 

2 3 3 4 4 5







#include <fstream>



using namespace std;



ifstream
fin("date.in");



ofstream
fout("date.out");



struct piesa {int a,b;};



int p[100], x[100],n,a;



piesa d[100];



void citire()



{



    int i;



    fin>>n;



    for(i=1;i<=n;i++)
fin>>d[i].a>>d[i].b;



    fin>>a;



}



void afis()



{



    int i;



    for(i=1;i<=a;i++)
fout<<d[x[i]].a<<" "<<d[x[i]].b<<"  ";



    fout<<endl;



}



void back(int k)



{



    int i;



    for(i=1;i<=n;i++)



        if(!p[i])



        {



            x[k]=i; p[i]=1;



            if(k==1 || d[x[k-1]].b==d[x[k]].a)
if(k==a) afis();



                                             
else back(k+1);



            p[i]=0;



        }



}



int main()



{



    citire();



    back(1);



    fin.close();



    fout.close();



    return 0;



























































































}



















PETSHOP:









Magazinul PetShop vinde n specii de peşti despre care se ştiu m perechi de
peşti care nu pot fi puşi in acelaşi acvariu deoarece se atacă.

Gigi are un acvariu si vrea să işi cumpere un numar maxim de specii de peşti de
la magazinul PetShop. Ajutati-l pe Gigi sa aleaga speciile de pesti astfel
încât să poată avea un număr maxim de specii in acvariul său.

Exemplu:

n=6, m=5

perechile:

1 2

1 3

1 4

3 5

3 6

soluţia: 2 4 5 6













#include <fstream>



using namespace std;



ifstream fin("date.in");



ofstream fout("date.out");



int a[50][50],x[50],p[50],n, best[50], maxx=0,m;



void citire()



{



    int i,j;



   
fin>>n>>m;



   
while(fin>>i>>j) a[i][j]=a[j][i]=1;



}



void afis()



{



   for(int
i=1;i<=maxx;i++) fout<<best[i]<<" ";



}



int bun(int k)



{



   for(int
i=1;i<k;i++)



   
if(a[x[k]][x[i]]==1) return 0;



   return 1;



}







void back(int k)



{



    for(int
i=1;i<=n;i++)



      if(!p[i])



      {



          x[k]=i;
p[i]=1;



          if(bun(k))
{  if(k>maxx)



                       
{



                           
maxx=k;



                           
for(int j=1;j<=k;j++) best[j]=x[j];



                       
}



                       
else back(k+1);



                     }



          p[i]=0;



      }







}



int main()



{



    citire();



    back(1);



    afis();



    fin.close();



    fout.close();



    return 0;



}



Sursa :
cnamd.wikispaces.com/Metoda+Backtracking

























Publicat de



la







































Niciun comentariu:















Trimiteți un comentariu


















        

      









Abonați-vă la:
Postare comentarii (Atom)