C++で合計がKであるフィボナッチ数の最小数を見つける

数kがあるとすると、フィボナッチ数を複数回使用できるかどうかにかかわらず、合計がkに等しいフィボナッチ数の最小数を見つける必要があります。

したがって、入力がk =7の場合、フィボナッチ数は1、1、2、3、5、8、13、...であるため、出力は2になります。k=7の場合、2+を使用できます。 5=7。

これを解決するには、次の手順に従います-

• 配列fを定義する

• fの最後に0を挿入します

• fの最後に1を挿入します

• f <=kの最後の要素である間、-

  • （fの最後の要素+ fの最後から2番目の要素）を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