Как найти число фибоначчи по его номеру

Была ли эта статья полезной?

Время на прочтение
5 мин

Количество просмотров 306K

Введение

Программистам числа Фибоначчи должны уже поднадоесть. Примеры их вычисления используются везде. Всё от того, что эти числа предоставляют простейший пример рекурсии. А ещё они являются хорошим примером динамического программирования. Но надо ли вычислять их так в реальном проекте? Не надо. Ни рекурсия, ни динамическое программирование не являются идеальными вариантами. И не замкнутая формула, использующая числа с плавающей запятой. Сейчас я расскажу, как правильно. Но сначала пройдёмся по всем известным вариантам решения.

Код предназначен для Python 3, хотя должен идти и на Python 2.

Для начала – напомню определение:

F_n= F_n-1+ F_n-2

и F₁= F₂=1.

Замкнутая формула

Пропустим детали, но желающие могут ознакомиться с выводом формулы. Идея в том, чтобы предположить, что есть некий x, для которого F_n = xⁿ, а затем найти x.

что означает

сокращаем x^n-2

Решаем квадратное уравнение:

Откуда и растёт «золотое сечение» ϕ=(1+√5)/2. Подставив исходные значения и проделав ещё вычисления, мы получаем:

что и используем для вычисления F_n.

from __future__ import division
import math

def fib(n):
    SQRT5 = math.sqrt(5)
    PHI = (SQRT5 + 1) / 2
    return int(PHI ** n / SQRT5 + 0.5)

Хорошее:
Быстро и просто для малых n
Плохое:
Требуются операции с плавающей запятой. Для больших n потребуется большая точность.
Злое:
Использование комплексных чисел для вычисления F_n красиво с математической точки зрения, но уродливо — с компьютерной.

Рекурсия

Самое очевидное решение, которое вы уже много раз видели – скорее всего, в качестве примера того, что такое рекурсия. Повторю его ещё раз, для полноты. В Python её можно записать в одну строку:

fib = lambda n: fib(n - 1) + fib(n - 2) if n > 2 else 1

Хорошее:
Очень простая реализация, повторяющая математическое определение
Плохое:
Экспоненциальное время выполнения. Для больших n очень медленно
Злое:
Переполнение стека

Запоминание

У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fib(n), то подсчитываются fib(n-1) и fib(n-2). Но когда считается fib(n-1), она снова независимо подсчитает fib(n-2) – то есть, fib(n-2) подсчитается дважды. Если продолжить рассуждения, будет видно, что fib(n-3) будет подсчитана трижды, и т.д. Слишком много пересечений.

Поэтому надо просто запоминать результаты, чтобы не подсчитывать их снова. Время и память у этого решения расходуются линейным образом. В решении я использую словарь, но можно было бы использовать и простой массив.

M = {0: 0, 1: 1}

def fib(n):
    if n in M:
        return M[n]
    M[n] = fib(n - 1) + fib(n - 2)
    return M[n]

(В Python это можно также сделать при помощи декоратора, functools.lru_cache.)

Хорошее:
Просто превратить рекурсию в решение с запоминанием. Превращает экспоненциальное время выполнение в линейное, для чего тратит больше памяти.
Плохое:
Тратит много памяти
Злое:
Возможно переполнение стека, как и у рекурсии

Динамическое программирование

После решения с запоминанием становится понятно, что нам нужны не все предыдущие результаты, а только два последних. Кроме этого, вместо того, чтобы начинать с fib(n) и идти назад, можно начать с fib(0) и идти вперёд. У следующего кода линейное время выполнение, а использование памяти – фиксированное. На практике скорость решения будет ещё выше, поскольку тут отсутствуют рекурсивные вызовы функций и связанная с этим работа. И код выглядит проще.

Это решение часто приводится в качестве примера динамического программирования.

def fib(n):
    a = 0
    b = 1
    for __ in range(n):
        a, b = b, a + b
    return a

Хорошее:
Быстро работает для малых n, простой код
Плохое:
Всё ещё линейное время выполнения
Злое:
Да особо ничего.

Матричная алгебра

И, наконец, наименее освещаемое, но наиболее правильное решение, грамотно использующее как время, так и память. Его также можно расширить на любую гомогенную линейную последовательность. Идея в использовании матриц. Достаточно просто видеть, что

А обобщение этого говорит о том, что

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

