Backtacking - Permutari

[•casz]

Salut, am si eu o problema si as vrea daca se poate sa mi-o explice cineva.

As vrea sa imi explice cineva cum se trece prin fiecare pas din problema.

De exemplu, pentru n=3. Ce se intampla in cod, cum functioneaza? cum circula 3-ul asta prin problema.

Cod:

#include<iostream>
using namespace std;

const MAX=20;
int n,v[MAX];

int valid(int k);
int solutie(int k);
void afisare(int k);
void BK(int k);

int valid(int k)

{
int i;
for(i=1; i<k; i++)
if(v[i]==v[k])
return 0;
return 1;
}

int solutie(int k)

{
if(k==n)
return 1;
return 0;
}

void afisare(int k)
{
int i;
for(i=1; i<=k; i++)
cout<<v[i]<<"";
cout<<endl;
}


void BK(int k)

{
int i;

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

{
v[k]=i;
if(valid(k))

{
if(solutie(k))
afisare(k);

else

BK(k+1);
}
}
}

int main()

{
cout<<"n=";
cin>>n;

BK(1);
return 0;

}

[•casz]

Nu stie nimeni?

[•wefgef]

Foloseste tagul "code" si indenteaza daca vrei sa iti citeasca cineva sursele .

[•casz]

nu stie nimeni:))

[•PlayLikeNeverB4]

Stie multa lume de pe infoarena, dar nimeni nu e dispus sa isi faca un scop in viata din a-ti citi sursele. Ori scrii o sursa cat de cat lizibila, ori nu te va ajuta nimeni.

[•CosminRusu]

Salut, am si eu o problema si as vrea daca se poate sa mi-o explice cineva.

As vrea sa imi explice cineva cum se trece prin fiecare pas din problema.

De exemplu, pentru n=3. Ce se intampla in cod, cum functioneaza? cum circula 3-ul asta prin problema.

Cod:

#include<iostream>
using namespace std;

const MAX=20;
int n,v[MAX];

int valid(int k);
int solutie(int k);
void afisare(int k);
void BK(int k);

int valid(int k)

{
int i;
for(i=1; i<k; i++)
if(v[i]==v[k])
return 0;
return 1;
}

int solutie(int k)

{
if(k==n)
return 1;
return 0;
}

void afisare(int k)
{
int i;
for(i=1; i<=k; i++)
cout<<v[i]<<"";
cout<<endl;
}


void BK(int k)

{
int i;

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

{
v[k]=i;
if(valid(k))

{
if(solutie(k))
afisare(k);

else

BK(k+1);
}
}
}

int main()

{
cout<<"n=";
cin>>n;

BK(1);
return 0;

}

In primul rand puteai specifica de la inceput ca este vorba despre problema generarii permutarilor de N elemente (sper ca stiai lucrul asta), astfel nu le mai dadeai dureri de cap oamenilor care nu stau sa iti citeasca postul, ci scaneaza putin sursa si se sperie ).
In al doilea rand ar trebui sa te familiarizezi cu recursivitatea ca sa intelegi ce se intampla acolo, in sursa ta. Nu cred ca daca eu sau altcineva ti-ar spune pasii algoritmului ai invata foarte mult. Fa putin debug! Afiseaza-ti cand bagi in stiva nivelul ei si elementul curent. Uite aici poti rezolva problema asta (http://www.infoarena.ro/problema/permutari) si, fiind din arhiva educationala, ai acces la sursa oficiala cat si a tuturor userilor de top, ai comentarii din care sa intelegi ce si cum face algoritmul in cauza, plus ca ai o groaza de alte site-uri de unde poti afla informatii cate vrei!
In incheiere daca vrei sa te pui la punct cu metoda backtracking iti sugerez, pentru inceput, sa faci atat problema de mai sus cat si urmatoarele :
http://www.infoarena.ro/problema/submultimi
http://www.infoarena.ro/problema/combinari
Enjoy!

[•casz]

Problema e luata dintr-o carte si pusa aici. Daca va bagati putin ochii in ea, o sa descoperiti ca e usor de citit. Cosmin, multumesc de materiale, o sa ma uit pe ele sa vad ce si cum. Si inca consider ca daca mi-ar explica cineva ce am cerut, as intelege. Daca ar putea sa-si faca cineva timp sa se uite putin pe cod as fi recunoscator.

[•costi_.-.]

Sper sa te ajute   .
http://www.mediafire.com/download/uafjazw9fabwgbc/bk.zip

[•casz]

Cu intarziere, dar iti multumesc pentru ajutor!