資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中和為K的最小斐波那契數項
在這個問題中，我們給定一個數字K。我們的任務是找到和等於K的最小斐波那契數項。
斐波那契數列 透過將前兩個數字相加來生成後續數字。斐波那契數列從兩個數字開始——F0 & F1。F0 & F1 的初始值可以分別取 0, 1 或 1, 1。
斐波那契數列是 0 1 1 2 3 5 8 13
讓我們來看一個例子來理解這個問題：
輸入
K = 5
輸出
2
解釋
The sum 5 can be made using 3 and 2.
解決方案方法
透過使用斐波那契數，我們可以得到任何數字的和，因為 1 是一個斐波那契數。將 1 加 n 次可以得到和為 n。我們的任務是最小化產生該和的斐波那契數的個數。我們可以透過從硬幣找零問題中獲取基礎來解決這個問題，其中硬幣具有斐波那契數值。在程式語言中，解決這個問題的技術被稱為貪婪演算法。
首先，我們將斐波那契數相加，直到小於或等於和 n。然後從最後一項開始，我們將該項從 n 中減去，直到 n > 第 k 項。同時，增加項數的計數。當 n < 第 k 項時，移動到小於或等於 n 的相鄰斐波那契項，並列印該計數的值。
演算法
建立一個函式來計算斐波那契項。
計算所有小於或等於 n 的斐波那契項。
如果下一項大於 n，則不要將其推入向量並返回。
建立一個函式來查詢和等於 n 的最小斐波那契項數。
初始化一個向量來儲存斐波那契項。
從和 n 中減去斐波那契項，直到和 > 0。
將和 n 除以第 j 個斐波那契項，以找到有助於該和的項數。
列印獲得的計數作為輸出。
示例
程式演示了我們解決方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void findFiboTerms(vector<int>& fiboVals, int K){
int i = 3, nextTerm;
fiboVals.push_back(0);
fiboVals.push_back(1);
fiboVals.push_back(1);
while (1) {
nextTerm = fiboVals[i - 1] + fiboVals[i - 2];
if (nextTerm > K)
return;
fiboVals.push_back(nextTerm);
i++;
}
}
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;
}輸出
Minimum Fibonacci terms with sum equal to K is 2
更新於: 2022年2月14日
139 次瀏覽
廣告