我试图找到斐波那契数列部分和的最后一位数字

Question

#python2
def sum_fib(m,n):
    a=list()
    a.append(0)
    a.append(1)
    i=2
    while i<=n:
        a.append((a[i-1]+a[i-2])%10)
        if a[i]==1 and a[i-1]==0:
            break
        i+=1
    if n>60:
        a.pop()
    #res=sum(a)%10
    q=n-m
    j=m%60
    su=0

    while q>=0:
        su+=a[j]
        j+=1
        if j==60:
            j=0
        q-=1

    return su%10


if __name__=='__main__':
    num=[int(x) for x in raw_input().split()]
    print sum_fib(num[0],num[1])

这段代码工作正常，但大斐波那契数需要时间。请帮我解决一下这个。

对于输入：1 100000000 获取time limit exceeded-> error Time used: 9.36/5.00

Answer 1

您正在尝试使用Fibonacci 60 Repeating Pattern，但效率不高：

通过以下循环，您仍然可能收集数千个斐波那契数，而您只需要其中的 60 个：

while i<=n:
    a.append((a[i-1]+a[i-2])%10)

为避免您不得不多次运行这 60 个数字，您可以使用 60 个连续斐波那契数字之和的最后一位数字始终为 0 的属性。这实际上意味着您不需要对数千个数字求和，只是前 60 个斐波那契数的一部分，因为再增加 60 不会改变总和的最后一位数字。

因此，...您可以通过对输入变量取模 60 来修剪输入变量，然后遍历存储的 60 Fibonacci 列表以计算所需的总和。

这是改编后的代码：

def sum_fib(m,n):
    if m > n:
        return

    # Collect 60 Fibonnaci numbers
    a = [0, 1]
    for i in xrange(2, 60):
        a.append(a[i-1] + a[i-2])

    # Simplify the input arguments, as the last digit pattern repeats with a period of 60, 
    # and the sum of 60 such consecutive numbers is 0 mod 10:
    m = m % 60
    n = n % 60
    # Make sure n is greater than m
    if n < m: 
        n += 60

    su = 0
    for j in xrange(m, n+1): # Assume n index is inclusive
        su += a[j % 60]

    return su % 10

看到它在repl.it 上运行