Chương trình C ++ cho Định lý Zeckendorf?

Ở đây chúng ta sẽ xem cách kiểm tra xem tổng đã cho có được tìm thấy hay không bằng cách thêm một số số Fibonacci không cân bằng hay không, nếu có, đó là những số nào? Ví dụ:nếu giá trị tổng cho trước là 10, đây là tổng của 8 và 2. Cả 8 và 2 đều là các số hạng Fibonacci và chúng không liền nhau. Hãy để chúng tôi xem thuật toán để có được ý tưởng.

Thuật toán

nonNeighbourFibo (tổng hợp)

Begin
   while sum > 0, do
      fibo := greatest Fibonacci term but not greater than sum
      print fibo
      sum := sum - fibo
   done
End

Ví dụ

#include<iostream>
using namespace std;
int fibonacci(int n) {
   if (n == 0 || n == 1)
      return n;
   // get the greatest Fibonacci Number smaller than n.
   int prev = 0, curr = 1, next = 1;
   while (next <= n) {
      prev = curr;
      curr = next;
      next = prev + curr;
   }
   return curr;
}
void nonNeighbourFibo(int sum) {
   while (sum > 0) {
      int fibo = fibonacci(sum);
      cout << fibo << " ";
      sum = sum - fibo;
   }
}
int main() {
   int sum = 120;
   cout << "Sum is same as Non-adjacent Fibonacci terms: ";
   nonNeighbourFibo(sum);
}

Đầu ra

Sum is same as Non-adjacent Fibonacci terms: 89 21 8 2