Последняя цифра суммы чисел Фибоначчи

Question

Я пытаюсь найти последнюю цифру суммы ряда Фибоначчи. Я рассчитываю сумму как 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

Попробуйте использовать свойство Период Пизано .Если вы хотите вычислить последнюю цифру, период Пизано, равный 10, будет равен 60. Зная это, вы можете получить функцию, подобную следующей:

def fibonacci_sum(n):

    pisano = 60

    if n < 2: return n

    n %= pisano

    fib_arr = [1,1]
    for _ in range(n):
        fib_arr.append((fib_arr[-1] + fib_arr[-2]) % 10)

    return (fib_arr[-1] - 1) % 10

Для получения дополнительной информации см. saveriogzz Github CS_Curriculum repo .

Ура!

Answer 2

Последовательность последних цифр чисел Фибоначчи повторяется с циклом 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

Посмотрите на эту таблицу: 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 4

Вот код, оптимизированный специально для последней цифры:

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?0. Продолжайте это: D