Advertisement
MouseyN1

Backtracking suma cu Fibonacci

Oct 22nd, 2013
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <fstream>
  2. using namespace std;
  3. ifstream cin("input.in");
  4. ofstream cout("output.out");
  5.  
  6.  
  7. long long v [100], p [100], c, i; // v, p-fibonacci, c-nr termeni
  8.  
  9. void Genereaza (int n) // generarea termenilor din sir cat timp sunt mai mici ca n
  10. {
  11.     v[1] = 1;
  12.     v[2] = 2;
  13.     int i = 3;
  14.     while (true)
  15.     {
  16.         v[i] = v[i - 1] + v[i - 2];
  17.         if (v[i] > n)
  18.             break;
  19.         ++i;
  20.     }
  21.     c = i - 1;
  22. }
  23.  
  24. void Afiseaza (void) // afisarea tuturor posibilitatilor de a descompune numarul
  25. {
  26.     for (int j = 1 ; j <= i ; ++j)
  27.         cout << p[j] << ' ';
  28.     cout << '\n';
  29. }
  30.  
  31. void Back (int m) // functia back
  32. {
  33.     if (m == 0)
  34.     {
  35.         Afiseaza();
  36.         return;
  37.     }
  38.     ++i;
  39.     for (int j=1 ; j <= c && v[j] <= m ; ++j)
  40.     {
  41.         if (v[j] < p[i - 1])
  42.             continue;
  43.         p[i] = v[j];
  44.         Back(m - v[j]);
  45.     }
  46.     --i;
  47. }
  48.  
  49. int main (void) // functia main.
  50. {
  51.     int m;
  52.     cin >> m;
  53.     Genereaza(m);
  54.     Back(m);
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement