Числа Фибоначчи

Чи́сла Фибона́ччи — элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,… 

в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (известного как Фибоначчи).
Более формально, последовательность чисел Фибоначчи задается линейным рекуррентным соотношением:

*-Нравится статья? Кликни по рекламе! :)

 Алгоритмы вычисления чисел Фибоначчи

Рекурсивный алгоритм
Используя рекуррентное соотношение, можно построить рекурсивный алгоритм вычисления чисел Фибоначчи:
Псевдокод. Числа Фибоначчи(рекурсивная функция)

def fib(n):
    if n<3:
        return 1
    return fib(n-1) + fib(n-2)

Наибольший интерес в этом алгоритме представляет строчка 4:
Интерес заключается в том, что дополнительный исполнитель действует по алгоритму — если его аргумент больше 1, он также вызывает очередного исполнителя для вычисления нужных ему значений. Получается серия вызовов, которые выстраиваются в дерево рекурсивных вызовов.

Древовидно-рекурсивный процесс.

При вычислении значения F(5) будут вызваны процедуры вычисления F(4) и F(3). В свою очередь, для вычисления последних потребуется вычисление двух пар F(3), F(2) и F(2), F(1).
Можно заметить, что F(2) вычисляется три раза. Если рассмотреть вычисление F(n) при больших n, то повторных вычислений будет очень много. Это и есть основной недостаток рекурсии — повторные вычисления одних и тех же значений. Кроме того, с рекурсивными функциями связана одна серьезная ошибка: дерево рекурсивных вызовов может оказаться бесконечным и компьютер «зависнет». Важно, чтобы процесс сведения задачи к более простым когда-нибудь заканчивался. Для того, чтобы рекурсивный алгоритм заканчивал свою работу, необходимо, чтобы дерево рекурсивных вызовов при любых входных данных обрывалось и было конечным, т.е. должно существовать некое терминальное условие. В данном примере дерево рекурсивных вызовов обрывается на F₁ и F₂, для вычисления которых не используются рекурсивные вызовы.

Довольно часто «зависание» компьютеров связано с использованием плохо реализизованных рекурсивных идей. Например, попробуйте подставить отрицательный аргумент n.
Пользоваться рекурсивными алгоритмами нужно осторожно, так как они могут быть очень неэффективными с точки зрения времени работы. Попробуем оценить количество операций, необходимых для того, чтобы вычислить n-й член последовательности Фибоначчи (здесь под операцией мы понимаем строчку в программе). Обозначим это число как T(n).

Для вычисления Fibo(n) нам потребуется вызвать Fibo(n - 1) и Fibo(n - 2), поэтому . Используя это соотношение и то, что T(1) = T(2) > 1, можно по индукции доказать, что . Значение
Fib(n) растет экспоненциально при увеличении n. Более точно,
Fib(n) — это целое число, ближайшее к

где

 то есть золотое сечение (golden ratio), которое удовлетворяет уравнению

Таким образом, число шагов нашего процесса растет экспоненциально при увеличении аргумента. С другой стороны, требования к памяти растут при увеличении аргумента всего лишь линейно, поскольку в каждой точке вычисления нам требуется запоминать только те вершины, которые находятся выше нас по дереву. В общем случае число шагов, требуемых древовидно-рекурсивным процессом, будет пропорционально числу вершин дерева, а требуемый объем памяти будет пропорционален максимальной глубине дерева.Поэтому даже на мощном компьютере с помощью этого алгоритма нам не удастся вычислить больше, чем первые несколько десятков членов последовательности Фибоначчи. Вы, наверное, уже догадываетесь, в чём здесь проблема. В нашей программе очень много избыточных вызовов — в дереве рекурсивных вызовов много повторений. Например Fibo(n - 2) будет вызвана два раза: сначала из Fibo(n), а потом из Fibo(n - 1), и оба раза будут проводится одни и те же вычисления.


Итеративный метод
Для получения чисел Фибоначчи мы можем сформулировать итеративный процесс. Идея состоит в том, чтобы использовать пару целых a и b, которым в начале даются значения Fib(1) = 1 и Fib(0) = 0, и на каждом шаге применять одновременную трансформацию

Нетрудно показать, что после того, как мы проделаем эту трансформацию n раз, a и b будут соответственно равны Fib(n + 1) и Fib(n). Таким образом, мы можем итеративно вычислять числа Фибоначчи при помощи процедуры

def fib(n):
    def fibIter(a, b, count):
        if count==0:
            return b
        else:
            return fibIter(a+b, a, count-1);
    return fibIter(1, 0, n)

