用 Python 编写程序来找出斐波那契数列中最小的和为 n 的数?

pythonserver side programmingprogramming更新于 2026/2/16 19:56:17

假设我们有一个数字 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))