Числа Фибоначчи



Для расчета какого-то числа Фибоначчи необязательно брутфорсить, т.е. перебирать всю последовательность методом сложения. Есть прекрасная Формула Бине. По ней прекрасно можно найти n-й элемент последовательности.

А если воспользоваться еще и асимптотикой, т.е. упрощенной формулой, то легко найти нужное число, как ближайшее целое число к результатам этой функции.

Ну и наконец мы можем таким образом найти n, при котором число Фибоначчи перевалит, например, за 1000 знаков, по формуле: i * Math.log10(phi) + Math.log10(1/Math.sqrt(5)) , где phi — так называемое Золотое сечение. Вычисляется по формуле (Math.sqrt(5) + 1) / 2

Почему формула такая? Да потому что следуем условию, что phi**n/sqrt(5) > 10**999 (** — степень, 10**999 — это первое число, у которого 1000 знаков)

Кстати, все это можно вычислить ручкой на бумаге без калькулятора (приблизительно). Квадратные корни вычисляются делением столбиком. Логарифмы тоже можно посчитать.

Share Button