|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitry Pankov 2:5022/58.27 24 Jul 2001 13:10:02
To : Dima Kiryakov
Subject : Числа фибоначи
--------------------------------------------------------------------------------
21 июля 2001 года (а было тогда 00:19) бабушка мне сказала, что
Dima Kiryakov в своем письме к All писал:
DK> Подскажите, как итеративно находить числа Фибоначи.
Из книжульки "Системы искусственного интеллекта" (Лорьен):
=== Cut ===
Итеративные алгоритмы. Чтобы уменьшить эту дорогостоящую из-за большой глубины
рекурсивность и избежать многократного повторения одних и тех же расчетов,
можно преобразовать приведенную выше рекурсивную схему в рекуррентную. Иными
словами, мы расчленим задачу, предположив, что она решена до определенной
точки, т. е. до некоторого значения i из n. Затем мы выведем из него F(j) по
крайней мере еще для одного значения j. Для этого выдвигается гипотеза
рекуррентности. В нашем случае естественно предположить следующее. Пусть F(1),
F(2), ..., F(i) уже получены. Hачнем с i=2. При этом задача решена полностью,
когда j = n.
Если j<>n, приведенная в определении формула F(i+1)= F(i)+F(i-1) позволяет
распространить рекуррентную гипотезу на одну ступень дальше; следовательно, нам
известны F(1), F(2), ..., F(i), F(i+1). Более того, приведенная в определении
формула показывает, что члены F(1),F(2), ..., F(i-2) в данном рекуррентном
соотношении не участвуют. Вся необходимая информация содержится в тройке [i,
F(i), F(i-1)]. Пусть в соответствии с гипотезой эта тройка известна; тогда мы
можем вывести из нее следующую тройку:
[i+1, F (i+1), F (i)] = [i+1, F (i) + F (i-1), F (i)].
Тем самым мы упростили гипотезу рекуррентности и нашу схему подсчета. Итак, у
нас есть искомый итеративный алгоритм.
Оказывается, нам не нужно было запоминать вектор F[1, n] целиком, а достаточно
было двух его значений. Hазовем эти значения u и v: u соответствует F(i), a v -
F(i-1). Тогда от тройки [i, u, v] мы можем перейти к тройке [i+l, u+v, u]
i = i+l {новое значение i}
w = u {сохранение прежнего значения u}
u = u+v {новое значение u по приведенной в определении формуле}
v = w {новое значение v = прежнее значение u=F(i)}
Hачальные условия и тест остановки программ уже были указаны, так что полный
алгоритм рассматриваемого третьего типа записывается следующим образом:
Процедура Фибоначчи: F (n)
i = 2; u = 1; v = 1;
{Рекуррентная гипотеза: [i, F(i)=u и F(i-1)=v] известны}
ПОВТОРЯТЬ ДО ТЕХ ПОР ПОКА i <> n
i = i+1;
w = u;
u = u+v;
v = w;
КОHЕЦ ЦИКЛА по i
РЕЗУЛЬТАТ u
Конец процедуры
=== Cut ===
С наилучшими пожеланиями, Dmitry
*e-mail: panda@tula.net*
. Тишина
... Increase free space on your HDD - del C:\WINDOWS\*.*
--- X-Mailer: The Bat! (v1.53) Personal
* Origin: Press any key to continue or any other key to exit (2:5022/58.27)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
