[Backtracking] Este gresita aceasta metoda?

[•ionutzm05]

Salutare,
Sunt in clasa a 11-a si am inceput sa studiem metoda Backtracking. Eu personal am invatat aceasta metoda anul trecut, la pregatirea pentru olimpiada. Bineinteles, prima problema pe care am rezolvat-o la clasa a fost problema permutarilor. Rezolvarea mea difera mult de cea a profesoarei, de aceea am intrebat-o daca rezolvarea mea este buna. Mi-a raspuns ca rezolvarea mea este incorecta si ca "este din noroc" faptul ca functioneaza la aceasta problema. Motivatia a fost ca eu in functia main folosesc un if pentru a verifica daca am succesor iar teoretic aceasta ar trebui sa fie folosita cu do while.
Probabil nu ati inteles mult din exprimarea mea dar va postez ambele rezolvari (a mea si a profesoarei) si doresc sa imi spuneti daca rezolvarea mea este incorecta.
Rezolvarea mea :

Cod:

#include <iostream>
using namespace std;

int st[100],n;

void init(int k)
{
    st[k]=0;
}

int succesor(int k)
{
    if(st[k]<n)
    {
        st[k]++;
        return 1;
    }
    else
        return 0;
}

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

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

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
      cout<<st[i]<<" ";
    cout<<'\n';
}

int main()
{
    int k;
    cout<<"n=";
    cin>>n;
    k=1;
    init(k);
    while(k>0)
    {
        if(succesor(k)) ***
        {
            if(valid(k))
            {
                 if(solutie(k))
                    tipar(k);
                 else
                 {
                    k++;
                    init(k);
                 }
            }
        }
        else
            k--;
    }
    return 0;
}

Rezolvarea profesoarei :

Cod:

#include <iostream>
using namespace std;

int st[100],k,n;

void init(int st[],int k)
{
    st[k]=0;
}

void succesor(int st[],int k, int &as)
{
    if(st[k]<n)
    {
        as=1;
        st[k]++;
    }
    else
        as=0;
}

void valid(int st[],int k,int &ev)
{
    int i;
    ev=1;
    for(i=1;i<k;i++)
    {
        if(st[k]==st[i])
            ev=0;
    }
}

int solutie(int st[],int k)
{
    if(k==n)
        return 1;
    else
        return 0;
}

void tipar(int st[],int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<st[i]<<" ";
    cout<<'\n';
}

int main()
{
    int as,ev;
    cout<<"n=";
    cin>>n;
    k=1;
    init(st,k);
    while(k>0)
    {
        do
        {
            succesor(st,k,as);
            if(as==1)
                valid(st,k,ev);
        }
        while(!(as==0||(as==1&&ev==1)));
        if(as==1&&ev==1)
        {
            if(solutie(st,k)==1)
              tipar(st,k);
            else
            {
                k++;
                init(st,k);
            }
        }
        else
            k--;
    }
}

Multumesc!

[•AlexandruValeanu]

Informatica nu prea functioneaza pe noroc asa ca ma surprinde raspunsul profesoarei tale. Rezolvarea ta este corecta...ia 100p pe problema din arhiva educationala: http://www.infoarena.ro/job_detail/1001326. Succes!