Как вычислить числа Фибоначчи: решение по шагам

Дано: рекуррентная формула $F_k = F_{k-1} + F_{k-2}$ с началом $F_0 = 0$, $F_1 = 1$ и номер члена $n = 30$. Найти: значение $F_{30}$, проверку по формуле Бине и число вызовов наивной рекурсии.

Ряд проходится один раз в цикле, причём хранить нужно только два последних члена, а результат сверяется с $\varphi^{30}/\sqrt{5}$. Ответ: $F_{30} = 832\,040$, цикл делает 29 сложений, наивная рекурсия на том же номере - 2 692 537 вызовов. Калькулятор сверху пересчитывает всё это для любого номера и другого начала ряда, ниже - решение по шагам.

Решение по шагам

Дано. Последовательность задана рекуррентно:

$$F_0 = 0, \qquad F_1 = 1, \qquad F_k = F_{k-1} + F_{k-2} \quad (k \ge 2).$$

Найти: $F_{30}$, проверку независимым способом и цену наивной рекурсии.

Шаг 1. Выписываем начало ряда. Правило не требует ничего, кроме двух предыдущих членов, поэтому первые значения получаются устным счётом:

Отсюда уже видно, что ряд растёт быстро, но не как степень двойки: $F_{10} = 55$, тогда как $2^{10} = 1024$. Скорость роста определяет золотое сечение, к этому вернёмся после решения.

Шаг 2. Идём по ряду итеративно. Держать весь массив незачем: для очередного члена хватает двух предыдущих. Заводим переменные $a = F_{k-2}$ и $b = F_{k-1}$ и сдвигаем их ровно $n - 1 = 29$ раз:

a, b = 0, 1              # F(0) и F(1)
for _ in range(n - 1):   # при n = 30 это 29 шагов
    a, b = b, a + b
# после цикла b = F(n)

Проверить число шагов легко на краю: при $n = 1$ цикл не выполняется ни разу и $b$ остаётся равным $F_1 = 1$. Значит, для тридцатого члена нужно 29 сложений, а не 30. Хвост прохода выглядит так:

Последнее сложение цикла - это $317\,811 + 514\,229 = 832\,040$.

Шаг 3. Проверяем результат формулой Бине. Формула выражает член ряда через золотое сечение и не опирается на предыдущие значения:

$$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}, \qquad \varphi = \frac{1 + \sqrt{5}}{2} \approx 1{,}6180339887, \qquad \psi = \frac{1 - \sqrt{5}}{2} \approx -0{,}6180339887.$$

Подставляем $n = 30$. Первое слагаемое: $\varphi^{30} \approx 1\,860\,498{,}0$, делим на $\sqrt{5} \approx 2{,}2360680$ и получаем $832\,040{,}0000002$. Второе слагаемое по модулю равно $|\psi|^{30}/\sqrt{5} \approx 2{,}4 \cdot 10^{-7}$, то есть намного меньше половины единицы. Поэтому ответ - просто округление первого слагаемого:

$$F_{30} = \left\lfloor \frac{\varphi^{30}}{\sqrt{5}} + \frac{1}{2} \right\rfloor = 832\,040.$$

Два независимых способа дали одно и то же число, значит, в проходе по ряду ошибки нет.

Шаг 4. Считаем, во что обошлась бы наивная рекурсия. Функция, которая честно вызывает себя дважды на каждом уровне, делает $T(k) = 1 + T(k-1) + T(k-2)$ вызовов, а это ровно $T(n) = 2F_{n+1} - 1$:

$$T(30) = 2 \cdot F_{31} - 1 = 2 \cdot 1\,346\,269 - 1 = 2\,692\,537.$$

Против 29 сложений в цикле это больше почти в 93 тысячи раз, и разрыв растёт с каждым следующим номером.

Ответ: $F_{30} = 832\,040$. Формула Бине даёт то же значение, итеративный проход стоит 29 сложений, а наивная рекурсия без запоминания промежуточных результатов - 2 692 537 вызовов.

Формула и откуда она берётся

Рекуррентность $F_k = F_{k-1} + F_{k-2}$ линейна и однородна, поэтому у неё есть решение в виде геометрической прогрессии. Подставим пробное $F_k = x^k$ и сократим на $x^{k-2}$:

$$x^{k} = x^{k-1} + x^{k-2} \quad \Longrightarrow \quad x^{2} = x + 1 .$$

Это характеристическое уравнение ряда. Его корни $\varphi = \tfrac{1+\sqrt{5}}{2}$ и $\psi = \tfrac{1-\sqrt{5}}{2}$ - те самые числа из формулы Бине; первый из них и есть золотое сечение. Любая комбинация $F_n = A\varphi^n + B\psi^n$ удовлетворяет рекуррентности, а начальные условия выбирают из этого семейства единственную последовательность.

Из $F_0 = 0$ следует $A + B = 0$, из $F_1 = 1$ получается $A\varphi + B\psi = 1$. Подставив $B = -A$, имеем $A(\varphi - \psi) = 1$, а разность корней равна $\sqrt{5}$. Отсюда $A = 1/\sqrt{5}$ и $B = -1/\sqrt{5}$, что и даёт формулу из шага 3.

Ключевая деталь - модуль второго корня: $|\psi| \approx 0{,}618 < 1$, поэтому $\psi^n$ убывает и уже при $n = 10$ вклад этого слагаемого меньше сотой доли единицы. Значит, при любом $n \ge 0$ достаточно взять первое слагаемое и округлить его до ближайшего целого. Тот же вывод получается через производящие функции: там ряд Фибоначчи сворачивается в дробь $x/(1 - x - x^2)$, и разложение на простейшие дроби приводит к тем же $\varphi$ и $\psi$ - подробный разбор этого пути есть в статье про метод производящих функций.

Быстрый способ: удвоение вместо прохода по всему ряду

Когда номер большой, 29 сложений превращаются в миллион, и проход по ряду перестаёт быть быстрым. Тогда используют тождества удвоения, которые сразу перепрыгивают от номера $k$ к номеру $2k$:

$$F_{2k} = F_k \bigl(2F_{k+1} - F_k\bigr), \qquad F_{2k+1} = F_k^{2} + F_{k+1}^{2}.$$

Проверим их на нашей задаче. Возьмём $k = 15$, где $F_{15} = 610$ и $F_{16} = 987$:

$$F_{30} = 610 \cdot (2 \cdot 987 - 610) = 610 \cdot 1364 = 832\,040 .$$

Совпало с итеративным ответом. Попутно получается и соседний член: $F_{31} = 610^{2} + 987^{2} = 372\,100 + 974\,169 = 1\,346\,269$ - то самое число, которое понадобилось в шаге 4. Рекурсия по этим тождествам делает порядка $\log_2 n$ шагов: для $n = 30$ это пять удвоений вместо двадцати девяти сложений.

Та же идея в матричной записи: возведение матрицы $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ в степень $n$ даёт в углах числа $F_{n+1}$, $F_n$ и $F_{n-1}$, а сама степень считается двоичным алгоритмом. Механика обоих приёмов разобрана в задачах про быстрое возведение в степень и возведение матрицы в степень.

Отношение соседних чисел и золотое сечение

Разделим каждый член на предыдущий: $1$, $2$, $1{,}5$, $1{,}667$, $1{,}6$, $1{,}625$, $1{,}615$, $1{,}619$ - значения скачут то выше, то ниже, но размах быстро сжимается. На тридцатом номере отношение уже неотличимо от золотого сечения на глаз:

$$\frac{F_{30}}{F_{29}} = \frac{832\,040}{514\,229} = 1{,}6180339887482, \qquad \varphi = 1{,}6180339887499 .$$

Причина видна из формулы Бине. Поделив $A\varphi^n + B\psi^n$ на $A\varphi^{n-1} + B\psi^{n-1}$, получаем $\varphi$ плюс поправку порядка $(\psi/\varphi)^n$, а отношение $|\psi|/\varphi \approx 0{,}382$ меньше единицы. Знак поправки меняется с каждым шагом, потому что $\psi$ отрицателен, - отсюда и колебания вокруг предела. Переключи график калькулятора сверху в режим отношения: линия видимо прижимается к пунктиру золотого сечения примерно к десятому номеру.

