程序查找最少的斐波纳契数以在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

    以上是 程序查找最少的斐波纳契数以在Python中加到n? 的全部内容, 来源链接: utcz.com/z/330835.html

    回到顶部