Калькулятор чисел Фибоначчи

F(1) = 1, F(2) = 1, F(n) = F(n − 1) + F(n − 2) ⇒ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …; отношение соседних членов → φ = (1 + √5) / 2 = 1,6180339887…

F(n)

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

F(1) = 1, F(2) = 1

Два начальных значения, с которых начинается отсчёт. Именно здесь расходятся два соглашения: эта страница берёт F(1) = F(2) = 1, а распространённое второе — F(0) = 0, F(1) = 1, и тогда все номера сдвигаются на единицу

n

Сколько членов вывести, от 2 до 78. Нижняя граница не случайна: чтобы отношение существовало, нужны два члена, и на единице делить было бы не на что, поэтому страница отказывает, а не печатает пустую строку

F(n) / F(n − 1)

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

φ = (1 + √5) / 2

Золотое сечение, 1,6180339887… — положительный корень уравнения x² = x + 1. Это уравнение есть та же рекуррентная формула, записанная иначе: если отношения к чему-то сходятся, то это «что-то» обязано ему удовлетворять. Поэтому последовательность и приходит к φ, а не приближается к нему случайно

78 членов

Потолок страницы. F(78) = 8 944 394 323 791 464 — последний член, который число двойной точности хранит точно; начиная с F(79) ответы перестали бы быть точными, и страница отказывает, а не печатает приближение

Проверить конкретный член — самое простое применение: в задаче спрашивают десятое число Фибоначчи или последовательность в учебнике уходит дальше, чем хочется складывать вручную, а страница выдаёт и значение, и весь ряд, который к нему привёл. Вывод с отношением отвечает на другой вопрос — откуда берётся золотое сечение. Увидеть, как 2, 1,5, 1,6667, 1,6, 1,625, 1,615 сходятся к 1,618, — куда более короткий путь к пониманию связи, чем чтение доказательства, и таблица на этой странице построена ровно под такое чтение. Третье применение — программирование и учёба: эта рекуррентная формула — стандартный первый пример рекурсии, а сама последовательность — стандартный пример рекурсивного определения, которое итеративно считается несравнимо дешевле; цикл на этой странице как раз итеративный, поэтому 78 членов не стоят ничего. Те же числа появляются в задачах на оценку, где рост накапливается сам на себе: число способов замостить полосу квадратами и доминошками, число путей по лестнице, если шагать на одну или две ступеньки, и количество ветвей у растения, которое делится каждый сезон, подчиняются той же рекуррентной формуле. Когда вопрос не о последовательности, а о самом числе, золотое сечение разбирается на отдельной странице как самостоятельная величина со своими свойствами; когда важен ровный рост, а не ступенчатый, его описывает страница про экспоненциальный рост.

1. Первые десять членов: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

   1. Начните с 1 и 1 — двух начальных значений, которые использует эта страница
   2. 1 + 1 = 2, затем 1 + 2 = 3, затем 2 + 3 = 5, затем 3 + 5 = 8
   3. Продолжайте: 5 + 8 = 13, 8 + 13 = 21, 13 + 21 = 34, 21 + 34 = 55
   4. Членов десять, значит десятый равен 55; отношение двух последних — 55 ÷ 34 = 1,61764706

   Ввод по умолчанию. Обратите внимание: десятый член равен 55, а отношение 55 к 34 — 1,61764706, то есть близко к золотому сечению, но уже в третьем знаке после запятой видно расхождение. Именно поэтому за последовательностью и интересно следить, а не просто подсматривать ответ: сходимость быстрая, но не мгновенная, и десяти членов пока не хватает, чтобы восемь напечатанных знаков дошли до 1,61803399.

2. Самая короткая выдача: два члена

   1. Два члена — это самый маленький запрос, который принимает страница
   2. Последовательность — это просто два начальных значения: 1 и 1
   3. Второй член равен 1, поэтому и в строке n-го члена стоит 1
   4. Отношение равно 1 ÷ 1 = 1 — дальше от золотого сечения эта страница не бывает

   Нижняя граница и объяснение, почему она равна двум, а не единице. Выводу с отношением нужны два члена, чтобы вообще существовать; при одном члене делить было бы не на что, поэтому страница отказывает в единице, а не печатает пустую строку или ноль. Отношение, равное единице, — это ещё и начало всей сходимости: каждое следующее отношение делает шаг от него, и путь от 1 к 1,618 разложен в таблице ниже член за членом.

3. Где отношение успокаивается: двадцать членов

   1. Продолжите ряд от десятого члена: 34 + 55 = 89, 55 + 89 = 144 и так далее
   2. Двадцатый член равен 6 765, а девятнадцатый — 4 181
   3. 6 765 ÷ 4 181 = 1,61803396317…
   4. Округлённое до восьми знаков, которые печатает страница, это 1,61803396

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

