Functiile

[•RazvanInfo10]

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;
}

[•rares96cheseli]

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)
{
       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;
            }
}

[•RazvanInfo10]

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)

[•rares96cheseli]

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.

[•RazvanInfo10]

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.

[•rares96cheseli]

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.

[•PlayLikeNeverB4]

sau asa "[ nobbc ]a[ i ][ /nobbc ]" (fara spatii)

[•RazvanInfo10]

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.

[•rares96cheseli]

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).

[•RazvanInfo10]

Acolo st [ 1 ] 1 de acolo este top?, iar viz [ 1 ] = este i, sau ma insel ?

[•rares96cheseli]

Nu, nu te inseli

[•RazvanInfo10]

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 )

[•rares96cheseli]

http://www.infoarena.ro/forum/index.php?topic=9064.0 la sfarsitul acelui topic sunt niste imagini. Poate te ajuta sa intelegi mai bine

[•RazvanInfo10]

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