斐波纳契数之和的最后一位 [英] Last Digit of the Sum of Fibonacci Numbers

问题描述

我试图找到斐波那契数列之和的最后一位.我将总和计算为 F(n + 2)-1 .以下代码可以正常工作，但是对于大量代码(例如 99999 )来说速度较慢.我该如何优化呢?

I am trying to find the last digit of sum of Fibonacci Series. I calculate the sum as F(n+2) - 1. The below code is working fine but it is slow for large numbers (e.g 99999). How can I optimize this?

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))

推荐答案

斐波那契数字的最后一位数字系列重复周期为60.因此，您可以将n个项的总和的计算优化为 F((n + 2)％60)-1 .另外，要保持在整数范围内，您只能保留每个术语的最后一位:

The series of final digits of Fibonacci numbers repeats with a cycle of 60. Therefore, you can optimize the calculation of the sum of n terms to F((n+2) % 60) - 1. Also, to stay in the integer range, you can keep only the last digit of each term:

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]

这篇关于斐波纳契数之和的最后一位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！