Вычисление чисел Фибоначчи: различия между версиями
Содержимое удалено Содержимое добавлено
Cayman R (обсуждение | вклад) |
VDS 22 (обсуждение | вклад) Нет описания правки |
||
Строка 66:
</source>
== Решение быстрым возведением матрицы в степень ==
Существует более эффективное решение данной задачи с помощью быстрого возведения матрицы в степень. Оно основано на следующем [[w:Числа_Фибоначчи|тождестве]]:
:: <math>P^n</math><math> = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =
\begin{pmatrix} F_{n+1} & F_n \\
F_n & F_{n-1} \end{pmatrix}.</math>
Без учета затрат на реализацию длинной арифметики этот алгоритм требует <math>O(log(n))</math> времени и <math>O(1)</math> памяти.
Ниже этот алгоритм реализован на языке С. Будем считать, что:
:: <math>A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}</math> — временная матрица, используемая в алгоритме возведения в степень. Инициализируется матрицей <math>P</math>.
:: <math>R = \begin{pmatrix} rc & rd \end{pmatrix}</math> — вектор результатов (вторая строка матрицы <math>P^n</math>)
<source lang="c">
//возвращает n-е число Фибоначчи
int fib(int n)
{
int a = 1, ta,
b = 1, tb,
c = 1, rc = 1, tc,
d = 0, rd = 0;
n--; // Уменьшаем степень, т.к. матрица инициализируется значением матрицы P, а не единичной матрицей,
// соответственно степень результата будет на единицу выше
while (n)
{
if (n & 1) // Если степень нечетная
{
// Умножаем вектор R на матрицу A
tc = rc;
rc = rc*a + rd*c;
rd = tc*b + rd*d;
}
// Умножаем матрицу A на саму себя
ta = a; tb = b; tc = c;
a = a*a + b*c;
b = ta*b + b*d;
c = c*ta + d*c;
d = tc*tb+ d*d;
n >>= 1; // Уменьшаем степень вдвое
}
return rc;
}
</source>--[[Участник:VDS 22|VDS 22]] ([[Обсуждение участника:VDS 22|обсуждение]]) 14:44, 9 января 2013 (UTC)
== Пример, показывающий первые 42 числа ряда Фибоначи ==
Есть еще одно решение, для вычисления чисел Фибоначчи. Для написания примера, используется 4 переменных: '''А''', '''В''', '''С''', '''Numb'''. Где:
| |||