|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 25 Jul 2001 03:59:35
To : All
Subject : Re: Числа фибоначи
--------------------------------------------------------------------------------
"Dmitry Pankov" <Dmitry.Pankov@p27.f58.n5022.z2.fidonet.org> wrote in
message news:995980524@p27.f58.n5022.z2.ftn...
> DK> Подскажите, как итеративно находить числа Фибоначи.
>
> Из книжульки "Системы искусственного интеллекта" (Лорьен):
>
> === Cut ===
> Итеративные алгоритмы. Чтобы уменьшить эту дорогостоящую из-за большой
глубины
> рекурсивность и избежать многократного повторения одних и тех же расчетов,
> можно преобразовать приведенную выше рекурсивную схему в рекуррентную.
Иными
> словами, мы расчленим задачу, предположив, что она решена до определенной
> точки, т. е. до некоторого значения i из n. Затем мы выведем из него F(j)
по
> крайней мере еще для одного значения j. Для этого выдвигается гипотеза
> рекуррентности. В нашем случае естественно предположить следующее.
Более того, для чисел Фибоначи
f(1) =1
f(2) =1
f(i+2) =f(i+1)+f(i)
можно записать
f(i+j) = a*f(i+1)+b*f(i)
где i>=1, j>=2, a = f(j), b=f(j-1) и
f(i+j) = f(i+1)*f(j)+f(i)*f(j-1)
и таким образом можно шагать квадратично,
т.е. для четного числа Фибоначи
f(2*k) = f(k+1)*f(k)+f(k)*f(k-1) = f(k)*(f(k)+2*f(k-1))
и для нечетного
f(2*k+1) = f(k+1)*f(k+1)+f(k)*f(k)
И надо явно задать
f(1)=1;
f(2)=1;
Hакладные расходы рекурсии весьма велики,
но, а принципе, при номере числа Фибоначи около 100
(что помещается в 64бит) и дополнительных ухищрениях
(типа запоминания уже вычисленных значений) этот подход
работает примерно со скоростью лобового вычисления
всех чисел. Для больших номеров ;) он будет быстрее.
В принципе я разбивал k на i+j беря максимально близкие i и j,
но возможно наверное использовать и другие походы,
степени двойки, например.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
