39
Metoda Backtracking
Metoda BacktrackingMetoda Backtracking
1. Aspecte teoretice1. Aspecte teoretice
Metoda Backtracking este o metodă de elaborare a algoritmilor. Ea se aplică problemelor în care soluţia se poate reprezenta sub forma unui vector, X=(x1,x2,...xm), care aparţine lui S=S1xS2x...Sm
- S=S1xS2x...Sm se numeşte spaţiul soluţiilor posibile
- Pentru fiecare problemă în parte se dau anumite condiţii între componentele vectorului soluţie care se numesc condiţii interne
- Soluţiile posibile care verifică condiţiile interne se numesc soluţii rezultat
- Metoda Backtracking îşi propune să genereze toate soluţiile rezultat
Metoda Backtracking este o metodă de elaborare a algoritmilor. Ea se aplică problemelor în care soluţia se poate reprezenta sub forma unui vector, X=(x1,x2,...xm), care aparţine lui S=S1xS2x...Sm
- S=S1xS2x...Sm se numeşte spaţiul soluţiilor posibile
- Pentru fiecare problemă în parte se dau anumite condiţii între componentele vectorului soluţie care se numesc condiţii interne
- Soluţiile posibile care verifică condiţiile interne se numesc soluţii rezultat
- Metoda Backtracking îşi propune să genereze toate soluţiile rezultat
O metodă simplă de a genera soluţiile rezultat constă în a genera într-un mod oarecare toate soluţiile posibile şi de a alege dintre acestea doar pe cele care verifică condiţiile interne. Dezavantajul constă în faptul că timpul cerut este foarte mare.
O metodă simplă de a genera soluţiile rezultat constă în a genera într-un mod oarecare toate soluţiile posibile şi de a alege dintre acestea doar pe cele care verifică condiţiile interne. Dezavantajul constă în faptul că timpul cerut este foarte mare.
Metoda Backtracking urmăreşte să evite generarea tuturor soluţiilor posibile. Pentru aceasta elementele vectorului x primesc pe rând valori în sensul că lui xk i se atribuie o valoare doar dacă componentele din faţa sa x1, x2,...xk-1 au primit valori.
Dacă lui xk i s-a atribuit o valoare, nu se trece direct la atribuirea de valori lui xk+1, ci se verifică nişte condiţii de continuare, referitoare la x1, x2,...xk-1 xk. Dacă condiţiile de continuare au fost satisfăcute, se trece la calculul lui xk+1. Neîndeplinirea lor exprimă faptul că oricum s-ar alege xk+1,...,xn, nu se va ajunge la o soluţie rezultat. Evident, ca în cazul neîndeplinirii condiţiilor de continuare va trebui să se facă o altă alegere pentru xk. Sau dacă Sk a fost epuizat, să se micşoreze k cu o unitate, încercând să se facă o nouă alegere pentru xk.
Metoda Backtracking urmăreşte să evite generarea tuturor soluţiilor posibile. Pentru aceasta elementele vectorului x primesc pe rând valori în sensul că lui xk i se atribuie o valoare doar dacă componentele din faţa sa x1, x2,...xk-1 au primit valori.
Dacă lui xk i s-a atribuit o valoare, nu se trece direct la atribuirea de valori lui xk+1, ci se verifică nişte condiţii de continuare, referitoare la x1, x2,...xk-1 xk. Dacă condiţiile de continuare au fost satisfăcute, se trece la calculul lui xk+1. Neîndeplinirea lor exprimă faptul că oricum s-ar alege xk+1,...,xn, nu se va ajunge la o soluţie rezultat. Evident, ca în cazul neîndeplinirii condiţiilor de continuare va trebui să se facă o altă alegere pentru xk. Sau dacă Sk a fost epuizat, să se micşoreze k cu o unitate, încercând să se facă o nouă alegere pentru xk.
2. Exemplu pentru înţelegerea metodei
2. Exemplu pentru înţelegerea metodei
Pentru a înţelege mai uşor prezentăm următorul exemplu:
Presupunem că dorim să ne îmbrăcăm de la un magazin pentru o festivitate şi dorim să cumpărăm: pantofi, ciorapi, pantaloni, cămaşă şi cravata astfel încât acestea să se asorteze între ele, să se genereze toate modalităţile de a ne îmbrăca.
Magazinul are:5 etajeLa etajul 1 are 4 raioane cu pantofiLa etajul 2 are 4 raioane cu ciorapiLa etajul 3 are 4 raioane cu pantaloniLa etajul 4 are 4 raioane cu cămăşiLa etajul 5 are 4 raioane cu cravate
Pentru a înţelege mai uşor prezentăm următorul exemplu:
Presupunem că dorim să ne îmbrăcăm de la un magazin pentru o festivitate şi dorim să cumpărăm: pantofi, ciorapi, pantaloni, cămaşă şi cravata astfel încât acestea să se asorteze între ele, să se genereze toate modalităţile de a ne îmbrăca.
Magazinul are:5 etajeLa etajul 1 are 4 raioane cu pantofiLa etajul 2 are 4 raioane cu ciorapiLa etajul 3 are 4 raioane cu pantaloniLa etajul 4 are 4 raioane cu cămăşiLa etajul 5 are 4 raioane cu cravate
Deoarece soluţia are mai multe componente, 5 – câte etaje are magazinul, putem folosi metoda Backtracking. Pentru rezolvare vom folosi:
k : variabilă întreagă care reprezintă etajul pe care ne găsim
x : vector care are 5 componente întregi, adică exact câte etaje are magazinul cu proprietatea că xk reprezintă numărul raionului de la care s-a cumpărat pe etajul k. În cazul de faţă xk {1,...,4} unde k{1,...,5}
as este o variabilă întreagă care primeşte valoarea 1 dacă pe etajul k mai sunt raioane nevizitate şi primeşte valoarea 0 dacă pe etajul k nu mai sunt raioane nevizitate.
ev este o variabilă întreagă care primeşte valoarea 1 dacă ce este la raionul xk convine şi primeşte valoarea 0 dacă ce este la raionul xk nu convine.
Deoarece soluţia are mai multe componente, 5 – câte etaje are magazinul, putem folosi metoda Backtracking. Pentru rezolvare vom folosi:
k : variabilă întreagă care reprezintă etajul pe care ne găsim
x : vector care are 5 componente întregi, adică exact câte etaje are magazinul cu proprietatea că xk reprezintă numărul raionului de la care s-a cumpărat pe etajul k. În cazul de faţă xk {1,...,4} unde k{1,...,5}
as este o variabilă întreagă care primeşte valoarea 1 dacă pe etajul k mai sunt raioane nevizitate şi primeşte valoarea 0 dacă pe etajul k nu mai sunt raioane nevizitate.
ev este o variabilă întreagă care primeşte valoarea 1 dacă ce este la raionul xk convine şi primeşte valoarea 0 dacă ce este la raionul xk nu convine.
se pleacă de la primul etajdin faţa uşiiatâta timp cât încă ne aflăm la un etaj , k
repetămne întrebăm dacă mai sunt raioane pe etajul kdacă da, atunci
se verifică dacă ne convine ce conţine raionul care urmeazăatâta timp cât mai sunt raioane şi nu am găsit ce ne place.dacă am găsit atunci
dacă le-am luat pe toate atunci
se afişeazăaltfel
se merge la etajul următor în faţa uşiialtfel
se coboară la etajul de jos
se pleacă de la primul etajdin faţa uşiiatâta timp cât încă ne aflăm la un etaj , k
repetămne întrebăm dacă mai sunt raioane pe etajul kdacă da, atunci
se verifică dacă ne convine ce conţine raionul care urmeazăatâta timp cât mai sunt raioane şi nu am găsit ce ne place.dacă am găsit atunci
dacă le-am luat pe toate atunci
se afişeazăaltfel
se merge la etajul următor în faţa uşiialtfel
se coboară la etajul de jos
Cum se procedează:
k=1; (se pleacă de la primul etaj)x[k]=0; (din faţa uşii)while (k>0) (atâta timp cât încă ne aflăm la un etaj , k)
{do (repetăm)
{succ(x,k,as); (ne întrebăm dacă mai sunt raioane pe etajul k)if(as) (dacă da, atunci)
valid(x,k,ev); (se verifică dacă ne convine ce conţine raionul care urmează)
}while(as&&!ev); (atâta timp cât mai sunt raioane şi nu am gasit ce ne
place.)if (as) (dacă am găsit atunci)
if(k==5) (dacă le-am luat pe toate atunci)afis(x,k) (se afişează)
else (altfel){
k=k+1; (se merge la etajul următor)x[k]=0; (în faţa uşii)
}else (altfel)
k=k-1; (se coboară la etajul de jos)}
k=1; (se pleacă de la primul etaj)x[k]=0; (din faţa uşii)while (k>0) (atâta timp cât încă ne aflăm la un etaj , k)
{do (repetăm)
{succ(x,k,as); (ne întrebăm dacă mai sunt raioane pe etajul k)if(as) (dacă da, atunci)
valid(x,k,ev); (se verifică dacă ne convine ce conţine raionul care urmează)
}while(as&&!ev); (atâta timp cât mai sunt raioane şi nu am gasit ce ne
place.)if (as) (dacă am găsit atunci)
if(k==5) (dacă le-am luat pe toate atunci)afis(x,k) (se afişează)
else (altfel){
k=k+1; (se merge la etajul următor)x[k]=0; (în faţa uşii)
}else (altfel)
k=k-1; (se coboară la etajul de jos)}
Reprezentarea a ceea ce s-a spus mai sus este:
Cum ne dăm seama dacă mai sunt raioane la etajul
k?
Cum ne dăm seama dacă mai sunt raioane la etajul
k?dacă numărul raionului de la etajul k este mai mic decât 4
atuncimai sunt raioane pe etajul kşi mergem la raionul următor
altfelnu mai sunt raioane pe etajul k
dacă numărul raionului de la etajul k este mai mic decât 4
atuncimai sunt raioane pe etajul kşi mergem la raionul următor
altfelnu mai sunt raioane pe etajul k
void succ(sir x,int k,int &as) (funcţia care determină dacă mai sunt raioane la etajul k){
if(x[k]<4) (dacă numărul raionului de la etajul k este mai mic decât 10)
{ (atunci)as=1; (mai sunt raioane pe etajul k)x[k]=x[k]+1 (şi mergem la raionul
următor)}
else (altfel)as=0; (nu mai sunt raioane pe etajul k)}
void succ(sir x,int k,int &as) (funcţia care determină dacă mai sunt raioane la etajul k){
if(x[k]<4) (dacă numărul raionului de la etajul k este mai mic decât 10)
{ (atunci)as=1; (mai sunt raioane pe etajul k)x[k]=x[k]+1 (şi mergem la raionul
următor)}
else (altfel)as=0; (nu mai sunt raioane pe etajul k)}
Cum se realizează afişarea
Cum se realizează afişarea
pentru i de la 1 la kse afişează x[i]
cursorul trece la linia următoare
pentru i de la 1 la kse afişează x[i]
cursorul trece la linia următoare
void afis(sir x, int k){int i;
for(i=1;i<=k;i++) (pentru i de la 1 la k)cout<<x[i]<<” ”; (se afişează x[i])
cout<<endl; (cursorul trece la linia următoare)
}
void afis(sir x, int k){int i;
for(i=1;i<=k;i++) (pentru i de la 1 la k)cout<<x[i]<<” ”; (se afişează x[i])
cout<<endl; (cursorul trece la linia următoare)
}
void valid(int &ev){
ev=1; (presupunem că orice alegere de haine ne convine)
}
void valid(int &ev){
ev=1; (presupunem că orice alegere de haine ne convine)
}
Pentru realizarea programului se parcurg următoarele etape:
declararea tuturor variabilelor care apar în cadrul programului principal
realizarea funcţiei succ realizarea funcţiei valid realizarea funcţiei afişrealizarea funcţiei bt programul principal care conţine rutina principală
Pentru realizarea programului se parcurg următoarele etape:
declararea tuturor variabilelor care apar în cadrul programului principal
realizarea funcţiei succ realizarea funcţiei valid realizarea funcţiei afişrealizarea funcţiei bt programul principal care conţine rutina principală
declararea tuturor variabilelor care apar în cadrul programului principal
declararea tuturor variabilelor care apar în cadrul programului principal
#include<iostream>Using namespace std;int x[100];int k, as,ev;
#include<iostream>Using namespace std;int x[100];int k, as,ev;
realizarea funcţiei succrealizarea funcţiei succ
void succ(int x[], int k, int&as){if(x[k]<4)
{as=1;x[k]=x[k]+1;
}else as=0;}
void succ(int x[], int k, int&as){if(x[k]<4)
{as=1;x[k]=x[k]+1;
}else as=0;}
Verific dacă mai sunt sau nu raioane pe etajul k
realizarea funcţiei validrealizarea funcţiei valid
void valid(int &ev){
ev=1;}
void valid(int &ev){
ev=1;}
Am găsit ce îmi place
realizarea funcţiei afişrealizarea funcţiei afiş
void afis(int x[],int k){int i;
for(i=1;i<=k;i++)cout<<x[i]<<" ";
cout<<endl;}
void afis(int x[],int k){int i;
for(i=1;i<=k;i++)cout<<x[i]<<" ";
cout<<endl;}
Afişarea rezultatului
programul principal care conţine rutina
principală
programul principal care conţine rutina
principalăvoid bt(){k=1;x[k]=0;while(k>0){ do
{succ(x,k,as);
if (as)valid(ev);
}while(as&&!ev);
void bt(){k=1;x[k]=0;while(k>0){ do
{succ(x,k,as);
if (as)valid(ev);
}while(as&&!ev);
if(as) if(k==5)afis(x,k);
else{
k=k+1;x[k]=0;}
else k=k-1;}}main(){ bt(); }
ComentariiComentarii
1. Dacă la etajul 1 ar fi fost n1 raioanela etajul 2 ar fi fost n2 raioane
.......la etajul k ar fi fost nk raioane
Funcţia succesor se modifică astfel:
1. Dacă la etajul 1 ar fi fost n1 raioanela etajul 2 ar fi fost n2 raioane
.......la etajul k ar fi fost nk raioane
Funcţia succesor se modifică astfel:
void succ(sir x, int k, int&as)
{if(x[k]<n[k])
{as=1;x[k]=x[k]
+1;}
else as=0;}
void succ(sir x, int k, int&as)
{if(x[k]<n[k])
{as=1;x[k]=x[k]
+1;}
else as=0;}
ComentariiComentarii
2. Dacă magazinul are m etaje atunci condiţia „dacă s-au făcut toate cumpărăturile” sau „s-a ajuns la ultimul etaj” se scrie
if(k==m)
2. Dacă magazinul are m etaje atunci condiţia „dacă s-au făcut toate cumpărăturile” sau „s-a ajuns la ultimul etaj” se scrie
if(k==m)
ComentariiComentarii
3. Dacă la fiecare etaj numărul de magazine este variabil (nu 4) condiţia de testare din funcţia succesor este
if(x[k]<n[k])
3. Dacă la fiecare etaj numărul de magazine este variabil (nu 4) condiţia de testare din funcţia succesor este
if(x[k]<n[k])
Atunci când nu există condiţii între componentele vectorului soluţie funcţia valid are forma:
void valid(int &ev){
ev=1;}
Atunci când nu există condiţii între componentele vectorului soluţie funcţia valid are forma:
void valid(int &ev){
ev=1;}
Atunci când componentele vectorului soluţie trebuie să fie distincte trebuie arătat că xkxi pentru i=1...k-1 se procedează astfel:
- se presupune că xk este diferit de toate elementele din faţa sa- se parcurg indicii 1...k-1 cu i- dacă xk nu este diferit de xi, atunci presupunerea este falsă
void valid(int &ev){
int i;ev=1;for(i=1;i<=k-1;i++)
if(!(x[k]!=x[i]))ev=0;
}
Atunci când componentele vectorului soluţie trebuie să fie distincte trebuie arătat că xkxi pentru i=1...k-1 se procedează astfel:
- se presupune că xk este diferit de toate elementele din faţa sa- se parcurg indicii 1...k-1 cu i- dacă xk nu este diferit de xi, atunci presupunerea este falsă
void valid(int &ev){
int i;ev=1;for(i=1;i<=k-1;i++)
if(!(x[k]!=x[i]))ev=0;
}
X[k] nu este diferit de x[i]
PermutăriPermutăriO permutare a unei mulţimi cu n elemente este un şir
de elemente obţinut prin schimbarea ordinii elementelor mulţimii date sau chiar mulţimea însăşi.
Ne gândim la generarea permutărilor atunci când se dă o mulţime cu n elemente ca date de intrare iar soluţia este sub forma de vector, tot cu n elemente, ale cărui componente sunt distincte şi aparţin mulţimii date.
Exemplu: Fie A={1,2,3}. Permutările mulţimii A sunt: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Fie A={a1, a2,…,am} o mulţime cu elemente de tip întreg. Trebuie determinate elementele mulţimii { y1, y2,…,ym }| ykA, k=1,2,...,m, pentru yiyj pentru ij}.
Deci, x=( x1, x2,…,xm) unde x{1,...,m}, elementele vectorului x trebuie să fie distincte.
O permutare a unei mulţimi cu n elemente este un şir de elemente obţinut prin schimbarea ordinii elementelor mulţimii date sau chiar mulţimea însăşi.
Ne gândim la generarea permutărilor atunci când se dă o mulţime cu n elemente ca date de intrare iar soluţia este sub forma de vector, tot cu n elemente, ale cărui componente sunt distincte şi aparţin mulţimii date.
Exemplu: Fie A={1,2,3}. Permutările mulţimii A sunt: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Fie A={a1, a2,…,am} o mulţime cu elemente de tip întreg. Trebuie determinate elementele mulţimii { y1, y2,…,ym }| ykA, k=1,2,...,m, pentru yiyj pentru ij}.
Deci, x=( x1, x2,…,xm) unde x{1,...,m}, elementele vectorului x trebuie să fie distincte.
Programul:Programul:
#include<iostream>using namespace std;int x[100],a[100];int i,k,m;int as,ev;
#include<iostream>using namespace std;int x[100],a[100];int i,k,m;int as,ev;
void succ(int x[], int k, int &as){if(x[k]<m)
{as=1;x[k]=x[k]+1;
}else as=0;}
void succ(int x[], int k, int &as){if(x[k]<m)
{as=1;x[k]=x[k]+1;
}else as=0;}
void valid(int x[], int k, int &ev){int i;ev =1;for(i=1;i<=k-1;i++)
if(!(x[i]!=x[k]))ev=0;
}
void valid(int x[], int k, int &ev){int i;ev =1;for(i=1;i<=k-1;i++)
if(!(x[i]!=x[k]))ev=0;
}
void afis(int x[], int k){int i;for(i=1;i<=k;i++)
cout<<a[x[i]]<<" ";cout<<endl;}
void afis(int x[], int k){int i;for(i=1;i<=k;i++)
cout<<a[x[i]]<<" ";cout<<endl;}
void bt(){k=1;x[k]=0;while(k>0)
{do{succ(x,k,as);
if(as) valid(x,k,ev);
}while(as&&!ev);
if(as) if(k==m) afis(x,k);else
{k=k+1; x[k]=0;}else k=k-1; } }
void bt(){k=1;x[k]=0;while(k>0)
{do{succ(x,k,as);
if(as) valid(x,k,ev);
}while(as&&!ev);
if(as) if(k==m) afis(x,k);else
{k=k+1; x[k]=0;}else k=k-1; } }
main(){cout<<"m=";cin>>m;for(i=1;i<=m;i++)
cin>>a[i];bt();}
main(){cout<<"m=";cin>>m;for(i=1;i<=m;i++)
cin>>a[i];bt();}
AranjamenteAranjamente
Se dau două mulţimi A={1,2,…,p} şi B={1,2,…,m} se cer toate funcţiile injective definite pe A cu valori în B. O astfel de problemă este una de generare a aranjamentelor de n luate cate p (An
p).
Exemplu: p=2, n=3. Avem (1,2), (2,1), (1,3), (3,1), (2,3), (3,2). De exemplu (2,1) este funcţia f:A→B dată astfel f(1)=2, f(2)=1. Avem relaţiile: =m(m-1)...(m-p+1).
Se dau două mulţimi A={1,2,…,p} şi B={1,2,…,m} se cer toate funcţiile injective definite pe A cu valori în B. O astfel de problemă este una de generare a aranjamentelor de n luate cate p (An
p).
Exemplu: p=2, n=3. Avem (1,2), (2,1), (1,3), (3,1), (2,3), (3,2). De exemplu (2,1) este funcţia f:A→B dată astfel f(1)=2, f(2)=1. Avem relaţiile: =m(m-1)...(m-p+1).
Avem relaţiile:Avem relaţiile:
)(
!
pm
mA pn
= m(m-1)...(m-p+1).
Se citesc m şi p. Să se genereze toate aranjamentele de m luate câte p.
Se observă că dacă se cunoaşte fiecare submulţime de p elemente a mulţimii de m elemente, atunci aranjamentele se pot obţine permutând în toate modurile posibile elementele unei astfel de mulţimi.
O soluţie este de forma: x1,x2,...xp unde x1,x2,...xpB. În plus x1,x2,...xp trebuie să fie distincte. O soluţie are p numere din mulţimea B şi numerele trebuie să fie distincte.
De aici rezultă că algoritmul este acelaşi ca la permutări, diferenţa fiind dată de faptul că soluţia are p numere, nu m ca în cazul permutărilor.
#include<iostream>Using namespace std;int x[100],a[100];int i,k,m,p;int as,ev;
void succ(int x[], int k, int &as){if(x[k]<m)
{as=1;x[k]=x[k]+1;
}else as=0;}
void valid(int x[], int k, int &ev){int i;ev =1;for(i=1;i<=k-1;i++)
if(x[k]==x[i])ev=0;
}
void afis(int x[], int k){int i;for(i=1;i<=k;i++)
cout<<a[x[i]]<<" ";cout<<endl;
}
se verifică dacă xkxi unde i=1,2,...,k-1
se afişează elementele din mulţimea A care corespund poziţiilor date de elementele
vectorului x
int main(void){cout<<"m=";cin>>m;for(i=1;i<=m;i++)
cin>>a[i];cout<<"p=";cin>>p;bt();}
Void bt(){k=1;x[k]=0;while(k>0)
{do
{succ(x,k,as);
if(as) valid(x,k,ev);}
while(as&&!ev);if(as)
if(k==p) afis(x,k);else{
k=k+1;x[k]=0;
}else k=k-1;
}}
CombinăriCombinări
Fiind dată o mulţime A cu n elemente, a combina elementele mulţimii în grupe de câte p<n elemente înseamnă a determina toţi vectorii cu p elemente ale căror componente aparţin mulţimii A şi sunt sortate crescător.
Ne gândim la generarea combinărilor atunci când se dă o mulţime cu n elemente ca date de intrare iar soluţia este sub forma unui vector cu p<n elemente, astfel încât să nu aibă importanţă ordinea pe care o au în cadrul şirului. Componentele sunt sortate crescător şi aparţin mulţimii date.
Fie A={1,2,3}. Combinările mulţimii A în grupe de câte două elemente sunt (1,2), (1,3), (2,3).
Fiind dată o mulţime A cu n elemente, a combina elementele mulţimii în grupe de câte p<n elemente înseamnă a determina toţi vectorii cu p elemente ale căror componente aparţin mulţimii A şi sunt sortate crescător.
Ne gândim la generarea combinărilor atunci când se dă o mulţime cu n elemente ca date de intrare iar soluţia este sub forma unui vector cu p<n elemente, astfel încât să nu aibă importanţă ordinea pe care o au în cadrul şirului. Componentele sunt sortate crescător şi aparţin mulţimii date.
Fie A={1,2,3}. Combinările mulţimii A în grupe de câte două elemente sunt (1,2), (1,3), (2,3).
#include<iostream>using namespace std;int x[100],a[100];int i,k,m,p;int as,ev;
void succ(int x[], int k, int &as){if(x[k]<m)
{as=1;x[k]=x[k]+1;
}else as=0;}
void valid(int x[], int k, int &ev){int i;ev =1;for(i=1;i<=k-1;i++)if((k>=2)&&!(a[x[k]]>a[x[k-1]])) ev=0;}
void afis(int x[], int k){int i;for(i=1;i<=k;i++)
cout<<a[x[i]]<<" "; cout<<endl;
}
se verifică dacă componentele aparţin mulţimii date şi sunt
sortate crescător
se afişează elementele din mulţimea A care corespund poziţiilor date de elementele
vectorului x
main(){cout<<"m=";cin>>m;for(i=1;i<=m;i++)
cin>>a[i];cout<<"p=";cin>>p;bt();}
void bt(){k=1;x[k]=0;while(k>0)
{do
{succ(x,k,as);
if(as) valid(x,k,ev);}
while(as&&!ev);if(as)
if(k==p) afis(x,k);else{
k=k+1;x[k]=0;
}else k=k-1; }
}
