数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用C++查找和为K的最小斐波那契数个数
假设我们有一个数字k，我们需要找到和等于k的最小斐波那契数个数，并且可以多次使用同一个斐波那契数。
例如，如果输入k = 7，则输出为2，因为斐波那契数列为：1, 1, 2, 3, 5, 8, 13, ... 对于k = 7，我们可以使用 2 + 5 = 7。
为了解决这个问题，我们将遵循以下步骤：
定义一个数组f
在f的末尾插入0
在f的末尾插入1
当f的最后一个元素小于等于k时，执行以下操作：
将(f的最后一个元素 + f的倒数第二个元素)插入到f中
ret := 0
j := f的最后一个索引
当(j >= 0 且 k > 0)时，执行以下操作：
如果f[j] <= k，则：
k := k - f[j]
(ret加1)
否则
(j减1)
返回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
更新于：2020年11月17日
445 次浏览
广告