Advertisement
Dani_info

problema paranteze - backtracking

Dec 7th, 2019
128
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. // ( -> 1
  6. // ) -> 2
  7.  
  8. int v[12], n;
  9.  
  10. void init (int k){
  11.     v[k]=0;
  12. }
  13.  
  14. int solutie (int k){
  15.     return k==n+1;
  16. }
  17.  
  18. int existaSuccesor (int k){
  19.     if (v[k]<2){
  20.         v[k]++;
  21.         return 1;
  22.     }
  23.     return 0;
  24. }
  25.  
  26. void tipar (){
  27.     for (int i=1; i<=n; i++){
  28.         if (v[i]==1) cout<<"(";
  29.         if (v[i]==2) cout<<")";
  30.     }
  31.     cout<<endl;
  32. }
  33.  
  34. int valid (int k){
  35.     int p1=0, p2=0;
  36.     for (int i=1; i<=k; i++){
  37.         if (v[i]==1) p1++;
  38.         if (v[i]==2) p2++;
  39.     }
  40.     if (p1>n/2) return 0;
  41.     if (p2>n/2) return 0;
  42.     if (v[1]==2) return 0;
  43.     if (v[n]==1) return 0;
  44.     if (v[k]==2){
  45.         if (p1==p2-1)
  46.            return 0;
  47.     }
  48.     return 1;
  49. }
  50.  
  51. void back (int k){
  52.     if(solutie(k)) tipar();
  53.     else{
  54.         init(k);
  55.         while (existaSuccesor(k)){
  56.             if (valid(k)) back(k+1);
  57.         }
  58.     }
  59. }
  60.  
  61. int main()
  62. {
  63.     cout<<"n="; cin>>n;
  64.     back (1);
  65.     return 0;
  66. }
Advertisement
RAW Paste Data Copied
Advertisement