Số hạng Fibonacci tối thiểu có tổng bằng K bằng C++

Mô tả bài toán

Cho số K. Tìm số lượng ít nhất các số Fibonacci có tổng bằng K (mỗi số Fibonacci có thể dùng nhiều lần).

Ví dụ

K = 5 → Output: 2 (5 = 3 + 2).

Giải thuật (Tham lam)

1. Sinh tất cả số Fibonacci ≤ K.
2. Từ số lớn nhất, lấy bao nhiêu lần có thể (K / fibo[j]), cộng vào đếm, cập nhật K = K % fibo[j], chuyển sang số Fibonacci nhỏ hơn.

Mã nguồn C++

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

void findFiboTerms(vector<int>& fiboVals, int K) {
    fiboVals = {0,1,1};
    for (int i=3;; i++) {
        int next = fiboVals[i-1] + fiboVals[i-2];
        if (next > K) return;
        fiboVals.push_back(next);
    }
}

int findTermForSum(int K) {
    vector<int> fiboVals;
    findFiboTerms(fiboVals, K);
    int termCount = 0, j = fiboVals.size()-1;
    while (K > 0) {
        termCount += K / fiboVals[j];
        K %= fiboVals[j];
        j--;
    }
    return termCount;
}

int main() {
    int K = 11;
    cout << "Minimum Fibonacci terms with sum equal to K is " << findTermForSum(K);
    return 0;
}

Đầu ra

Minimum Fibonacci terms with sum equal to K is 2