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>kth 项。并排，增加术语的数量。在 n<kth 项时，移动到小于或等于 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<<"总和等于 K 的最小斐波那契项是 "<<findTermForSum(K);
   return 0;
}

总和等于 K 的最小斐波那契项是 2