Последняя цифра большого числа Фибоначчи

Эта проблема была взята из Coursera Специализация по структурам данных и алгоритмам, в частности из Курса Algorithmic Toolbox, неделя 2, который я Недавно закончил. Если вы проходите этот курс или планируете пройти этот курс, пожалуйста, не ждите решения, поскольку оно противоречит Кодексу чести и не принесет вам никакой пользы.

Введение в проблему

Числа Фибоначчи определяются следующим образом: F (0) = 0, F (1) = 1 и
F (i) = F (i − 1) + F (i − 2) для i ≥ 2.

описание проблемы

Задача: Для целого числа n найдите последнюю цифру n-го числа Фибоначчи F (n) (которое равно, F (n) mod 10).
Формат ввода: ввод состоит из единственного целого числа n.
Ограничения: 0 ≤ n ≤ 10 ^ 7.
Формат вывода: выведите последнюю цифру F (n). < br /> Ограничения по времени: C: 1 секунда, C ++: 1 секунда, Java: 1,5 секунды, Python: 5 секунд. C #: 1,5 секунды, Haskell: 2 секунды, JavaScript: 3 секунды, Ruby: 3 секунды, Scala: 3 секунды
Ограничение памяти: 512 Мб.

Образец 1

Вход:
3
Выход:
2

Образец 2

Ввод:
327305
Выход:
5

Что делать

Напомним, что числа Фибоначчи растут экспоненциально быстро. Например, 200-е число Фибоначчи равно 280571172992510140037611932413038677189525. Следовательно, такое решение, как

F[0]=0
F[1]=1
for i=2 to n:
    F[i]=F[i-1]+F[i-2]
print(F[n] mod 10)

окажется слишком медленным, потому что по мере роста i итерация ith цикла вычисляет сумму более длинных и длинных чисел. Кроме того, например, F (1000) не вписывается в стандартный тип C ++ int.
Чтобы преодолеть эту трудность, вы можете сохранить в F [i] не само i-е число Фибоначчи, а только его последнюю цифру. (то есть F (i) mod 10). Вычислить последнюю цифру F (i) легко: это просто последняя цифра суммы последних цифр F (i − 1) и F (i − 2):

F[i]=(F[i-1]+F[i-2]) mod 10

Таким образом, все F [i] являются просто цифрами, поэтому они идеально вписываются в любой стандартный целочисленный тип, а вычисление суммы F [i - 1] и F [i - 2] выполняется очень быстро.

Мое решение:

Объяснение:

Что ж, тут особо нечего сказать, это не такая уж сложная проблема. Я только что реализовал алгоритм, который они предложили в разделе Что делать. Вместо того, чтобы хранить все числа Фибоначчи, просто сохраните их модуль и вычислите следующий, используя его.

Если вы можете придумать какой-либо другой способ улучшить этот алгоритм или указать на что-то, что, по вашему мнению, я сделал неправильно, вы более чем рады связаться со мной, ответив к этому и указав на ошибки. Если вам нравится это решение, нажмите кнопку «Рекомендовать» ниже, это будет много значить для меня. Спасибо.

Последняя цифра большого числа Фибоначчи