Fibonacci II

949. Fibonacci II

描述

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:0,1,1,2,3,5,8,13,21,34,…

An alternative formula for the Fibonacci sequence is:

Given an integer n, your goal is to compute the last 4 digits of Fn

1.0 ≤ n ≤ 1,000,000,000

2.If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros(print Fn mod 10000)

样例

Given: n =

Return:

思路：数组保存每个数字的4位尾数，叠加计算到数组末尾。

ifn==:

return

ifn==1:

return1

numbers = [forxinrange(n+1)]

numbers[]=

numbers[1]=1

forxinrange(2,n+1):

numbers[x]=(numbers[x-1]%10000+numbers[x-2]%10000)%10000

运行结果：

超过了空间限制，5531354，数字挺大的..要考虑是否有循环的可能了。

以100000为限进行一下测试，查找连续2个1存在的位置：

发现4位尾数以15000为单位进行循环。头一次知道Fibonacci数列里有循环...

那就把n对15000求余。

ifn==:

return

ifn==1:

return1

ifn>=15000:

n = n%15000

numbers = [forxinrange(n+1)]

numbers[]=

numbers[1]=1

forxinrange(2,n+1):

numbers[x]=(numbers[x-1]%10000+numbers[x-2]%10000)%10000

returnstr(numbers[n])

运行结果：

在该题Python语言排行榜中，第一名的运行时间是50ms，后面都要500多ms了，不明白是怎么做到的。

我直接把前15000个数放进数组直接查询，运行结果也要540ms左右......