C++で合計がKになるフィボナッチ数の最小個数を求める方法

数値 k が与えられたとき、合計がちょうど k と等しくなるようなフィボナッチ数の最小個数を求めます。ただし、同じフィボナッチ数は複数回使用しても構いません。

例えば、入力が k = 7 の場合、出力は 2 になります。フィボナッチ数列は 1, 1, 2, 3, 5, 8, 13, ... と続きますが、k = 7 の場合は 2 + 5 = 7 という 2 つの数の組み合わせで表現できるためです。

アルゴリズム(貪欲法)

この問題は貪欲法(グリーディ法)を用いることで効率的に解けます。基本的な考え方は、「k を超えない最大のフィボナッチ数を選び、残りの値に対して同じ操作を繰り返す」というものです。ゼッケンドルフの定理(Zeckendorf's theorem)によれば、「すべての正整数は互いに連続しないフィボナッチ数の和として一意に表現できる」ことが証明されているため、この貪欲な選択が常に最適解を導きます。

具体的には、以下の手順に従います。

• 配列 f を定義する
• f の末尾に 0 を挿入する
• f の末尾に 1 を挿入する
• f の最後の要素が k 以下である間、次を繰り返す:
  • (f の最後の要素 + 最後から 2 番目の要素)を f に挿入する
• ret := 0 と初期化する
• j := f の最後のインデックス とする
• (j >= 0 かつ k > 0)である間、次を繰り返す:
  • もし f[j] <= k ならば:
    • k := k - f[j]
    • ret を 1 増やす
  • そうでなければ:
    • j を 1 減らす
• ret を返す

C++ 実装例

以下の実装例を見ると、より理解が深まるでしょう。

#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

計算量について

フィボナッチ数列の生成は O(log k) で完了し、貪欲な選択処理も同様に O(log k) で終了するため、全体の時間計算量は O(log k) となり、非常に効率的です。空間計算量も、生成したフィボナッチ数列を格納する分の O(log k) に抑えられます。