Pythonで合計がnとなるフィボナッチ数の最小個数を求めるプログラム

問題の概要

ある整数 n が与えられたとき、その合計がちょうど n になるようにするために必要なフィボナッチ数の最小個数を求めます。

たとえば、入力が n = 20 の場合、出力は 3 になります。これは、フィボナッチ数列に含まれる [2, 5, 13] の3つの数を足し合わせることで 20 を作れるためです。

解決のためのアルゴリズム

この問題は「貪欲法（グリーディ法）」を用いることで効率的に解けます。基本的な考え方は、「n 以下の最大のフィボナッチ数を選び、n から引く」という操作を n が 0 になるまで繰り返すというものです。

• res := 0（使用したフィボナッチ数のカウント用変数）

• fibo := 初期値 [1, 1] を持つリスト

• fibo の最後の要素が n 以下である間、次を繰り返す

  • x := fibo の末尾2つの要素の合計

  • x を fibo に追加する

• n が 0 でない間、次を繰り返す

  • fibo の最後の要素が n より大きい間、末尾の要素を削除する

  • n := n − fibo の最後の要素

  • res := res + 1

• res を返す

この貪欲法が正しく機能する背景には、ゼッケンドルフの定理があります。すべての正の整数は、連続しないフィボナッチ数の和として一意に表すことができ、各ステップで「n 以下の最大のフィボナッチ数」を採用することで、必要な項数が最小になります。

Pythonでの実装例

class Solution:
    def solve(self, n):
        res = 0
        fibo = [1, 1]
        while fibo[-1] <= n:
            fibo.append(fibo[-1] + fibo[-2])

        while n:
            while fibo[-1] > n:
                fibo.pop()
            n -= fibo[-1]
            res += 1
        return res

ob = Solution()
n = 20
print(ob.solve(n))

入力

20

出力

3

処理の流れの解説

まず最初の while ループで、n を超えない範囲でフィボナッチ数列を生成します（1, 1, 2, 3, 5, 8, 13, 21 …）。次に、n が 0 になるまで、n 以下の最大のフィボナッチ数を順に引いていきます。

n = 20 の場合の流れは以下の通りです。

• 21 は 20 を超えるため削除され、13 を選択 → 残り 7

• 8 は 7 を超えるため削除され、5 を選択 → 残り 2

• 2 を選択 → 残り 0

このように 3 回の引き算で完了するため、答えは 3 となります。計算量はフィボナッチ数列の生成に O(log n)、残りの処理も同程度であり、非常に効率的な手法です。