หาจำนวนฟีโบนัชชีน้อยที่สุดที่รวมกันได้ K ใน C++

สมมติว่าเรามีจำนวน k หาจำนวนฟีโบนัชชีน้อยที่สุดที่รวมกันได้ k (ใช้ซ้ำได้)

ตัวอย่าง: k = 7 → 2 (2 + 5 = 7)

วิธีแก้ปัญหา (Greedy)

1. สร้างเลขฟีโบนัชชีจนเกิน k
2. จากตัวมากที่สุดลงมา: ถ้า fib[j] ≤ k ให้ลบ k และนับ +1
3. ทำซ้ำจน k = 0 (Zeckendorf's theorem: greedy ให้คำตอบ optimal)

ตัวอย่างโค้ด C++

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

int main(){ 
    Solution ob; 
    cout << (ob.findMinFibonacciNumbers(7)); 
}

ข้อมูลนำเข้า

7

ผลลัพธ์

2