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 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告