Titlul: Functiile Scris de: Razvan din 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; } Titlul: Răspuns: Functiile Scris de: Rares Cheseli din 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
Cod: void back(int top) Titlul: Răspuns: Functiile Scris de: Razvan din 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) Titlul: Răspuns: Functiile Scris de: Rares Cheseli din 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.
Titlul: Răspuns: Functiile Scris de: Razvan din 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. Titlul: Răspuns: Functiile Scris de: Rares Cheseli din 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.
Titlul: Răspuns: Functiile Scris de: George Marcus din Octombrie 14, 2013, 18:29:05 sau asa "[ nobbc ]a[ i ][ /nobbc ]" (fara spatii) :)
Titlul: Răspuns: Functiile Scris de: Razvan din 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. Titlul: Răspuns: Functiile Scris de: Rares Cheseli din 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). Titlul: Răspuns: Functiile Scris de: Razvan din Octombrie 15, 2013, 11:28:19 Acolo st [ 1 ] 1 de acolo este top?, iar viz [ 1 ] = este i, sau ma insel ?
Titlul: Răspuns: Functiile Scris de: Rares Cheseli din Octombrie 15, 2013, 18:03:40 Nu, nu te inseli
Titlul: Răspuns: Functiile Scris de: Razvan din 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 :)) Titlul: Răspuns: Functiile Scris de: Rares Cheseli din Octombrie 15, 2013, 20:58:52 http://www.infoarena.ro/forum/index.php?topic=9064.0 la sfarsitul acelui topic sunt niste imagini. Poate te ajuta sa intelegi mai bine
Titlul: Răspuns: Functiile Scris de: Razvan din 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 :D
|