Что такое последовательность Фибоначчи?
Последовательность Фибоначчи — это ряд целых чисел, в котором каждое число равно сумме двух предыдущих, начиная с 0 и 1: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 и так далее. Она встречается повсюду — и в математике, и в природе: от спиралей раковин и расположения семечек в подсолнухе до золотого сечения. Этот калькулятор возвращает отдельное число Фибоначчи \(F_n\) по любому индексу \(n\) или строит всю последовательность между начальным и конечным индексами.
Как пользоваться калькулятором
Выберите режим в списке Что вычислять. Вариант одно число и ввод индекса \(n\) дадут единственное значение \(F_n\) вместе с шагом рекуррентной формулы. Вариант последовательность и ввод начального и конечного \(n\) выведут все числа Фибоначчи в этом диапазоне (включая границы). Индексы могут быть как положительными, так и отрицательными; допустимый диапазон — от -200 до 200.
Разбор формулы
Основное правило — рекуррентное соотношение $$F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, \; F_1 = 1$$ Чтобы получать точные результаты при больших \(n\), калькулятор использует итерации с целыми числами произвольной точности, а не формулу Бине с плавающей точкой, которая теряет точность примерно после \(n = 71\). Отрицательные индексы подчиняются правилу нега-Фибоначчи \(F_{-n} = (-1)^{n+1} F_n\), поэтому \(F_{-1} = 1\), \(F_{-2} = -1\), \(F_{-3} = 2\), \(F_{-4} = -3\) и так далее.
Пример вычисления
Чтобы найти \(F_{15}\), пройдём по последовательности до индекса 15: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610. Получаем $$F_{15} = 610 = F_{14} + F_{13} = 377 + 233 = 610$$
Частые вопросы
Поддерживаются ли отрицательные индексы? Да. Используется расширение нега-Фибоначчи, которое даёт результаты с чередующимися знаками, например \(F_{-6} = -8\).
Насколько большим может быть n? Допустимый диапазон — от -200 до 200. Например, \(F_{200}\) содержит 42 цифры и вычисляется точно с помощью целых чисел произвольной точности.
Почему не используется формула Бине? Замкнутая формула Бине \(F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}\) удобна для демонстрации, но округление при двойной точности делает её ненадёжной для больших \(n\), поэтому для самого ответа применяется точная целочисленная итерация.
Таблица чисел Фибоначчи (от F0 до F30 и отрицательные индексы)
Последовательность Фибоначчи задаётся условиями \(F_0 = 0\), \(F_1 = 1\) и \(F_n = F_{n-1} + F_{n-2}\). В таблице приведены первые 31 члена.
| n | Fn | n | Fn | n | Fn |
|---|---|---|---|---|---|
| 0 | 0 | 11 | 89 | 22 | 17711 |
| 1 | 1 | 12 | 144 | 23 | 28657 |
| 2 | 1 | 13 | 233 | 24 | 46368 |
| 3 | 2 | 14 | 377 | 25 | 75025 |
| 4 | 3 | 15 | 610 | 26 | 121393 |
| 5 | 5 | 16 | 987 | 27 | 196418 |
| 6 | 8 | 17 | 1597 | 28 | 317811 |
| 7 | 13 | 18 | 2584 | 29 | 514229 |
| 8 | 21 | 19 | 4181 | 30 | 832040 |
| 9 | 34 | 20 | 6765 | ||
| 10 | 55 | 21 | 10946 |
Отрицательные индексы
Последовательность продолжается назад по формуле \(F_{-m} = (-1)^{m+1} F_m\). Нечётное \(m\) даёт положительное значение, а чётное \(m\) — отрицательное.
| n | Fn | Правило знака (-1)m+1, m = |n| |
|---|---|---|
| -1 | 1 | m = 1, знак + |
| -2 | -1 | m = 2, знак − |
| -3 | 2 | m = 3, знак + |
| -4 | -3 | m = 4, знак − |
| -5 | 5 | m = 5, знак + |
| -6 | -8 | m = 6, знак − |
| -7 | 13 | m = 7, знак + |
| -8 | -21 | m = 8, знак − |
| -9 | 34 | m = 9, знак + |
| -10 | -55 | m = 10, знак − |
Как вычислять числа Фибоначчи вручную
- Начните с двух исходных значений \(F_0 = 0\) и \(F_1 = 1\).
- Сложите два предыдущих члена, чтобы получить следующий: \(F_2 = F_1 + F_0 = 1\), \(F_3 = F_2 + F_1 = 2\), \(F_4 = 3\), \(F_5 = 5\) и так далее.
- Повторяйте, пока не дойдёте до индекса n. Для \(n = 10\): 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, поэтому \(F_{10} = 34 + 21 =\) 55.
- Для отрицательного индекса вычислите \(m = |n|\), найдите \(F_m\), затем примените знак \((-1)^{m+1}\). Пример: \(F_{-7} = (-1)^{8} F_7 = (+1)(13) =\) 13. Другой пример: \(F_{-6} = (-1)^{7} F_6 = -8\).
- Проверка через золотое сечение: \(F_n \approx \varphi^n/\sqrt{5}\). Для \(n = 10\) получаем \(\varphi^{10} \approx 122.99\), и \(122.99 / 2.23607 \approx 55.0\), что совпадает. Кроме того, для больших n отношение \(F_{n+1}/F_n\) должно быть близко к 1.618.
- Для очень больших n используйте быстрое удвоение вместо последовательного сложения: \(F_{2k} = F_k\,(2F_{k+1} - F_k)\) и \(F_{2k+1} = F_k^2 + F_{k+1}^2\). Проверка при \(k = 5\): \(F_{10} = F_5(2F_6 - F_5) = 5 \times (16 - 5) = 55\).
Значения растут очень быстро: \(F_{100}\) уже имеет 21 цифру, поэтому для больших n необходима точная целочисленная арифметика (этот калькулятор поддерживает n от −200 до 200).