Pentru inceput am introdus majoritatea programelor invatate pana acum la backtracking.

Site-ul este interzis urmatorilor indivizi:

                                                  

                                                   Neacsu VLADut

                                                   Ramboi IONut

 

                 Deorece contine elemente cu continut pornographic( pentru ei).

                                 

Probleme rezolvate prin backtracking.

 

 

1.Permutari

2.Aranjamente

3.Combinari

4.Problma celor n dame

5.Produs cartezian

6.Problema colorarii hartilor

 

 

(1)Problema permutarilor

 

#include <iostream.h>

#include <conio.h>

int n,k,st[100];

void tipar(){

for(int i=1;i<=n;i++) cout<<st[i]<<' ';

cout<<endl;}

int e_valid(){

for(int i=1;i<=k-1;i++) if(st[i]==st[k]) return 0;

return 1;

}

int am_succesor(){

if(st[k]<n){st[k]++;return 1;}

else return 0;

}

int solutie(){

return k==n;}

void init(){st[k]=0;}

void back(){

int as;

k=1;

init();

 

while(k>0){

do{}while((as=am_succesor())&&!e_valid());

if(as)

                 if(solutie()) tipar();

                 else{k++;init();}

else k--;

}

}

void main()

{

clrscr();

cin>>n;

back();

getch();

}

 

 

 

(2)Problema aranjamentelor

 

#include <iostream.h>

#include <conio.h>

int n,k,st[100],p;

void tipar(){

for(int i=1;i<=p;i++) cout<<st[i]<<' ';

cout<<endl;}

int e_valid(){

for(int i=1;i<=k-1;i++) if(st[i]==st[k]) return 0;

return 1;

}

int am_succesor(){

if(st[k]<n){st[k]++;return 1;}

else return 0;

}

int solutie(){

return k==p;}

void init(){st[k]=0;}

void back(){

int as;

k=1;

init();

 

while(k>0){

do{}while((as=am_succesor())&&!e_valid());

if(as)

                 if(solutie()) tipar();

                 else{k++;init();}

else k--;

}

}

void main()

{

clrscr();

cin>>n;

cin>>p;

back();

getch();

}

 

 

(3) Problema combinarilor

 

#include <iostream.h>

#include <conio.h>

int n,k,st[100],p;

void tipar(){

for(int i=1;i<=p;i++) cout<<st[i]<<' ';

cout<<endl;}

int e_valid(){

for(int i=1;i<=k-1;i++) if(st[i]==st[k]) return 0;

return 1;

}

int am_succesor(){

if(st[k]<n-p+k){st[k]++;return 1;}

else return 0;

}

int solutie(){

return k==p;}

void init(){

if(st[k]>1) st[k]=st[k-1];

else st[k]=0;}

void back(){

int as;

k=1;

init();

 

while(k>0){

do{}while((as=am_succesor())&&!e_valid());

if(as)

                 if(solutie()) tipar();

                 else{k++;init();}

else k--;

}

}

void main()

{

clrscr();

cin>>n;

cin>>p;

back();

getch();

}

 

 

(4) Problema celor n dame

 

#include <iostream.h>

#include <conio.h>

#include <math.h>

int n,k,st[100];

void tipar(){

for(int i=1;i<=n;i++) cout<<st[i]<<' ';

cout<<endl;}

int e_valid(){

for(int i=1;i<=k-1;i++) if(st[i]==st[k] || abs(st[k]-st[i])==abs(k-i))return 0;

return 1;

}

int am_succesor(){

if(st[k]<n){st[k]++;return 1;}

else return 0;

}

int solutie(){

return k==n;}

void init(){st[k]=0;}

void back(){

int as;

k=1;

init();

 

while(k>0){

do{}while((as=am_succesor())&&!e_valid());

if(as)

                 if(solutie()) tipar();

                 else{k++;init();}

else k--;

}

}

void main()

{

clrscr();

cin>>n;

back();

getch();

}

 

 

(5) Problema produsului cartezian

 

#include <iostream.h>

#include <conio.h>

int n,k,st[100],a[100];

void tipar(){

for(int i=1;i<=n;i++) cout<<st[i]<<' ';

cout<<endl;}

int e_valid(){

return 1;

}

int am_succesor(){

if(st[k]<a[k]){st[k]++;return 1;}

else return 0;

}

int solutie(){

return k==n;}

void init(){st[k]=0;}

void back(){

int as;

k=1;

init();

 

while(k>0){

do{}while((as=am_succesor())&&!e_valid());

if(as)

                 if(solutie()) tipar();

                 else{k++;init();}

else k--;

}

}

void main()

{

clrscr();

cin>>n;

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

back();

getch();

}

 

 

(6)Problema colorarii hartilor

 

#include <iostream.h>

#include <conio.h>

int n,k,st[100],a[50][50];

void tipar(){

for(int i=1;i<=n;i++) cout<<"Tara "<<i<<" culoarea "<<st[i]<<' ';

cout<<endl;}

int e_valid(){

for(int i=1;i<=k-1;i++) if(st[i]==st[k]&&a[i][k]==1) return 0;

return 1;

}

int am_succesor(){

if(st[k]<4){st[k]++;return 1;}

else return 0;

}

int solutie(){

return k==n;}

void init(){st[k]=0;}

void back(){

int as;

k=1;

init();

 

while(k>0){

do{}while((as=am_succesor())&&!e_valid());

if(as)

                 if(solutie()) tipar();

                 else{k++;init();}

else k--;

}

}

void main()

{

clrscr();

cin>>n;

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

for(int j=1;j<=i-1;j++){

cout<<"a["<<i<<"]["<<j<<"]=";

cin>>a[i][j];

a[j][i]=a[i][j];}

back();

getch();

}