Fibonacci数之和的最后一位数

Question

我试图找到Fibonacci系列总和的最后一位数。我计算总和为F(n+2) - 1。下面的代码工作正常，但对于大数字（例如99999）来说速度很慢。我该如何优化呢？

n = int(input())

def last_digit(n):
    a, b = 0, 1
    for i in range(n+2):
        a, b = b, a + b
    return (a-1) % 10

print(last_digit(n))

Answer 1

看看这张表：http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html注意到fib(60)的最后一位是0，而fib(61)的最后一位是1，与fib(0)和fib(1)相同，因此从60开始，最后一位数字开始重复，所以你可以计算fib(n%60)的最后一位数而不是fib(n)。例如，fib(115)和fib(55)的最后一位数字相同，等于5。

Answer 2

Fibonacci的最终数字序列号为repeats，周期为60.因此，您可以优化n个项之和到F((n+2) % 60) - 1的计算。另外，要保持整数范围，您只能保留每个术语的最后一位数：

def last_digit(n):
    a, b = 0, 1
    for i in range((n + 2) % 60):
        a, b = b, (a + b) % 10
    return 9 if a == 0 else a - 1

print([last_digit(n) for n in range(1, 11)])

输出：

[1, 2, 4, 7, 2, 0, 3, 4, 8, 3]

Answer 3

这里的代码专门针对最后一位进行了优化：

def fib(n):
    a, b = 0, 1
    r = 1
    if n < 1:
        return 0
    for i in range(n - 1):
        a, b = b, (a + b)%10
        r += b
        r %= 10
    return r

它的工作原理是只获取下一个术语的最后一个数字并将其添加到结果中。然后它获取结果的最后一位并将其设置为自身。它会重复，直到达到术语编号并返回一位数字：D

有趣的事实：在99上尝试上述功能。返回0. 999怎么样？ 0. 9999？继续这个：D