Второй метод вычисления чисел Фибоначчи представляет собой линейную итерацию. Разница в числе шагов, требуемых двумя этими методами — один пропорционален n, другой растет так же быстро, как и само Fib(n), — огромна, даже для небольших значений аргумента.

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

 Рекурсия с запоминанием (динамическим программированием сверху)

Есть способ решить проблему повторных вычислений. Он очевиден — нужно запоминать найденные значения, чтобы не вычислять их каждый раз заново. Конечно, для этого придётся активно использовать память. Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:

1. создать глобальный массив FD, состоящий из нулей;
2. после вычисления числа Фибоначчи F(n) поместить его значение в FD[n];
3. в начале рекурсивной процедуры сделать проверку на то, что FD[n] = 0 и, если , то вернуть FD[n] в качестве результата, а иначе приступить к рекурсивному вычислению F(n).

 Человеческий алгоритм
Рекурсию с запоминанием для вычисления чисел Фибоначчи мы привели просто для демонстрации идеи. Для чисел Фибоначчи есть простой «человеческий алгоритм», не использующий рекурсивные вызовы и запоминание всех вычисленных значений. Достаточно помнить два последних числа Фибоначчи, чтобы вычислить следующее. Затем предпредыдущее можно «забыть» и перейти к вычислению следующего:

1. a = b = 1;
2. если n > 2, то сделать n − 2 раз: c = a + b; a = b; b = c;
3. вернуть ответ b;

Простой «человеческий» алгоритм вычисления чисел Фибоначчи работает существенно быстрее. Алгоритм 2 для вычисления F_n выполнит n − 2 итераций цикла While. Видно, что время работы алгоритма растёт линейно с n (увеличение n в k раз приведёт к тому, что время работы алгоритма тоже увеличится примерно в k раз).

Алгоритм 2. Числа Фибоначчи: нерекурсивный алгоритм

def fib(n):
    fib1=fib2=1
    i = 2 
    while i < n:
        fib_sum = fib2 + fib1
        fib1 = fib2
        fib2 = fib_sum
        i += 1
    return fib_sum;

От экспоненциального роста времени вычисления рекурсивных алгоритмов легко избавится с помощью запоминания вычисленных значений. А именно, в памяти хранят вычисленные значения, а в начале функции помещается проверка на то, что требуемое значение уже вычислено и хранится в памяти. Если это так, то это значение возвращается как результат, а вычисления и рекурсивные вызовы осуществляются лишь в том случае, когда функция с такими аргументами ещё ни разу не вызывалась.  

Ну и напоследок - тестирование fib(30) вызывалось 1000 раз.

• Рекурсивный алгоритм 1802004 function calls (5004 primitive calls) in 15.061 CPU seconds
• Итеративный 902004 function calls (2004 primitive calls) in 7.436 CPU seconds
• Человеческий метод 1004 function calls in 0.272 CPU seconds
  

Как мы видим, в данном случае рекурсивный алгоритм оказался существенно менее эффективным (дольше работающим при больших n), нежели нерекурсивный алгоритм. Но это не значит, что использовать рекурсию не надо. Рекурсия очень важный и удобный инструмент программирования. С помощью рекурсии успешно реализуют важный подход к решению задач: разделяй и властвуй. Лучший способ решить сложную задачу — это разделить её на несколько простых и «разделаться» с ними по отдельности. По сути, это один из важных инструментов мышления при решении задач.  

Еще, я наткнулся на функцию вывода всех чисел Фибоначчи до определенного. Приведен здесь просто, для развития, т.к. вариант использует генератор:

def fibonacci(max):# генератор (а не функция, т.к. оператор return заменён на yield)
    a, b = 0, 1
    while a < max:
        yield a# return a, + запоминаем место рестарта для следующего вызова
        a, b = b, a + b# параллельное присваивание, которое выполняется одновременно и параллельно
 
for n in fibonacci(100): # используем генератор fibonacci() как итератор
    print n, # печатаем все числа Фибоначчи меньшие 100 через пробел

Для лучшего понимания, как работает генератор(если не очень поняли код выше), советую просмотреть код http://www.kigorw.com/articles/python-yield-generator


Используемая литература: 1.)Вошедшая в привычку ссылка на действительно мощную математическую статью на Вики -  Числа Фибоначчи.
2.)  Что такое алгоритм
3.) Вычисление чисел Фибоначчи
4.) Рекурсия
5.) Числа Фибоначчи на http://younglinux.info/algorithm/fibonacci
6.) Что такое числа Фибоначчи