用 Python 查找斐波那契数列在第 n 项结果的程序


假设我们有一个数字 n。我们必须找到前 n 个斐波那契数列项之和(斐波那契数列最多 n 个项)。如果答案太大,则返回结果取余 10^8 + 7。

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

要解决此问题,我们将遵循以下步骤 −

  • m := 10^8+7
  • memo := 一个新映射
  • 定义一个函数 solve()。这将获取 n,m
  • 如果 memo 中有 n,则
    • 返回 memo[n]
  • 当 n < 2 时,memo[n] := n;否则 (solve(n-1, m) +solve(n-2, m)) mod m
  • 返回 memo[n]
  • 从主方法获取 memo 值列表,并计算其总和。

示例

让我们看看以下实现,以获得更好的理解 −

Open Compiler
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

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

33

更新于:2021-10-12

386 次浏览

开启您的职业生涯

完成课程以获得认证

开始学习
广告