Cuprins introducere Ce şanse am să devin un bun programator ? Legile succesului durabil (Ghidul studentului îndărătnic) 6 Probleme de judecată 8

Probleme ce necesită back-tracking

Am explicat pe larg această metodă de programare într-un capitol separat. În acest capitol vom oferi doar cîteva exemple de probleme rezolvate. Majoritatea dintre ele sînt de maximă dificultate şi nu li se cunoaşte o altfel de rezolvare decît prin această metodă. Din fericire, această metodă de proiectare a soluţiei are un caracter foarte general şi "funcţionează" în fiecare caz. Din nefericire, în practică, atunci cînd dimensiunea datelor de intrare este consistentă (avînd valori cel puţin de ordinul sutelor) programul rezultat devine, prin durata astronomică de execuţie, total inutilizabil.

Atragem atenţia că doar simpla lecturare a acestor exemple de probleme de back-tracking rezolvate nu permite nicidecum însuşirea acestei metode de proiectare a soluţiilor. Este necesară mai întîi implicarea şi participare personală, a celui ce-şi propune să înveţe această metodă, încercînd direct soluţionarea lor şi abia apoi comparînd soluţia rezultată cu cea propusă de noi.

Problema clasică de programare care necesită back-tracking (revenirea pe urma lăsată) este problema ieşirii din labirint.
- iată o soluţie simplă care iniţializează labirintul în mod static, ca o matrice de caractere
#include

#include

#include

#define XMAX 6

#define YMAX 6
char a[XMAX+1][YMAX+1]={

"*******",

"* * *",

"* * * *",

"* * ****",

"** * *",

"* * ",

"********"

};

int x0=1,y0=2;

void print(void){

int i,j;

for(i=0;i<=XMAX;i++){

for(j=0;j<=YMAX;j++)putchar(a[i][j]);

putchar('\n');

}

getchar();clrscr();

}
void escape(int x,int y){

if(x==XMAX || y==YMAX){ puts("Succes!");exit(1);}

a[x][y]='*';print();

if(a[x][y+1]==' '){puts("la dreapta");escape(x,y+1);}

if(a[x+1][y]==' '){puts("in jos ");escape(x+1,y);}

if(a[x][y-1]==' '){puts("la stinga ");escape(x,y-1);}

if(a[x-1][y]==' '){puts("in sus ");escape(x-1,y);}

return;

}
void main(void){

escape(x0,y0);

puts("Traped!");

}

Să se genereze toate şirurile de lungime n formate numai din caracterele a, b şi c a.î. să nu existe două subşiruri identice alăturate.
- de exemplu, dacă n=3 putem avea şiruri de forma abc, cab, bcb, etc. dar nu şi şiruri de forma aab; pentru n=4 nu putem genera şiruri de forma abab, baac, etc.
#include

#include

#include

#define byte unsigned char

char car[4]=" abc";

unsigned int n,contor;

int Valid(char *s,char c,byte k){ // functia de validare a sirului generat

byte i,j,ok,Val=1; // prin concatenarea unui singur caracter

for(i=k-1;i>=(k+1)/2;i--)

if (s[i]==c){

ok=1;

for(j=1;j<=k-i-1;j++)

if (s[i-j]!=s[k-j]){ok=0;break;}

if (ok) { Val=0;break;}

}

return Val;

}
void ConcatSir(char *s,byte k){ // functia ce implementeaza back-tracking-ul

byte i; // in varianta recursiva

if(k<=n){

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

if (Valid(s,car[i],k)) {

s[k]=car[i];s[k+1]='\0';

ConcatSir(s,k+1);

}

} else { contor++;printf("%4i:%s",contor,s);}

}
void main(void){

printf("n:");scanf("%i",&n);

contor=0;

ConcatSir(" ",1);

exit;

}

Să se afişeze toate descompunerile unei sume s într-un număr minim de monezi ale unui sistem monetar de n valori.

- de exemplu, în cazul unui sistem monetar de forma 10, 5, 3, 1 putem descompune suma 18 în diverse moduri dar soluţia minimală necesită doar 3 monezi: 18=1 x 10+1 x 5+1 x 3 ; descompunerea minimală poate să nu fie unică ; sistemul monetar trebuie să fie astfel ales încît să permită descompunerea oricărei sume începînd de la o valoare minimală în sus (orice sistem monetar conţine de obicei moneda unitară 1)
#include
int m[10],a[10],a_final[10],s,n,nrmin=32000,kmin;
void descompune(int s,int k,int contor){

register int i;

if(s==0)

if(contor

nrmin=contor;kmin=k-1;

for(i=1;i<=k;i++)a_final[i]=a[i];

for(i=k+1;i<=n;i++)a_final[i]=0;

return;

}

else return;

if(k>n) return;

if(k==n){

a[k]=s/m[k];descompune(s-a[k]*m[k],k+1,contor+a[k]);

}

else for(i=s/m[k];i>=0;i--){

a[k]=i;descompune(s-i*m[k],k+1,contor+i);

}

}

void main(void){

int i;

printf("Introd.nr.de valori n a sistemului monetar:");scanf("%i",&n);

printf("Introd.in ordine descresc.cele %i valori monetare:",n);

for(i=1;i<=n;i++)scanf("%i",&m[i]);

printf("Introd.suma s:");scanf("%i",&s);

descompune(s,1,0);

if(nrmin>0) for(i=1;i<=kmin;i++)printf("%i * %i,",a_final[i],m[i]);

else puts("Nu se poate descompune !");

}

Să se afişeze toate descompunerile unui număr s ca sumă de n elemente.

- de exemplu, pentru s=13 şi n=3 avem următoarele 14 descompuneri 13= 1+1+11= 1+2+10= 1+3+9=…= 1+6+6= 2+2+9= 2+3+8= 2+4+7= 2+5+6= 3+3+7= 3+4+6= 3+5+5= 4+4+5

- deşi este cu totul altă problemă decît cea dinainte, putem observa asemănarea dintre cele două soluţii (ambele sînt date în varianta recursivă)

#include
int a[10],s,n,contor=0;
void descompune(int s,int k){

register int i;

if(k==1){ a[n]=s;printf("%3i:",++contor);

for(i=1;i<=n;i++)printf("%i ",a[i]);

puts("");return;

}

else for(i=1;i

}
void main(void){

printf("Introd.suma s si in cit se descompune n:");scanf("%i %i",&s,&n);

descompune(s,n);

getchar();

}

Să se afişeze toate descompunerile unui număr s ca sumă de n elemente distincte.
- aceasta este o variantă a problemei dinainte; puteţi sesizaţi unde apare diferenţa în rezolvare ?
#include
int a[10],s,n,contor=0;
void descompune(int s,int k){

register int i;

if(k==0){ printf("%3i:",++contor);

for(i=1;i<=n;i++)printf("%4i",a[i]);

puts("");return;

}

else for(i=a[n-k]+1;i

}
void main(void){

printf("Introd.suma s si in cit se descompune n:");scanf("%i %i",&s,&n);

a[0]=0;

descompune(s,n);

if(contor==0)puts("Nu se poate descompune !");

getchar();

}