程序查找最少的斐波纳契数以在Python中加到n？

假设我们有一个数字n；我们必须找到加n所需的最小斐波纳契数。

因此，如果输入像n = 20，那么输出将为3，因为我们可以使用斐波那契数[2，5，13]求和为20。

为了解决这个问题，我们将按照以下步骤

• res：= 0

• fibo：=带有值[1，1]的列表

• 而fibo的最后一个元素<= n，则

• 而fibo的最后一个元素> n，则

• n：= n-fibo的最后一个元素

• res：= res + 1

• 从fibo删除最后一个元素

• x：= fibo的最后两个元素之和

• 将x插入fibo

• 当n不为零时，

• 返回资源

让我们看一下下面的实现以获得更好的理解

示例

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