Вычисление чисел Фибоначчи: различия между версиями

Содержимое удалено Содержимое добавлено
м Ссылки; избыточные <big /> и <font /> вокруг <source />; пробелы.
Строка 72:
 
== Решение быстрым возведением матрицы в степень ==
Существует более эффективное решение данной задачи с помощью быстрого возведения матрицы в степень. Оно основано на следующем [[w:Числа_ФибоначчиЧисла Фибоначчи|тождестве]]:
:: <math>\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =
\begin{pmatrix} F_{n+1} & F_n \\
Строка 78:
Для удобства обозначим матрицу, возводимую в степень, как P:
:: <math>P = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.</math>
Без учета затрат на реализацию длинной арифметики этот алгоритм требует <math>O(log(n))</math> времени и <math>O(1)</math> памяти.
 
Ниже этот алгоритм реализован на языке С. Будем считать, что:
Строка 117:
}
</source>
 
{{нет категорий}}