Python程式：找到將n加和所需的最小斐波那契數？

假設我們有一個數字n；我們需要找到將n加和所需的最小斐波那契數。

因此，如果輸入類似於n = 20，則輸出將為3，因為我們可以使用斐波那契數[2, 5, 13] 來加和到20。

為了解決這個問題，我們將遵循以下步驟

  • res := 0

  • fibo := 一個包含值[1, 1]的列表

  • 當fibo的最後一個元素 <= n時，執行以下操作

    • x := fibo最後兩個元素的和

    • 將x插入fibo

    • 當n不為零時，執行以下操作

      • 當fibo的最後一個元素 > n時，執行以下操作

        • 從fibo中刪除最後一個元素

      • n := n - fibo的最後一個元素

      • res := res + 1

  • 返回res

讓我們看一下以下實現以獲得更好的理解

示例

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

更新於: 2020年11月10日

312 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告