Практика программирования (Бейсик, Си, Паскаль)



         

Задачи,советы и ответы


Задание 5.01. Числа Фибоначчи

История чисел Фибоначчи восходит к началу XIII в., когда итальянский математик Леонардо Пизанский нашел изящное решение задачи о размножении кроликов. Пусть в начале эксперимента имеется единственная пара -самец и самка, которые приносят каждый месяц приплод, состоящий также из самца и самки. Дети включаются в цикл продолжения рода через два месяца. Требуется определить количество пар, спустя k месяцев после начала эксперимента. Ситуация не так уж и сложна:

  • в начале эксперимента — 1 родительская пара;

  • через 1 месяц — 2 пары (родители и дети первого поколения);

  • через 2 месяца — 3 пары (родители и дети двух поколений);

  • через 3 месяца — 5 пар (родители, дети трех поколений, внуки от первого поколения);

  • через 4 месяца — 8 пар (родители, дети четырех поколений, 2 пары внуков от первого поколения, 1 пара внуков от второго поколения);

  • ..............................................................................

    Леонардо догадался, что числа указанной последовательности связаны рекуррентным соотношением:

    fk = fk-2 + fk-1

    В разных учебниках последовательность чисел Фибоначчи дополняют либо еще одной единицей, либо нулем и единицей:

    1,1,2,3,5,8,13,21,34,55,...

    0,1,1,2,3,5,8,13,21,34,.....

    Последний вариант принят в приводимых ниже программах, отсчет порядковых номеров чисел Фибоначчи ведется от 0. Диапазон действия этих программ не так уж велик: fit>(22)=17711, fib(23) =28657 и уже 24-е число выходит за пределы предусмотренного диапазона. Если вас заинтересуют числа с большими номерами, то можно изменить тип функции fib или воспользоваться формулой Бинэ:

    f ib (k) = ( ( (1+sqrt (5) ) /2)*k- ( (1-sqrt (5) ) /2} ^k) /sqrt (5)

    Наиболее известное применение чисел Фибоначчи — оптимальный выбор точек при поиске экстремума унимодальной функции на заданном отрезке. Рекурсивная реализация нахождения чисел Фибоначчи абсолютно неэффективна, т. к. в теле процедуры при каждой итерации происходит два обращения к этой же процедуре и объем вычислений с ростом k возрастает почти в геометрической профессии.




    Содержание  Назад  Вперед