[C++] Permutari a n numere naturale

[CoSmE]

Salutare B-Zone, sunt nou dsr vreau sa va prezint algoritmul de calcul a permutarilor a n numere naturale folosind metoda backtracking.

#include<iostream> //Permutari de n numere intregi. Metoda backtracking.
using namespace std;
typedef int stiva[30]; //Declaram tipul stiva ca un vector de numere intregi.
int n,k,ev,as,nr=0; //Declaram variabilele intregi n,k,ev,as si nr care este initializat cu 0.
stiva st; //Declaram variabila st de tipul stiva.

void init() //Incepe subprogramul init care initializeaza stiva.
{
st[k]=0; //st in pozitia k primeste 0.
}

int succesor() //Incepe subprogramul succesor care mai adauga o pozitie in stiva.
{
if (st[k]<n) //Daca st in pozitia k este mai mic ca si n va executa.
{
st[k]=st[k]+1;return 1; // st in pozitia k se va incrementa cu 1 si va returna valoarea 1.
}
else return 0; //Daca st in pozitia k nu este mai mare ca n va returna 0.
}

int valid() //Incepe subprogramul valid care verifica daca variabila pusa este corecta.
{
for(int i=1;i<k;i++) //Functie iterativa cu i de la 1 la k.
if(st[k]==st[i])
return 0; //Daca st in pozitia k este egala cu pozitia i atunci returneaza 0.
return 1;
}

int solutie() //Incepe subprogramul solutie si arata daca mai putem sa punem valori in stiva.
{
return k==n; //Returneaza valoarea k=n.
}

void tipar() //Incepe subprgoramul tipar si scrie solutiile.
{
for(int i=1;i<=n;i++) //Va scrie de n ori st[i] si la fiecare solutie va incrementa nr.
cout<<st[i]<<" ";
cout<<endl;

nr++;
}

void bt() //Subprogram principal bt.
{
k=1; //Intitializeaza k cu 1.
init(); //Apeleaza subprogramul init.
while(k>0) //Iterativa cu pas initial pana cand k mai mic sau egal cu 0.
{
as=1; ev=0; //Initializeaza as cu 1 si ev cu 0.
while(as && !ev) //Iterativa cu pas intial cat timp as este egal cu 1 si ev este egal cu 0.
{
as=succesor(); //As primeste valoarea returnata de apelarea subprogramului succesor.
if(as) ev=valid(); //Daca as este egal cu 1 ev va primi valoarea returnata de apelarea subprogramului valid.
}
if(as)//dava as==1
if(solutie()) tipar(); //Daca valoarea returnata de apelarea subprogramului solutie este 1 va apela subprogramul tipar.
else
{
k++; init(); //Daca nu este va incrementa k si va apela subprogramul init din nou.
}
else k--;
}
}

int main() //Programul principal.
{
cout<<"n="; cin>>n; //Citeste variabila n
bt();cout<<nr<<" solutii"; //Apeleaza subprogramul bt si scrie numarul de solutii.
}

Pentru sfaturi/nelamurir/critici puteti lasa un reply.

Edited November 25, 2014 by CoSmE

[eS Arthur]

Frumos, de aste facem si noi la scoala dar ai explica bine.

[LloydSiLENT]

O voi folosi , multumesc , felicitari !

[AIM Katzuno Valoare]

Topic Closed, multumim pentru informatii.