SHARE
TWEET

Untitled

a guest Oct 21st, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. RUTINA BKTR  ( construieste solutia unui enunt utilizand un vector manevrat
  4.                             cu strategie stiva )
  5.  
  6. -top=1
  7. - initializeza  stiva S la varf top=1
  8. - atata timp cat stiva nu este vida executa
  9.             - cauta in multimea de candidati ai locului curent un prim succesor admisibil
  10.             - daca am gasit succesor admisibil atunci executa
  11.                                                                 - daca am solutie atunci executa
  12.                                                                                                         - tiparire
  13.                                                                                                         sf_executa
  14.                                                                                               altfel executa
  15.                                                                                                          - top=top+1
  16.                                                                                                          - initializeza  stiva S la varf top=1
  17.                                                                                                         sf_executa
  18.                                                                                sf_executa
  19.                                                                 altfel  executa
  20.                                                                              -top=top-1
  21.                                                                         sf_executa
  22.                                                       sf_executa atata timp
  23.  
  24. rutina pentru a fi  pusa in practica trebuie sa utilizeze intrumentele :
  25.  
  26. 1) initializeaza S la varf curent
  27.     functia init(S,top) depune stiva o valoare de la care prin incrementare ajung
  28.     pe prim candidat din multimea arondatilor locului
  29.  
  30. 2) succesor la varf curent pe stiva
  31.      functia succ(S,top) depisteaza existenta unui succesor in multimea
  32.      de candidati arondati locului curent . In caz afirmativ functie succ(S,top)
  33.      si depune acel candidat iar ca rezultat intoarce 1 TRUE
  34.      in caz negativ intoare 0 FALSE
  35.  
  36. 3) validarea la varf curent pe stiva
  37.     functia succ(S,top) intoarece 1 TRUE sau 0 FALSE dupa cum candidatul
  38.     depistat si depus de succ(S,top) este sau nu admisibil in baza unor conditii
  39.     din anunt
  40.  
  41. 4) solutie
  42.    functia solutie (S,top) intoarece 1 TRUE sau 0 FALSE dupa cum
  43.    pe stiva am sau solutie
  44.  
  45. 5) tipar
  46.    functia tipar (S,top) tipareste solutia adica continutul stivei din baza pana in varf
  47.  
  48. ===============================================
  49. Aplicatie :
  50. Problema P(n)  problema generarii permutarilor unei multimi cu n componente
  51. ( prezentarii tuturor modurilor de aranjare a elementelor ei )
  52.  
  53. n=3 M={1,2,3}
  54. Solutii  :
  55. 1 2 3
  56. 1 3 2
  57. 2 1 3
  58. 2 3 1
  59. 3 1 2
  60. 3 2 1
  61.  
  62. Sunt intrunite conditiile unui enunt incadrabil in clasa problemelor BKTR
  63. 1) Se cer toate solutiile
  64. 2) Orice solutie este reprezentabila sub forma de forma de vector
  65. 3) Pentru toate locurile din solutie sunt multimi de candidati
  66.     A1={1,2,3}
  67.     A2={1,2,3}
  68.     A3={1,2,3}
  69.  
  70. */
  71. #include<iostream>
  72. using namespace std;
  73. int n;
  74. int S[100];
  75. int top;
  76.  
  77. int init(int stiva[],int top)
  78. { stiva[top]=0;}
  79.  
  80. int succ(int stiva[],int top)
  81. { if (stiva[top]<n)  {
  82.                             stiva[top]=stiva[top]+1;
  83.                             return 1;
  84.                             }
  85.   return 0;}
  86.  
  87. int valid(int stiva[],int top)
  88. { if (top==1)   return 1;
  89.    int i;
  90.    i=1;
  91.    while (i<top)
  92.    { if (stiva[i]==stiva[top]) return 0;
  93.       i=i+1;}
  94.   return 1;}
  95.  
  96. int solutie(int stiva[],int top)
  97. { if (top==n) return 1;
  98.    return 0;}
  99.  
  100. int tipar(int stiva[],int top)
  101. { cout<<endl;
  102.    int i;
  103.    i=1;
  104.    while (i<=top)
  105.    { cout<<stiva[i]<<" ";
  106.       i=i+1;}
  107.   return 1;}
  108.  
  109. int bktr()
  110. {
  111. top=1;
  112. init(S,top);
  113. while (top>=1)
  114.      {
  115.         int am;
  116.        int este;
  117.        do {
  118.            am=succ(S,top);
  119.            este=valid(S,top);
  120.             } while(!((am&&este)||(!am)));
  121.         if (am) {
  122.             if (solutie(S,top)) { tipar(S,top);}
  123.                         else {
  124.                               top=top+1;
  125.                               init(S,top);
  126.                               }
  127.                     }
  128.                  else {
  129.                           top=top-1;
  130.                          }
  131.         }
  132. }
  133.  
  134. int main()
  135. {  cout<<"n=";cin>>n;
  136.     bktr();
  137. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top