Число членов должно быть целым от 2 до 78. Единица отклоняется, потому что выводу с отношением нужны два члена, а 79 — потому что точность там заканчивается: F(78) = 8 944 394 323 791 464, это последнее число Фибоначчи, которое точно помещается в значение двойной точности, а F(79) уже выходит за потолок в 9 007 199 254 740 991. Страница отказывает в таком запросе, а не возвращает приблизительный член: число, которое почти верно, но напечатано шестнадцатью цифрами, выглядит ровно как правильное. Отсчёт ведётся с единицы, эта страница использует F(1) = F(2) = 1. Второе распространённое соглашение задаёт F(0) = 0 и F(1) = 1, и тогда все номера сдвигаются на единицу: по нему пятый член равен 5, а здесь он равен 8. Оба соглашения встречаются и в учебниках, и в программах, поэтому если вы сравниваете эту страницу с другим источником и числа расходятся на одну позицию, дело именно в этом, а не в ошибке. Вывод с отношением — это оценка, напечатанная до восьми знаков; при конечном числе членов она никогда не равна золотому сечению точно, хотя к семьдесят восьмому члену напечатанное значение и само золотое сечение совпадают всеми восемью знаками. Ещё одна деталь про формат: члены печатаются списком через запятую и без разделителей разрядов, поэтому десятый член читается как 55, а семьдесят восьмой — как 8944394323791464. Строка n-го члена ведёт себя иначе: это числовой вывод, и он подчиняется правилам языка, так что то же самое значение печатается там как 8 944 394 323 791 464. Это не расхождение, а разная природа двух строк: длинные члены удобнее читать в строке n-го члена, чем в списке. Наконец, таблица ниже зафиксирована на первых десяти членах и не следует за вашим вводом; она нужна, чтобы показать, как успокаивается отношение, а не чтобы ответить на введённое число.

Последовательность начинается с F(0) или с F(1)?

Эта страница начинает с F(1): F(1) = 1, F(2) = 1, F(3) = 2, а десятый член равен 55. Второе широко распространённое соглашение задаёт F(0) = 0 и F(1) = 1, и тогда все номера сдвигаются на единицу — по нему пятый член равен 5, а здесь он равен 8. Оба соглашения используются и в учебниках, и в программах, и ни одно из них не ошибка. Но если вы сравниваете эту страницу с другим источником и значения расходятся ровно на одну позицию, причина именно в этом: это самый частый способ получить неверный ответ про числа Фибоначчи.

Почему отношение всё время меняется, а не устанавливается сразу?

Потому что это предел, а не тождество. Каждый член равен сумме двух предыдущих, поэтому отношение соседних членов подчиняется своему собственному правилу: оно перескакивает то выше цели, то ниже, а размах каждого следующего скачка примерно вдвое меньше предыдущего. В таблице это видно: 2, затем 1,5, затем 2, затем 1,667, затем 1,6, затем 1,625, и дальше уже 1,615 и 1,619. Десяти членов мало, двадцати хватает на восемь напечатанных знаков, а точным золотым сечением не станет никакое конечное число членов — оно будет только всё ближе.

Что такое золотое сечение и почему последовательность к нему приходит?

Золотое сечение — это 1,6180339887…, положительный корень уравнения x² = x + 1. Это уравнение и есть рекуррентная формула, записанная по-другому: если отношения к чему-то сходятся, то это число обязано ему удовлетворять. Поэтому последовательность к нему и приходит, и это не совпадение и не курьёз. Заодно это самое «иррациональное» число из всех — его хуже всего приближают дробями, потому что его непрерывная дробь состоит из одних единиц, — и именно этим свойством пользуются растения, располагая листья и семена.

Почему можно запросить только 78 членов?

Потому что F(79) больше самого большого целого числа, которое значение двойной точности хранит точно: этот потолок равен 9 007 199 254 740 991. F(78) = 8 944 394 323 791 464 и он точен, а F(79) был бы записан как число, близкое к настоящему, но не равное ему. Страница отказывает в таком запросе вместо того, чтобы напечатать приближение: член, напечатанный шестнадцатью цифрами, выглядит точно так же, как правильный, и увидеть ошибку по выводу невозможно. Ограничение — факт про числа с плавающей запятой, а не про математику: сама последовательность бесконечна.

Откуда взялась задача о кроликах?

Фибоначчи ввёл последовательность именно загадкой: возьмите одну пару кроликов, пусть каждая пара месяц взрослеет, а затем каждый месяц приносит новую пару, и считайте пары в начале каждого месяца. Числа получаются 1, 1, 2, 3, 5, 8 и так далее, потому что все взрослые пары прошлого месяца живы и по-прежнему приносят потомство, а новая пара берётся у тех, кто созрел месяц назад, — это и есть рекуррентная формула, полученная с совершенно другой стороны. Знать об этом стоит потому, что задача показывает: последовательность не определяется каким-то одним применением.

Можно ли вычислить n-й член, не перечисляя предыдущие?

В принципе да, и строка n-го члена выдаёт это число отдельно, но получается оно тем же циклом, а не по короткой формуле. Причина — точность: замкнутая формула есть, это формула Бине, она даёт n-е число Фибоначчи прямо через золотое сечение, но в ней иррациональное число возводится в степень, и в арифметике с плавающей запятой результат уходит от настоящего целого уже на небольших n. Сложение целых точно там, где эта формула неточна, поэтому страница складывает. Да и 78 членов ничего не стоят именно потому, что здесь нет формулы, которую надо решать: только сложение, повторённое 76 раз.

• Fibonacci Number — the recurrence, the closed form in terms of the golden ratio, and the identity that makes the ratio converge on it — Wolfram MathWorld (United States)
• Golden Ratio — the number 1.6180339887…, its definition as the positive root of x² = x + 1, and why it is the hardest number to approximate with fractions — Wolfram MathWorld (United States)
• Continued Fraction — why the all-ones continued fraction of the golden ratio is exactly what makes the Fibonacci ratios converge on it — Wolfram MathWorld (United States)