หาจำนวนขั้นต่ำของตัวเลขฟีโบนักชีที่มีผลรวมเป็น K ใน C++

สมมติว่าเรามีตัวเลข k เราต้องหาจำนวนขั้นต่ำของตัวเลขฟีโบนักชีที่มีผลรวมเท่ากับ k ไม่ว่าตัวเลขฟีโบนักชีจะถูกนำมาใช้หลายครั้งหรือไม่

ดังนั้น หากอินพุตเป็น k =7 ผลลัพธ์จะเป็น 2 เนื่องจากตัวเลขฟีโบนักชีคือ 1, 1, 2, 3, 5, 8, 13, ... สำหรับ k =7 เราสามารถใช้ 2 + 5 =7.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดอาร์เรย์ f
ใส่ 0 ที่ท้าย f
แทรก 1 ที่ส่วนท้ายของ f
ในขณะที่องค์ประกอบสุดท้ายของ f <=k ทำ −
- แทรก (องค์ประกอบสุดท้ายของ f + องค์ประกอบสุดท้ายที่สองของ f) ลงใน f
ยกเลิก :=0
j :=ดัชนีสุดท้ายของ f
ในขณะที่ (j>=0 และ k> 0) ทำ -
- ถ้า f[j] <=k แล้ว −
  - k :=k - f[j]
  - (เพิ่มการถอยกลับโดย 1)
- มิฉะนั้น
  - (ลด j โดย 1)
รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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));
}