Question

in C++ !!!Abordare Backtracking !!!  Problema celor n paranteze, n - apartine numerelor naturale pare diferite de 0.Se cerre sa se genereze toate sirurile de paranteze care se imperecheaza corect.  in C++ !!!Abordare Backtracking !!!

Answer 1

 Cam asta ar fi programul(nu l-am compilat,dar vezi si tu...) :

#include<iostream>
using namespace std;
int n,st[1000];

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

int valid(int k)
{
  return 1;
}

int solutie(int k)
{
   if(k!=n) return 0;
   int zero=0,unu=1;
   for(int i=1;i<=k;i++)
      if(st[k]==0) zero++;
       else unu++;
   if(zero!=unu) return 0;
  else return 1;
}

void afiseaza(int k)
{
   for(int i=1;i<=k;i++)
     if(st[i]==0) cout<<'(';
      else cout<<')';
   cout<<'\n';
}

void back(int k)
{
   st[k]=-1;
   while(succesor(k))
     if(valid(k))
       if(soluti(k)) afiseaza(k);
       else back(k+1);
}

int main()
{
  cout<<"n="; cin>>n;
  if(n%2==1) {cout<<"nu exista o astfel de pereche"; return 0;}
  back(1);
  return 0;
}