数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学用 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 值列表，并计算其总和。
示例
让我们看看以下实现，以获得更好的理解 −
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
更新于：2021-10-12
386 次浏览
广告