Số lượng ít nhất số Fibonacci tổng bằng K (Find the Minimum Number of Fibonacci Numbers Whose Sum Is K) trong C++

Cho số k. Tìm số lượng nhỏ nhất các số Fibonacci (có thể dùng lặp lại) có tổng bằng k.

Ví dụ

Đầu vào: k = 7
Đầu ra: 2 (2 + 5 = 7).

Thuật toán Tham lam (Zeckendorf's Theorem)

Định lý Zeckendorf: mọi số nguyên dương đều có thể biểu diễn duy nhất dưới dạng tổng các số Fibonacci không liên tiếp. Chiến lược tham lam lấy số Fibonacci lớn nhất ≤ k cho kết quả tối ưu (dù cho phép lặp, tham lam vẫn đúng).

1. Sinh dãy Fibonacci đến > k.
2. Duyệt từ lớn đến nhỏ: nếu fib[i] ≤ k thì k -= fib[i], ans++.
3. Lặp cho đến khi k = 0.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        vector fib = {0, 1};
        while (fib.back() <= k)
            fib.push_back(fib[fib.size()-1] + fib[fib.size()-2]);
        int ans = 0;
        for (int i = fib.size()-1; i >= 0 && k > 0; --i)
            if (fib[i] <= k) { k -= fib[i]; ++ans; }
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(log k) - số lượng số Fibonacci ≤ k tỷ lệ log_φ(k).
• Không gian: O(log k) lưu dãy Fibonacci.

Kết quả kiểm thử

Đầu vào: 7
Đầu ra: 2