Python中找到斐波那契数列结果的程序

Python中找到斐波那契数列结果的程序

假设我们有一个数n。我们需要找到前n个斐波那契数的和(斐波那契数列前n项)。如果答案太大,则返回结果模10^8 + 7。

所以,如果输入为n = 8,则输出将是33,因为前几个斐波那契数是0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33

为了解决此问题,我们将遵循以下步骤 –

  • m := 10^8+7
  • memo :=一个新映射
  • 定义一个解决()函数。这将采取n,m
  • 如果n在备忘录中,则
    • 返回memo [n]
  • 否则, memo[n] := n if n < 2 else (solve(n-1, m) +solve(n-2, m)) mod m
  • 返回memo [n]
  • 从main方法获取备忘录值列表并取它们的总和。

例子

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

m = 10**8+7
memo = {}
def solve(n, m):
   if n in memo:
      return memo[n]
   memo[n] = n if n < 2 else (solve(n-1, m)+solve(n-2, m)) % m
   return memo[n]

n = 8
solve(n, m)
print(sum(list(memo.values())[:n]))

输入

8

输出

33

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

Numpy 示例