資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告