[Rezolvarea mea :]

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!

Am inteles si sunt de acord. Nu voi mai folosi astfel de metode. Dar nu sunt de acord sa fiu depunctat pentru o problema care functioneaza corect!
Din ce am observat, s[-1] nu mai este NULL doar in cazul in care se mai declara si alte caractere sau siruri de caractere. In cazul numerelor (declarare de tip int, float, double) acestea nu afecteaza programul.

[un singur sir de caractere]

Ok, am inteles dar totusi, in problema pe care ea a formulat-o se declara un singur sir de caractere. Atat!

EDIT: Sa zicem ca eram la olimpiada (bineinteles ca nu se da o asemenea banalitate la olimpiada, dar ca idee). Eu cu acest cod luam tot 100 puncte, desi sustinem ca este incorect, si altul cu o rezolvare corecta lua tot 100 puncte.

Spune-mi te rog atunci, de ce urmatorul cod afiseaza mesajul "Este NULL!"?

Cod:

#include <string.h>
#include <iostream>
using namespace std;

int main()
{
    char s[100]="test";
    if(s[-1]==NULL)
      cout<<"Este NULL!";
    else
      cout<<"Nu este NULL!";
    return 0;
}

[NULL]

Salut,
Astazi am avut teza la informatica. Am primit o problema banala, pe care am rezolvat-o cred eu corect :
"Se citeste de la tastatura un sir de caractere (doar litere mici). Sa se modifice litera de la inceputul fiecarui cuvant in litera mare."
Rezolvarea mea suna astfel :

Cod:

//declarare, citire sir
for(i=0;i<strlen(s);i++)
  if(s[i-1]==' ' || s[i-1]==NULL)
     s[i]=toupper(s[i])

Problema este ca, pentru a rezolva si primul cuvant din propozitie am pus conditia || s[i-1]==NULL, deoarece inaintea primei litere nu se afla nimic, adica NULL.
Dupa ce i-am explicat profesoarei modul meu de rezolvare a problemei mi-a spus ca este complet gresit, desi eu am demonstrat ca rezolvarea mea este corecta. Motivatia ei a fost faptul ca s[-1] este in afara zonei de memorie si ca este o simpla coincidenta faptul ca am gasit NULL pe s[-1].
Nu sunt de acord, deoarece am verificat si am observat ca un sir de caractere este delimitat intotdeauna de NULL, mai exact pe s[-1] intotdeauna va exista NULL.
Ce parere aveti? Este gresita rezolvarea mea?
Multumesc!