C++で合計がKに等しい最小フィボナッチ項

この問題では、数値Kが与えられます。私たちのタスクは、合計がKに等しい最小フィボナッチ項を見つけることです。 。

フィボナッチ数列は、前の2つの数値を加算することにより、後続の数値を生成します。フィボナッチ数列は、F0とF1の2つの数字から始まります。 F0とF1の初期値は、それぞれ0、1、または1、1にすることができます。

フィボナッチ数列は011 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

アルゴリズム

• フィボナッチ項を計算する関数を作成します。

• 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