Вычисление чисел Фибоначчи: различия между версиями
Содержимое удалено Содержимое добавлено
→Решение быстрым возведением матрицы в степень: нет, само перемножение матриц даёт линейные коэффициенты |
|||
Строка 90:
Существует более эффективное решение данной задачи с помощью быстрого возведения матрицы в степень. Оно основано на следующем [[w:Числа Фибоначчи|тождестве]]:
:: <math>\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =
\begin{pmatrix} F_
F_{
Для удобства обозначим матрицу, возводимую в степень, как P:
:: <math>P = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.</math>
|