在 C++ 中查找和为 K 的斐波那契数的最小数量
c++server side programmingprogramming
假设我们有一个数字 k，我们必须找到和等于 k 的斐波那契数的最小数量，无论斐波那契数是否可以多次使用。
因此，如果输入为 k = 7，则输出将为 2，因为斐波那契数为:1、1、2、3、5、8、13，... 对于 k = 7，我们可以使用 2 + 5 = 7。
为了解决这个问题，我们将遵循以下步骤 −
定义一个数组 f
在 f 的末尾插入 0
在f
当 f 的最后一个元素 <= k 时，执行 −
将 (f 的最后一个元素 + f 的倒数第二个元素) 插入 f
ret := 0
j := f 的最后一个索引
当 (j >= 0 且 k > 0) 时，执行 −
如果 f[j] <= k，则 −
k := k - f[j]
(将 ret 增加 1)
否则
(将 j 减少 1)
return ret
示例
让我们看下面的实现，以便更好地理解 −
#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));
}
输入
7
输出
2
