Алгоритмы поиска чисел Фибоначчи

Для лучшего понимания статьи, можно почитать про виды сложностей алгоритмов и операции с матрицами.

Числа Фибоначчи — последовательность чисел, где каждое следующее число это сумма двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Их мельком проходят в школе на алгебре и примерно в то же время на геометрии говорят про золотое сечение.
Так Евклид назвал формулу почти идеального для построения правильного пятиугольника. Большая величина относится к меньшей так же, как сумма этих величин к большей. В виде формулы это выглядит так: \(\frac ab = \frac {a+b}{a}\), a — большая величина и b — меньшая.

Золотое сечение обозначается греческой буквой ФИ и объясняется вот такой формулой: \(\phi = \frac {1 + \sqrt 5}{2}\), с точностью до пяти знаков ФИ равно 1,61803.

И тут появляются числа Фибоначчи: отношение одного числа к предыдущему постоянно приближается к значению золотого сечения. Чем больше числа, тем точнее приближение \(\frac {55}{34} \approx 1.61764, \frac {377}{233} \approx 1.61802\).

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

Вычисление чисел Фибоначчи

Чтобы найти какое-то конкретное число есть четыре способа. Некоторые эффективны только до какого-то числа, но все вычисляют точно.

Рекурсивный — самый медленный

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

Это работает сносно, пока не нужно вычислять числа стоящие выше 30 номера в последовательности, потому что при каждом вызове функции она вызывает себя дважды и вычисляет одни и те же значения много раз.

Алгоритмическая сложность — экспоненциальная, \(\mathbf O(2^n)\)

Хорошее быстрое решение — динамическое программирование

Из определения последовательности Фибоначчи становится понятно, что для вычисления нам нужны только два последних числа. Тогда теперь переменно записываем только два последних вычисленных числа, а не всю последовательность.

Алгоритмическая сложность — линейная, O(n)

Самое быстрое точное решение — возведение матриц в степень

Это работает потому что возведение матрицы в степень можно сделать за \(\mathbf O(log_2 n)\).
Существует вот такое матричное уравнение:
$$\begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} =
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$$
Правую матрицу обычно называют Ку-матрицой и если понизить её степень на один, то индексы в левой матрице тоже понизятся.

После понижения степени получается такое уравнение:
$$\begin{bmatrix} F_n & F_{n-1} \\ F_{n-1} & F_{n-2} \end{bmatrix} =
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1}$$

Теперь делаем так: возводим Ку-матрицу в степень n − 1 и берём элемент из первой строки, первого столбца. В программировании всё считается с нуля, поэтому там нулевой элемент, нулевого столбца

Алгоритмическая сложность — логарифмическая, \(\mathbf O(log_2 n)\)

Формула Бине

Тоже быстрое решение, но после семидесятого числа начинаются погрешности, потому что там очень длинная дробь, а точность чисел в компьютере ограничена.
Формула: \(F_n = \frac {\phi^n}{\sqrt 5}, \phi = \frac {1 + \sqrt 5}{2}\).

Например, вычисление 25 числа будет выглядеть так:

  1. Вычисляем ФИ: \(\phi = \frac {1 + 2.23606797749979}{2} = 1.618033988749895\)
  2. Вычисляем формулу: \(F_{25} = \frac {1.618033988749895^{25}}{2.23606797749979} = \frac {167761.000005961}{2.23606797749979} = 75024.99999733428 \approx 75025\)
  3. Получаем 25 число: \(F_{25} = 75025\)

Алгоритмическая сложность — постоянная, O(1)

Мы запустили все способы на своих печках и посчитали их время, чтобы показать разницу в скорости.
Рекурсивному алгоритму мы отдали вычислять 43 число, он считал его чуть меньше 7 минут.
Динамический и матричный алгоритмы сильнее, поэтому пускай вычисляют 1 000 000 число.
Матричный алгоритм справился за пол секунды, динамический за 12 секунд.

Поделиться
Отправить
Запинить
 43   2 мес   алгоритмы   математика
Популярное