Imprimă pagina - Backtacking

Titlul: Backtacking - Permutari
Scris de: Coman Sorin din August 03, 2013, 19:53:35

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;

}

Titlul: Răspuns: Backtacking - Permutari
Scris de: Coman Sorin din August 05, 2013, 11:59:37

Nu stie nimeni?

Titlul: Răspuns: Backtacking - Permutari
Scris de: Andrei Grigorean din August 05, 2013, 12:14:42

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

Titlul: Răspuns: Backtacking - Permutari
Scris de: Coman Sorin din August 06, 2013, 14:48:15

nu stie nimeni:))

Titlul: Răspuns: Backtacking - Permutari
Scris de: George Marcus din August 06, 2013, 16:09:12

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.

Titlul: Răspuns: Backtacking - Permutari
Scris de: Cosmin Rusu din August 06, 2013, 17:21:49

Citat din mesajul lui: Coman Sorin din August 03, 2013, 19:53:35

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!

Titlul: Răspuns: Backtacking - Permutari
Scris de: Coman Sorin din August 08, 2013, 22:48:55

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.

Titlul: Răspuns: Backtacking - Permutari
Scris de: Costinnel din August 09, 2013, 00:29:41

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

Titlul: Răspuns: Backtacking - Permutari
Scris de: Coman Sorin din August 22, 2013, 12:34:31

Cu intarziere, dar iti multumesc pentru ajutor!

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Coman Sorin din August 03, 2013, 19:53:35