•RazvanInfo10
Strain
Karma: 2
Deconectat
Mesaje: 32
|
|
« : Octombrie 14, 2013, 12:52:05 » |
|
Salut, si imi cer scuze pentru acest topic(dar nu inteleg o problema) Metoda Backtracking:
presupunem: n=2
#include<iostream> using namespace std; int a[20], n, viz[20]; void PrintSol() { int i; for (i = 1; i <= n; i++) { cout << a << " "; } cout << "\n"; cout<<endl; } void Back(int top) { int i; if (top == n + 1) PrintSol(); else for (i = 1; i <=n; i++) if (viz==0) { viz = 1; a[top] = i; Back(top + 1); // aici: pentru i=1, top va deveni 2,pentru i=2, top va deveni 3, si se activeaza din nou functia Back(), nu? Eu nu inteleg, a[1]=1,a[2]=2 corect ? dupaia se activeaza PrintSol(), si imi afiseaza 1 2, dar dupaia nu se opreste functiile(ambele)?Cum face din nou sa imi apare si 2 1 ? Nu pot intelege, si profesorul de Informatica nu stie pe ce "planeta este" a spus ca el a terminat matematica(nu stie chestii dinastea).Multumesc viz = 0; } } int main() { cout << "n = "; cin >> n; cout<<"da ce plm"<<endl; Back(1); system("pause"); return 0; }
|
|
|
Memorat
|
|
|
|
•rares96cheseli
Client obisnuit
Karma: 45
Deconectat
Mesaje: 60
|
|
« Răspunde #1 : Octombrie 14, 2013, 13:49:28 » |
|
In functia de back, dupa ce apelezi back( top+1 ) fa-l pe viz[ i ] 0. Adica fa functia de back asa void back(int top) { if ( top>n) print(); for ( int i=1; i<=n; ++i) if (viz[ i ]==0 ) { st[ top ]=i; viz[ i ]=1; back( top+1 ); viz[ i ]=0; } }
|
|
|
Memorat
|
|
|
|
•RazvanInfo10
Strain
Karma: 2
Deconectat
Mesaje: 32
|
|
« Răspunde #2 : Octombrie 14, 2013, 14:02:08 » |
|
am inteles, dar nu inteleg asta: de ex: cand incepe for-ul: for(i=1;i<=n;i++) , pentru i=1 , se executa programul si cand ajunge la: back(top+1) nu se apeleaza din nou functia de la inceput ? sau se activeaza DUPA ce se termina for-ul ?Si cand se apeleaza functia print(); --> afiseaza rezultatele, si dupaia cum face sa revina la functia asta back() , pentru a continua Combinarile(ex: n=2 , 1 2 si 2 1)
|
|
|
Memorat
|
|
|
|
•rares96cheseli
Client obisnuit
Karma: 45
Deconectat
Mesaje: 60
|
|
« Răspunde #3 : Octombrie 14, 2013, 14:09:02 » |
|
Ba da, cand se ajunge la back(top+1) functia se apeleaza de la inceput. Apropo, pt multimea {1, 2}, ai doar combinarea 1 2 ( daca vrei combinari de 2 luate cate 2). Pt combinari trebuie modificata putin functia de back.
|
|
|
Memorat
|
|
|
|
•RazvanInfo10
Strain
Karma: 2
Deconectat
Mesaje: 32
|
|
« Răspunde #4 : Octombrie 14, 2013, 14:38:52 » |
|
codu, ce l-am aratat mai sus merge, daca scriu pentru n=2 imi afiseaza: 1 2 2 1
Dar nu inteleg mecanismu...si da in if era viz , nu am copiat eu bine.
|
|
|
Memorat
|
|
|
|
•rares96cheseli
Client obisnuit
Karma: 45
Deconectat
Mesaje: 60
|
|
« Răspunde #5 : Octombrie 14, 2013, 17:46:32 » |
|
Cand mai postezi cod posteaza-l intre [ code ] [ / code ] (fara spatii). Si cand mai scri indici, scrie asa "a[ i ]". Daca scrii fara spatii, iti transforma scrisul in scris italic.
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #6 : Octombrie 14, 2013, 18:29:05 » |
|
sau asa "[ nobbc ]a[ i ][ /nobbc ]" (fara spatii)
|
|
|
Memorat
|
|
|
|
•RazvanInfo10
Strain
Karma: 2
Deconectat
Mesaje: 32
|
|
« Răspunde #7 : Octombrie 14, 2013, 19:02:36 » |
|
am inteles,codul normal:
#include<iostream> using namespace std; int a[20], n, viz[20]; void PrintSol() { int i; for (i = 1; i <= n; i++) { cout << a[ i ]<< " "; } cout << "\n"; cout<<endl; } void Back(int top) { int i; if (top == n + 1) PrintSol(); else for (i = 1; i <=n; i++) if (viz[ i ]==0) { viz[ i ] = 1; a[top] = i; Back(top + 1); viz[ i ] = 0; } } int main() { cout << "n = "; cin >> n; Back(1); system("pause"); return 0; }
acum este ok ? pentru n=2: imi apare: 1 2 2 1 si nu inteleg cum s-a ajuns la rezultate, am o carte ce nu explica prea bine functiile.Daca ma puteti ajuta.
|
|
|
Memorat
|
|
|
|
•rares96cheseli
Client obisnuit
Karma: 45
Deconectat
Mesaje: 60
|
|
« Răspunde #8 : Octombrie 14, 2013, 21:44:20 » |
|
Pt n=2 nu e foarte greu de inteles cum se comporta algoritmul. O sa incerc sa iti explic
back(1) { pt i=1 se executa urmatoarele: { st[1]=1; viz[1]=1; back(2) { st[2]=2; viz[2]=1; back(3) afisare(); viz[2]=0; } viz[1]=0; }
pt i=2 se executa urmatoarele: { st[1]=2; viz[2]=1; back(2) { st[2]=1; viz[1]=1; back(3) afisare(); } viz[2]=0; } viz[1]=0; } Cam asta ar fi. Sper sa nu fi gresit ceva. Ar fi bine sa incerci si niste probleme de backtracking din arhiva educationala ( generare de permutari, cimbinari, submultimi).
|
|
|
Memorat
|
|
|
|
•RazvanInfo10
Strain
Karma: 2
Deconectat
Mesaje: 32
|
|
« Răspunde #9 : Octombrie 15, 2013, 11:28:19 » |
|
Acolo st [ 1 ] 1 de acolo este top?, iar viz [ 1 ] = este i, sau ma insel ?
|
|
« Ultima modificare: Octombrie 15, 2013, 12:09:50 de către Razvan »
|
Memorat
|
|
|
|
•rares96cheseli
Client obisnuit
Karma: 45
Deconectat
Mesaje: 60
|
|
« Răspunde #10 : Octombrie 15, 2013, 18:03:40 » |
|
Nu, nu te inseli
|
|
|
Memorat
|
|
|
|
•RazvanInfo10
Strain
Karma: 2
Deconectat
Mesaje: 32
|
|
« Răspunde #11 : Octombrie 15, 2013, 20:53:11 » |
|
eu credeam ca face asa: dupa ce se executa Back(1), pana se intalneste cu Back(2)--> aici, nu se apeleaza din nou functia, si intr iara prin for(int i=1;i<=n;i++)...etc...Daca ar fii asa, pentru: 1 2 --> ar fii corect 2 1 --> nu ar fii corect, pentru ca: a[2]=2 , iar a[2]=2 ? asa imi da mie pe hartie, unde gresesc?Eu fac o greseala undeva, unde mi se duce tot algoritmu )
|
|
|
Memorat
|
|
|
|
|
•RazvanInfo10
Strain
Karma: 2
Deconectat
Mesaje: 32
|
|
« Răspunde #13 : Octombrie 15, 2013, 21:11:10 » |
|
Perfect, am inteles unde tot greseam.Iti multumesc mult de tot pentru tot ajutorul acordat, si pentur ca ti-ai batut capu cu un incepator.Multa bafta la scoala
|
|
|
Memorat
|
|
|
|
|