Еще одна задача про Фибоначчи

Последовательность Фибоначчи

Последовательность Фибоначчи - это такая последовательность, в которой каждый элемент равен сумме двух предыдущих, за исключением первых двух F0 и F1, которые соответственно равны нулю и единице.

Чему равно значение n-го числа Фибоначчи?

Входные данные

Каждая строка содержит целое число i (0 ≤ i ≤ 10^8), для которого необходимо вычислить значение i-го числа Фибоначчи Fi.

Выходные данные

Большие числа Фибоначчи получить довольно не сложно, поэтому, когда ответ состоит более чем из 8 цифр, выведите только первые и последние 4 цифры ответа, разделенные на две части многоточием ("...") - см. пример.

Лимит времени 1 секунда

Лимит использования памяти 64 MiB

Входные данные

0
1
2
3
4
5
35
36
37
38
39
40
64
65

Выходные данные

0
1
1
2
3
5
9227465
14930352
24157817
39088169
63245986
1023...4155
1061...7723
1716...7565

Задачу в режиме онлайн можно протестировать тут.

В данной задаче нам потребуется вычислять первые четыре цифры числа Фибоначчи, помимо вычисление последних четерых цифр (эта задача была разобрана в предыдущей статье). По факту задачу поиска первых k-цифр n-го числа Фибоначчи можно решать в общем виде, только необходимо учесть ограничение точности чисел с плавающей запятой, это около 14 цифр.

Формула Бине выражает в явном виде значение Fn как функцию от n:

Из формулы Бине следует, что Fn ближайшее целое число к

Тогда получим приближение:

Дальше воспользуемся формулой:

Приведем знаменатель и числитель выражение (4) и получим:

Обозначим:

Получим:

Где k1 - целая часть числа k, k2 - дробная. Очевидно за значащие цифры числа Фибоначчи отвечает множитель 10^k2, так как от нас требуют первые четыре цифры, достаточно вознести 10 в степень k2, умножить на 1000 и взять целую часть.

Так как нас просят выводить все цифры числа когда его длина меньше либо равна восьми, достаточно отыскать такой номер, после которого все числа будут длиной больше чем восемь. Это F40.

Рассмотрим детали реализации которые касаются только вычисления первых четырех цифр, так как задача нахождения последних четырех уже была разобрана ранее.

В строках 2-3 вычисляются значение числителя и знаменателя из выражения (4). В строке 4 высчитываем разность показателей. В строке 5 находим дробную часть числа. В строке 6 возвращаем результат в виде первых четырех цифр.

В других деталях реализация совпадает с задачей разобранной в прошлой статье.

Спасибо за внимание.