Правило сохраняется и для других начальных значений. Если взять $F_0 = 2$, $F_1 = 1$, получатся числа Люка $2, 1, 3, 4, 7, 11, 18, \dots$ - ряд другой, а предел отношения тот же, потому что характеристическое уравнение не изменилось. Меняются только коэффициенты $A$ и $B$.

Частые ошибки

• Сдвиг нумерации. Часть учебников начинает ряд с $F_1 = F_2 = 1$, и тогда «тридцатое число» оказывается нашим $F_{29} = 514\,229$. В ответе всегда указывай, от какого начала считал.
• Лишняя итерация в цикле. Проход из $n$ шагов вместо $n-1$ выдаёт $F_{31} = 1\,346\,269$. Проверяй цикл на краю: при $n = 1$ он не должен выполниться ни разу.
• Наивная рекурсия на больших номерах. При $n = 50$ дерево вызовов разрастается до $2F_{51} - 1 \approx 4 \cdot 10^{10}$ - программа зависает. Лечится одной строкой с запоминанием уже посчитанных значений, см. динамическое программирование.
• Переполнение целого типа. Числа растут экспоненциально: $F_{92}$ - последний член, помещающийся в 64-битное знаковое целое, а $F_{93}$ уже выходит за предел и даёт мусор без всякого предупреждения.
• Слепая вера в формулу Бине в программе. В арифметике с плавающей точкой $\varphi^n$ теряет младшие разряды, и примерно после семидесятого номера округление начинает давать не тот ответ. Для больших $n$ нужны целочисленные способы: цикл или удвоение.
• Путаница с числами Люка. Ряд $2, 1, 3, 4, 7, 11$ подчиняется тому же правилу, но это не числа Фибоначчи; сверяй первые члены с условием задачи.

FAQ

Чему равны $F_0$ и $F_1$? В общепринятой нумерации $F_0 = 0$ и $F_1 = 1$, дальше $F_2 = 1$. Эта версия удобна тем, что формула Бине работает без поправок, а тождества удвоения не требуют отдельных оговорок для нулевого члена.

Можно ли считать числа Фибоначчи прямо по формуле Бине? Для небольших номеров - да, округление $\varphi^n/\sqrt{5}$ даёт точный ответ. Но double хранит около шестнадцати значащих цифр, поэтому примерно с семидесятого номера результат расходится с истинным. Если номер большой, считай целыми числами.

Почему наивная рекурсия работает так медленно? Она пересчитывает одни и те же подзадачи заново: $F_{28}$ вычисляется дважды, $F_{27}$ - трижды, и число вызовов растёт как $\varphi^n$. Это классический пример экспоненциальной сложности, разбор оценки такого кода есть в задаче про сложность алгоритма.

Как найти $F_{1000}$? Понадобится длинная арифметика: в этом числе 209 десятичных цифр. Алгоритм - удвоение или матричная степень, они дадут ответ примерно за десять шагов умножения длинных чисел, тогда как обычный цикл потребует тысячи сложений.

Коротко

1. Числа Фибоначчи заданы правилом $F_k = F_{k-1} + F_{k-2}$ при $F_0 = 0$, $F_1 = 1$.
2. Итеративный проход хранит два числа и делает $n - 1$ сложение: для $n = 30$ это 29 шагов и результат $F_{30} = 832\,040$.
3. Проверка формулой Бине: $F_n$ - округление $\varphi^n/\sqrt{5}$, где $\varphi$ - золотое сечение; для тридцатого номера она даёт то же $832\,040$.
4. Формула выводится из характеристического уравнения $x^2 = x + 1$, а второй корень $\psi$ быстро исчезает, потому что $|\psi| < 1$.
5. Наивная рекурсия стоит $2F_{n+1} - 1 = 2\,692\,537$ вызовов, тождества удвоения - около пяти шагов; отношение соседних членов равно $1{,}6180339887482$ против $\varphi = 1{,}6180339887499$.