Pythonで合計n個のフィボナッチ数の最小数を見つけるプログラム？

数nがあるとします。 nまで加算するために必要なフィボナッチ数の最小数を見つける必要があります。

したがって、入力がn =20の場合、出力は3になります。これは、フィボナッチ数[2、5、13]を使用して合計を20にすることができるためです。

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

• res：=0

• fibo：=値が[1、1]

  のリスト

• fiboの最後の要素<=n、do

  • x：=fiboの最後の2つの要素の合計

  • xをfiboに挿入

  • nがゼロ以外の場合、実行

    • fiboの最後の要素>n、do

      • fiboから最後の要素を削除する

    • n：=n-fiboの最後の要素

    • res：=res + 1

• 解像度を返す

理解を深めるために、次の実装を見てみましょう

例

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