数据结构
网络
关系数据库管理系统 (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 次浏览
广告