SHARE
TWEET

Untitled

a guest Feb 28th, 2020 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Vectori . Aplicatii alg de sortare
  2. 1.  Select Sort
  3. 2.  Bubble Sort
  4. 3.  Insert Sort
  5. 4.  Heap Sort
  6. ------------------------------------
  7. Aplicatii
  8. 1. Generarii permutarilor unei multimi cu n elemente
  9. 2. Generarea vectorilor booleni cu n componente
  10.  
  11. exemplu : n=3
  12.  
  13. 0 0 0
  14. 0 0 1
  15. 0 1 0
  16. 0 1 1
  17. 1 0 0
  18. 1 0 1
  19. 1 1 0
  20. 1 1 1
  21.  
  22. Procedeu
  23.  
  24. la pasul initial se porneste cu prima solutie vectorul nul
  25. aplicam o strategie de tip greedy
  26. ( lacom = avansez "lacom" = irevocabil in drum generarii tuturo solutiilor )
  27. din solutie anterior generata dorim sa obtinem o noua solutie
  28. Astfel
  29. parcurgem solutia anterioara de la ultimul catre primul element
  30. in timpul acestei parcurgeri putem intalni una din situatiile :
  31.  
  32. [a]  V[i]=0 atunci executa
  33.                                         - V[i]=1
  34.                                         - stop
  35.                               sfarsit
  36. [b]  V[i]=1 atunci executa                              
  37.                                         - V[i]=0
  38.                                         - avansez
  39.                               sfarsit
  40. [solutie 1]
  41. 0 0 0        
  42. [solutie 2]
  43. 0 0 1        
  44. [solutie 3]
  45. 0 1 0
  46. [solutie 4]
  47. 0 1 1
  48. [solutie 5]
  49. 1 0 0
  50. [solutie 6]
  51. 1 0 1
  52. [solutie 7]
  53. 1 1 0
  54. [solutie 8]
  55. 1 1 1
  56.  
  57. Obs : Pentru problema enuntata exista rezultat matematic care afirma
  58.          ca sunt 2^n solutii !
  59.  
  60. Abordare 1 :
  61.                  
  62. pentru i de la 1 pana la 2^n executa
  63.                                             -----
  64.                                                sfarsit
  65.  
  66. functioneaza neeficient datorita 2^n                                                                                              
  67.  
  68. Abordare 2 :
  69.  
  70. procedeul de parcurgere  de la coada la cap cu aplicarea regulilor
  71. [a]  si [b] continua pana cand numarul celor schimbate este n
  72. Adica in timpul executiei unei parcurgeri NUMAR numarul
  73. schimbarilor din 1 in 0 . Daca acest numar este n opresc generarile !
  74.  
  75.  
  76. PSEUDOCOD :
  77. - citeste n
  78. - executa
  79.      - counter = 0
  80.      - pentru i=1 pana la n afiseaza V[i]          
  81.      - pentru i=n pana la 1 executa
  82.                                             - daca V[i]=0 atunci executa
  83.                                                                                    - V[i]=1
  84.                                                                                    -  i=0
  85.                                                                                sfarsit
  86.                                                                     altfel  executa
  87.                                                                                    - V[i]=0
  88.                                                                                    - counter=counter+1
  89.                                                                                 sfarsit  
  90.   pana cand counter=n
  91.                
  92.  
  93. #include <iostream>
  94. using namespace std;
  95. int n,i;
  96. int counter = 0;
  97. int v[100];
  98. int main()
  99. {
  100.     cout<<"n=";cin>>n;
  101.  
  102.         do
  103.         {
  104.         for(i=1;i<=n;i++)
  105.         {
  106.             cout<<v[i];
  107.         }
  108.         cout<<endl;
  109.         for(i=n;i>=1;i--)
  110.         {
  111.             if(v[i]==0)
  112.             {
  113.                 v[i] = 1;
  114.                 break;
  115.             }
  116.             else
  117.             {
  118.                 v[i] = 0;
  119.             }
  120.         }
  121.         counter = counter + 1;
  122.         }
  123.     while(counter < n);
  124.  
  125. }
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
Top