|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 30 Mar 2002 04:34:08
To : Alexander Shmidt
Subject : Фибоначчи
--------------------------------------------------------------------------------
Fri Mar 29 2002 18:18, Alexander Shmidt wrote to All:
AS> и еще вопрос: сабжевая последовательность строго итеративна, или есть
AS> фомула n-го члена?
F(n)=(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5)
как ни странно...
AS> Если итеративна, то как быстрее всего найти n-й член?
Еще одно решение:
Очередная пара чисел Фибоначчи получается из предыдущей пары умножением
вектора на матрицу 2х2
(1 1)
(1 0)
Так что возведя матрицу в n-ную степень (скажем, двоичным методом это можно
сделать за log(n) шагов) получим соответствующие числа Фибоначчи...
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
