题目描述:
斐波那契数列为1,1,2,3,5,8…。数列从第三项起满足,该项的数是其前面两个数之和。现在给你一个正整数n(n < 10000), 请你求出第n个斐波那契数取模20132013的值(斐波那契数列的编号从1开始。)
例如:
n=1, 则输出:1
n=4, 则输出:3
示例:
输入:n = 2 输出:1
分析: 斐波拉契数列 f[n] = f[n-1] + f[n+2]
这里要注意不能全部相加完了以后再取余,最好是要一边相加一边取余,这样是最好的。因为如果是最后才取余,在中间运算的时候就会出现很大的数,虽然python对整数的位数没有限制,但是在大数运算的时候,其运算性能会受到影响,所以我们最好控制一下整数的位数。 有兴趣的同学可以查一下 python 整数的实现细节。
代码:
1
2
3
4
5
fac_lst = [1, 1]
for i in range(2, 10001):
fac_lst.append((fac_lst[-1] + fac_lst[-2])%20132013)
print(fac_lst[n-1])