Вопрос № 42149: Существует ли алгоритм поиска Фибоначчи? Если да, не могли бы вы привести его. Спасибо!...
Вопрос № 42.149
Существует ли алгоритм поиска Фибоначчи? Если да, не могли бы вы привести его. Спасибо!
Отправлен: 05.05.2006, 16:26
Вопрос задала: Veranda (статус: Посетитель)
Всего ответов: 4 Мини-форум вопроса >>> (сообщений: 0)
Отвечает: EPDSota
Здравствуйте, Veranda!
Один из простых вариантов:
unsigned long Fibon(unsigned long Position){
if(!Position)return 0;
if((Position==1)|(Position==2))return 1;
return(Fibon(i-1)+Fibon(i-2));
}
--------- Открыть глаза навстречу солнцу
Ответ отправил: EPDSota (статус: Специалист)
Ответ отправлен: 05.05.2006, 16:36
Отвечает: Ramok
Здравствуйте, Veranda!
вот пример
http://khpi-iip.mipk.kharkiv.edu/library/datastr/lab/lab4.html
найдено так:
в http://google.com введена строка поиска "алгоритм поиска Фибоначчи пример" без кавычек
вторая ссылка сверху. ниже не смотрел. но принцип надеюсь понятен Ж:-)
Ответ отправил: Ramok (статус: 1-ый класс)
Ответ отправлен: 05.05.2006, 17:19
Отвечает: Mamont0001
Здравствуйте, Veranda!
Если имеется в виду последовательность 1 1 2 3 5 8 13... :
Создаем массив чисел. Заносим в первый елемент ноль, во второй - 1.
Далее в цикле проходимся по массиву,начиная с 3 элемента и задаем каждый раз значение (сума 2 предыдущих элементов).
Необходимо использовать особо большие беззнаковые типы (unsigned long).
--------- Сон — это маленькая смерть
Ответ отправил: Mamont0001 (статус: 3-ий класс)
Ответ отправлен: 05.05.2006, 19:52
Отвечает: Селиванов Александр Владимирович
Здравствуйте, Veranda!
Числа Фибоначчи вычисляются по следующей формуле:
Ф(n) = Ф(n-2) + Ф(n-1);
Т.е. каждое число равно сумме двух предыдущих.
Ф(0) = 0; Ф(1) = 1.
Вот две функции, вычисляющие Ф(n) разными методами:
Рекурсивный метод нагляднее, но работает в разы медленнее. Это обусловлено тем, что по нескольку раз приходится вычислять одно и то же число. И чем глубже разворачивается рекурсия, тем больше раз вычисляем одинаковые числа.
Числа растут очень быстро, поэтому предлагаю использовать тип __int64, но это на ваше усмотрение и зависит от выбора компилятора.
Другие алгоритмы вычисления можно посмотреть на
http://algolist.manual.ru/maths/count_fast/fibonacci.php
или ещё где…