Так чем же полезна такая формулировка? Тем, что возведение в степень можно произвести за логарифмическое время. Это делается через возведения в квадрат. Суть в том, что

где первое выражение используется для чётных A, второе для нечётных. Осталось только организовать перемножения матриц, и всё готово. Получается следующий код. Я организовал рекурсивную реализацию pow, поскольку её проще понять. Итеративную версию смотрите тут.

def pow(x, n, I, mult):
    """
    Возвращает x в степени n. Предполагает, что I – это единичная матрица, которая 
    перемножается с mult, а n – положительное целое
    """
    if n == 0:
        return I
    elif n == 1:
        return x
    else:
        y = pow(x, n // 2, I, mult)
        y = mult(y, y)
        if n % 2:
            y = mult(x, y)
        return y


def identity_matrix(n):
    """Возвращает единичную матрицу n на n"""
    r = list(range(n))
    return [[1 if i == j else 0 for i in r] for j in r]


def matrix_multiply(A, B):
    BT = list(zip(*B))
    return [[sum(a * b
                 for a, b in zip(row_a, col_b))
            for col_b in BT]
            for row_a in A]


def fib(n):
    F = pow([[1, 1], [1, 0]], n, identity_matrix(2), matrix_multiply)
    return F[0][1]

Хорошее:
Фиксированный объём памяти, логарифмическое время
Плохое:
Код посложнее
Злое:
Приходится работать с матрицами, хотя они не так уж и плохи

Сравнение быстродействия

Сравнивать стоит только вариант динамического программирования и матрицы. Если сравнивать их по количеству знаков в числе n, то получится, что матричное решение линейно, а решение с динамическим программированием – экспоненциально. Практический пример – вычисление fib(10 ** 6), числа, у которого будет больше двухсот тысяч знаков.

n = 10 ** 6
Вычисляем fib_matrix: у fib(n) всего 208988 цифр, расчёт занял 0.24993 секунд.
Вычисляем fib_dynamic: у fib(n) всего 208988 цифр, расчёт занял 11.83377 секунд.

Теоретические замечания

Не напрямую касаясь приведённого выше кода, данное замечание всё-таки имеет определённый интерес. Рассмотрим следующий граф:

Подсчитаем количество путей длины n от A до B. Например, для n = 1 у нас есть один путь, 1. Для n = 2 у нас опять есть один путь, 01. Для n = 3 у нас есть два пути, 001 и 101. Довольно просто можно показать, что количество путей длины n от А до В равно в точности F_n. Записав матрицу смежности для графа, мы получим такую же матрицу, которая была описана выше. Это известный результат из теории графов, что при заданной матрице смежности А, вхождения в Аⁿ — это количество путей длины n в графе (одна из задач, упоминавшихся в фильме «Умница Уилл Хантинг»).

Почему на рёбрах стоят такие обозначения? Оказывается, что при рассмотрении бесконечной последовательности символов на бесконечной в обе стороны последовательности путей на графе, вы получите нечто под названием «подсдвиги конечного типа», представляющее собой тип системы символической динамики. Конкретно этот подсдвиг конечного типа известен, как «сдвиг золотого сечения», и задаётся набором «запрещённых слов» {11}. Иными словами, мы получим бесконечные в обе стороны двоичные последовательности и никакие пары из них не будут смежными. Топологическая энтропия этой динамической системы равна золотому сечению ϕ. Интересно, как это число периодически появляется в разных областях математики.

Задача: посчитать N-е число последовательности, в которой каждый элемент равен сумме двух предыдущих. Такая последовательность называется последовательностью Фибоначчи: 1, 1, 2, 3, 5, 8…

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

int fibo(int n)
{
    if (n == 1 || n == 2) {
        return 1;
    } else {
        return fibo(n - 1) + fibo(n - 2);
    }
}

Давайте подумаем, почему так происходит. Например, для вычисления fibo(30) мы сначала вычисляем fibo(29) и fibo(28). Но при этом наша программа «забывает», что fibo(28) мы уже вычисляли при поиске fibo(29).

Основная ошибка такого подхода «в лоб» в том, что одинаковые значения аргументов функции исчисляются многократно — а ведь это достаточно ресурсоемкие операции. Избавиться от повторяющихся вычислений нам поможет метод динамического программирования — это прием, при использовании которого задача разбивается на общие и повторяющиеся подзадачи, каждая из которых решается только 1 раз — это значительно повышает эффективность программы. Этот метод подробно описан в нашей статье, там же есть и примеры решения других задач.

Самый просто вариант улучшения нашей функции — запоминать, какие значения мы уже вычисляли. Для этого нужно ввести дополнительный массив, который будет служить как бы «кэшем» для наших вычислений: перед вычислением нового значения мы будем проверять, не вычисляли ли его раньше. Если вычисляли, то будем брать из массива готовое значение, а если не вычисляли — придётся считать его на основе предыдущих и запоминать на будущее:

int cache[100];

int fibo(int n)
{
    if (cache[n] == 0) {
        if (n == 1 || n == 2) {
            cache[n] = 1;
        } else {
            cache[n] = fibo(n - 1) + fibo(n - 2);
        }
    }

    return cache[n];
}

Так как в данной задаче для вычисления N-ого значения нам гарантированно понадобится (N-1)-е, то не составит труда переписать формулу в итерационный вид — просто будем заполнять наш массив подряд до тех пор, пока не дойдём до нужной ячейки:

cache[0] = 1;
cache[1] = 1;

for (int i = 2; i <= n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
}

cout << cache[n-1];

Теперь мы можем заметить, что когда мы вычисляем значение F(N), то значение F(N-3) нам уже гарантированно никогда не понадобится. То есть нам достаточно хранить в памяти лишь два значения — F(N-1) и F(N-2). Причём, как только мы вычислили F(N), хранение F(N-2) теряет всякий смысл. Попробуем записать эти размышления в виде кода:

//Два предыдущих значения:
int cache1 = 1;
int cache2 = 1;
//Новое значение
int cache3;

for (int i = 2; i <= n; i++) {
    cache3 = cache1 + cache2; //Вычисляем новое значение

    //Абстрактный cache4 будет равен cache3+cache2
    //Значит cache1 нам уже не нужен?..

    //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации.
    //cache5 = cache4 - cache3 => через итерацию потеряет актуальность cache2, т.е. он и должен стать cache1

    //Иными словами, cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n).
    //Пусть N=n+1 (номер, который мы вычисляем на следующей итерации). Тогда n-2=N-3, n-1=N-2, n=N-1.
    //В соответствии с новыми реалиями мы и переписываем значения наших переменных:

    cache1 = cache2;
    cache2 = cache3;
}

cout << cache3;

Бывалому программисту понятно, что код выше, в общем-то ерунда, так как cache3 никогда не используется (он сразу записывается в cache2), и всю итерацию можно переписать, используя всего одно выражение:

cache[0] = 1;
cache[1] = 1;
 
for (int i = 2; i <= n; i++) {
    cache[i%2] = cache[0] + cache[1];
    //При i=2 устареет 0-й элемент
    //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый
    //При i=4 последним элементом мы обновляли cache[1], значит ненужное старьё сейчас в cache[0]
    //Интуитивно понятно, что так будет продолжаться и дальше
}
 
cout << cache[n%2];

Для тех, кто не может понять, как работает магия с остатком от деления, или просто хочет увидеть более неочевидную формулу, существует ещё одно решение:

int x = 1;
int y = 1;

for (int i = 2; i < n; i++) {
   y = x + y;
   x = y - x;
}

cout << "Число Фибоначчи: " << y;

Попробуйте проследить за выполнением этой программы: вы убедитесь в правильности алгоритма.

P.S. Вообще, существует единая формула для вычисления любого числа Фибоначчи, которая не требует никаких итераций или рекурсии:

const double SQRT5 = sqrt(5);
const double PHI = (SQRT5 + 1) / 2;

int fibo(int n){
    return int(pow(PHI, n) / SQRT5 + 0.5);
}

Но, как можете догадаться, подвох в том, что цена вычисления степеней нецелых чисел довольно велика, как и их погрешность.

Фибоначчи был первым математиком, обнаружившим в природном мире тенденцию среди растений следовать в своем росте ряду определенных чисел. До 90% всех видов флоры подчиняется данной числовой закономерности на протяжении всей жизни, начиная от количества листьев на стеблях и семян в коробочках, а также включая различные компоненты согласно конкретному типу размножения растения. Числа в этой последовательности были названы «Числа Фибоначчи» в честь первооткрывателя. Они начинаются с двух последовательных единиц (или нуля в определенных источниках, что практически не используется в математической модели), и каждое следующее число представляет собой сумму двух предыдущих:
1,1,2,3,5,8,13,21,…

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