Imprimă pagina - Backtracking

Titlul: Backtracking
Scris de: Stratulat Alexandru din Ianuarie 17, 2012, 21:41:35

Buna. Sunt destul de incepator in programere si anume am inceput serios sa lucrez la informatica de 3-4 luni.
Am o problema la metoda backtraking pe care nu am nici o idee cum sa o fac si aceea este:
Se da un numar N natural par. Sa se determine toate sirurile de N paranteze care se inchid corect.
De exemplu: N=6. Se va afisa:
( ( ( ) ) ), ( ( )( ) ), ( ) ( ) ( ), ( ) ( ( ) ), ( ( ) ) ( )
Va rog sa imi spuneti mai intai un algortim pe care ar trebui sa il urmez si o secventa de cod cheie.
Codul de asemenea sa fie in C++.

Titlul: RÄƒspuns: Backtracking
Scris de: Sorin Rita din Ianuarie 18, 2012, 00:27:42

Pai ai N/2 paranteze de fiecare fel. Ca sa iti fie mai usor poti sa pui in loc de paranteza deschisa cifra 0 si 1 pt cele inchise. Si acum e destul de simplu. Trebuie sa ai grija ca numarul de paranteze deschise/inchise sa nu fie mai mare ca N/2 si la fiecare pas numarul celor inchise sa fie mai mic sau egal cu numarul celor deschise.

Titlul: RÄƒspuns: Backtracking
Scris de: Stratulat Alexandru din Ianuarie 18, 2012, 17:37:28

Am incercat sa fac problema si nu imi afiseaza nimic. Iata codul pe care l-am scris.

Cod:

#include<fstream>
using namespace std;

 int n,ST[100],as,ev,k,y=0,l=0,z=0;

ifstream f("paranteze.in");
ofstream g("paranteze.out");

void init()
{
    ST[k]=-1;

}

  void succ()
  {

      if(ST[k]<2)
      {
         ST[k]++;
      as=1;
      }
  else as=0;

  }

void valid()
{
    ev=1;
     for(int i=1;i<=k;i++)
{
    if(ST[i]==0)
    {
            y++;
    for(int j=i+1;j<=k;j++)
{
    if(ST[j]==1)
    l++;}}
    else z++;

}
if(l==0)
ev=0;
if(z!=y!=n/2)
ev=0;
}

void tipar()
{
    for(int i=1;i<=k;i++)
    g<<ST[i]<<" ";
g<<endl;
}

int sol()
{

return (k==n);
}

void back()
{
    k=1;
    init();
    while(k)
    {
        do{
                succ();
                if(as)
        valid();

}
       while(as && !ev);
    if(as)   if(sol())
    tipar();
    else{
    k++;
    init();
    }
    else k--;
    }

}

int main()
{
    f>>n;
    back();
f.close();
g.close();
return 0;
}

Titlul: RÄƒspuns: Backtracking
Scris de: Simoiu Robert din Ianuarie 18, 2012, 17:46:43

Pune tagurile code ca sa se vada codul ... altfel nu-l putem citi :P.

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Stratulat Alexandru din Ianuarie 17, 2012, 21:41:35