Tìm Số Fibonacci Số Fibonacci Tối thiểu có Tổng là K trong C ++

Giả sử chúng ta có một số k, chúng ta phải tìm số lượng Fibonacci tối thiểu có tổng bằng k, liệu một số Fibonacci có thể được sử dụng nhiều lần hay không.

Vì vậy, nếu đầu vào là k =7, thì đầu ra sẽ là 2, vì các số Fibonacci là:1, 1, 2, 3, 5, 8, 13, ... Với k =7, chúng ta có thể sử dụng 2 + 5 =7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng f

• chèn 0 vào cuối f

• chèn 1 vào cuối f

• trong khi phần tử cuối cùng của f <=k, do -

  • insert (phần tử cuối cùng của f + phần tử cuối cùng thứ hai của f) vào f

• ret:=0

• j:=chỉ số cuối cùng của f

• while (j> =0 và k> 0), do -

  • nếu f [j] <=k, thì -

    • k:=k - f [j]

    • (tăng ret lên 1)

  • Nếu không

    • (giảm j đi 1)

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findMinFibonacciNumbers(int k) {
      vector<int> f;
      f.push_back(0);
      f.push_back(1);
      while (f.back() <= k) {
         f.push_back(f[f.size() - 1] + f[f.size() - 2]);
      }
      int ret = 0;
      int j = f.size() - 1;
      while (j >= 0 && k > 0) {
         if (f[j] <= k) {
            k -= f[j];
            ret++;
         }
         else
            j--;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findMinFibonacciNumbers(7));
}

Đầu vào

7

Đầu ra

2