Как найти число в последовательности фибоначчи

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

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 21 декабря 2022 года; проверки требуют 33 правки.

Чи́сла Фибона́ччи (вариант написания — Фибона́чи^[2]) — элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (последовательность A000045 в OEIS),

в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел^[3]. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи)^[4].

Правда, в некоторых книгах, особенно в старых^{[каких?]}, член , равный нулю, опускается — тогда последовательность Фибоначчи начинается с ^[5][6].

Говоря более формально, последовательность чисел Фибоначчи задаётся линейным рекуррентным соотношением:

,

где .

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

n	…	−10	−9	−8	−7	−6	−5	−4	−3	−2	−1	0	1	2	3	4	5	6	7	8	9	10	…
	…	−55	34	−21	13	−8	5	−3	2	−1	1	0	1	1	2	3	5	8	13	21	34	55	…

Легко заметить, что .

Происхождение

Последовательность Фибоначчи была хорошо известна в древней Индии^[7][8][9], где она применялась в метрических науках (просодии, другими словами — стихосложении) намного раньше, чем стала известна в Европе^[8][10][11].

Образец длиной n может быть построен путём добавления S к образцу длиной n − 1, либо L к образцу длиной n − 2 — и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности^[9]. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Книга абака» (1202)^[12][13]. Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, где условия таковы: изначально дана новорождённая пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и производить новую пару кроликов, причём уже каждый месяц; кролики никогда не умирают^[14][15], — а в качестве искомого выдвигает количество пар кроликов через год.

• В начале первого месяца есть только одна новорождённая пара (1).
• В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1).
• В конце второго месяца первая пара рождает новую пару и опять спаривается (2).
• В конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3).
• В конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5).

В конце -го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количеству новорождённых пар, которых будет столько же, сколько пар было два месяца назад, то есть ^[16].
Возможно, эта задача также оказалась первой, моделирующей экспоненциальный рост популяции.

Название «последовательность Фибоначчи» впервые было использовано теоретиком XIX века Эдуардом Люка^[17].

Формула Бине

Формула Бине выражает в явном виде значение как функцию от n:

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

Обоснование

^[18]

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

Таким образом образуется общее уравнение: Чтобы это уравнение обратить в верное равенство и отсюда выразить сами числа Фибоначчи, нужно подставить корни и

Следствие и обобщение

Из формулы Бине следует, что для всех число есть округление то есть
В частности, при справедлива асимптотика

Формула Бине может быть аналитически продолжена следующим образом:

При этом соотношение выполняется для любого комплексного числа z.

Тождества

• ^[20]

• ^[20][21]

• ^[20][22]

Это тождество можно доказать вычитанием первого из второго:

И более общие формулы:

где матрицы имеют размер и где i — мнимая единица.

• С равенством Кассини сопряжено более общее утверждение, названное в честь Эжена Каталана:

Свойства

на множестве неотрицательных целых чисел x и y^[30].

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

  1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS).

• Натуральное число является числом Фибоначчи тогда и только тогда, когда или является квадратом^[31].
• Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи^[32].
• Число Фибоначчи равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом равно количеству таких кортежей, начинающихся с нуля, а  — начинающихся с единицы.
• Произведение любых подряд идущих чисел Фибоначчи делится на произведение первых чисел Фибоначчи.
• Бесконечная сумма чисел, обратных числам Фибоначчи, сходится, его сумма («обратная постоянная Фибоначчи») равна 3,359884…

Вариации и обобщения

В других областях

Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространённый миф, который часто оказывается неточной подгонкой под желаемый результат^[34][35].

В природе

• Филлотаксис (листорасположение) у растений описывается последовательностью Фибоначчи, если листья (почки) на однолетнем приросте (побеге, стебле) имеют так называемое спиральное листорасположение. При этом число последовательно расположенных листьев (почек) по спирали плюс один, а также число совершенных при этом полных оборотов спирали вокруг оси однолетнего прироста (побега, стебля) выражаются обычно первыми числами Фибоначчи.
• Семена подсолнуха, сосновые шишки, лепестки цветков, ячейки ананаса также располагаются согласно последовательности Фибоначчи^{[36][37][38][39]}.

В искусстве

В поэзии чаще находят отношение «золотого сечения» (золотую пропорцию), связанное через формулу Бине с числами Фибоначчи. Например, в поэме Ш. Руставели «Витязь в тигровой шкуре» и на картинах художников^[40].

Однако числа Фибоначчи встречаются и непосредственно в поэзии и в музыке^[41]

В кодировании

В теории кодирования предложены устойчивые так называемые «коды Фибоначчи»^[42], причём основание этих кодов — иррациональное число.

См. также

• Дерево Фибоначчи
• Метод Фибоначчи с запаздываниями
• Метод Фибоначчи поиска экстремума
• Фибоначчи
• Фибоначчиева система счисления
• Числа Бине
• Числа Леонардо
• Таблица Витхоффа
• Последовательность коров Нараяны
• Золотое сечение
• Пропорционирование

Примечания

Литература

• Н. Н. Воробьёв. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).
• А. И. Маркушевич. Возвратные последовательности. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — (Популярные лекции по математике).
• А. Н. Рудаков. Числа Фибоначчи и простота числа 2¹²⁷ − 1 // Математическое Просвещение, третья серия. — 2000. — Т. 4.
• Дональд Кнут. Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol. 1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4.
• Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7.
• Грант Аракелян. Математика и история золотого сечения. — М.: Логос, 2014. — 404 с. — ISBN 978-5-98704-663-0.
• Ball, Keith M (2003), 8: Fibonacci’s Rabbits Revisited, Strange Curves, Counting Rabbits, and Other Mathematical Explorations, Princeton, NJ: Princeton University Press, ISBN 978-0-691-11321-0.
• Beck, Matthias & Geoghegan, Ross (2010), The Art of Proof: Basic Training for Deeper Mathematics, New York: Springer, ISBN 978-1-4419-7022-0.
• Bóna, Miklós (2011), A Walk Through Combinatorics (3rd ed.), New Jersey: World Scientific, ISBN 978-981-4335-23-2.
  • Bóna, Miklós (2016), A Walk Through Combinatorics (4th Revised ed.), New Jersey: World Scientific, ISBN 978-981-3148-84-0.
• Lemmermeyer, Franz (2000), Reciprocity Laws: From Euler to Eisenstein, Springer Monographs in Mathematics, New York: Springer, ISBN 978-3-540-66957-9.
• Livio, Mario. The Golden Ratio: The Story of Phi, the World’s Most Astonishing Number (англ.). — First trade paperback. — New York City: Broadway Books  (англ.) (рус., 2003. — ISBN 0-7679-0816-3.
• Lucas, Édouard (1891), Théorie des nombres, vol. 1, Paris: Gauthier-Villars, Théorie des nombres в «Книгах Google», <https://archive.org/details/thoriedesnombr01lucauoft>.
• Pisano, Leonardo (2002), Fibonacci’s Liber Abaci: A Translation into Modern English of the Book of Calculation, Sources and Studies in the History of Mathematics and Physical Sciences, Springer, ISBN 978-0-387-95419-6

Ссылки

• Первые 300 чисел Фибоначчи (англ.).
• Числа Фибоначчи в природе (англ.).

Fibonacci sequence is one of the most known formulas in number theory. In the Fibonacci sequence, each number in the series is calculated by adding the two numbers before it. Generally, the first two terms of the Fibonacci series are 0 and 1. Fibonacci sequence was known in India hundreds of years before Leonardo Pisano Bigollo know about it. November 23rd is celebrated as Fibonacci Day, as it has the digits “1, 1, 2, 3” which is part of the sequence.

The Fibonacci sequence is as follows: 

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

Fibonacci’s sequence is useful for its operations in advanced mathematics and statistics, computer science, economics, and nature.

Formula of Fibonacci Number

F_n = F_n-1 + F_n-2

• F_n is term number “n”
• F_n−1 is the previous term (n−1)
• F_n−2 is the term before that (n−2)

To calculate the 5th Fibonacci number, add the 4th and 3rd Fibonacci numbers.

Golden Ratio

On choosing any two consecutive (one after the other) Fibonacci numbers, their ratio is near to 1.618034 and it is called Golden Ratio. It is denoted by “φ”. The golden ratio is generally can be seen in nature, and when applied in a design, it fosters natural-seeming works that are pleasing to the eye. There are numerous operations of the golden ratio in the field of architecture. For illustration, the Great Pyramid of Egypt and the Great Mosque of Kairouan is many of the architectural miracles in which the notion of the golden ratio has been applied.  

For example: 

X	Y	Y/X
2	3	1.5
3	5	1.6666
5	8	1.6
8	13	1.625
13	21	1.6154
21	34	1.6190
34	55	1.6176
55	89	1.6181
89	144	1.6179

Note: Golden Ratio can be calculated from Any Fibonacci sequence, it does not necessarily have to start with 2 and 3.

Calculation of Fibonacci number using Golden Ratio

Any Fibonacci number can be calculated by using this formula, 

x_n =  (φⁿ − (1−φ)ⁿ)/√5

x_n denotes Fibonacci number to be calculated

φ is Golden ratio that is 1.618034

For example: If you want to calculate the 7th term:

x₇ = ((1.618034)⁷-(1-1.618034)⁷)/√5

x₇ = 13.0000007

x₇ = 13(rounded off)

The next Fibonacci number can also be calculated using Golden Ratio. Multiplying a Fibonacci number with a golden ratio will give the next Fibonacci number of the sequence. But that only works for numbers greater than 1.

Example: 13*1.618034 = 21.034442 = 21(rounded off)

Some Problems based on Golden Ratio

Question 1: Calculate the 9th Fibonacci number if given golden ratio is 1.618034.

Solution: 

We can calculate the 9th Fibonacci number by using the formula:

x_n =  (φⁿ − (1−φ)ⁿ)/√5

x₉ = ((1.618034)⁹-(1-1.618034)⁹)/√5

x₉ = (76.0131604-(-0.0131556197))/√5 = 34.0000021 

x₉ = 34 

Question 2: Find the next Fibonacci number of answers calculated in the above question.

Solution: 

Next Fibonacci number of 34 can be easily found by multiplying it by the Golden ratio that is 1.618034.

x₁₀ = 34×1.61803 = 55.01302

x₁₀ = 55(rounded off)

Some Problems based on Fibonacci Numbers

Question 1: If the 5th and 6th terms of a Fibonacci sequence are 3 and 5 respectively, find the 7th term of the sequence.

Solution: 

With the use of the Fibonacci Sequence formula, we can easily calculate the 7th term of the Fibonacci sequence which is the sum of the 5th and 6th terms.

seventh term = 5th term + 6th term

= 3+5

= 8

The 7th term of the Fibonacci sequence is 8.

Question 2: The first 4 numbers in the Fibonacci sequence are given as 1,1,2,3.

(a) What is the eighth term of the Fibonacci sequence? 

(b) What is the eleventh term of the Fibonacci sequence? 

Solution: 

By the use of the Fibonacci number formula, we can calculate the rest of the Fibonacci numbers like 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

(a) Therefore, the 8th term will be 21.

(b) 11th term will be 89.

Question 3: Find the next 3 terms for each of the following Fibonacci-style sequences.  

(a) x, 4x, 5x, 9x,… 

(b) 3a, 3a+b, 6a+b, 9a+2b….  

Solution: 

With the use of the Fibonacci Sequence formula, we can easily calculate the rest of the terms

(a) Fifth term = 5x+9x = 14x, 

     Sixth term = 9x+14x = 23x, 

     Seventh term = 14x+23x = 37x

(b) Fifth term = 6a+b+9a+2b = 15a+3b, 

     Sixth term = 9a+2b+15a+3b = 24a+5b, 

     Seventh term = 15a+3b+24a+5b = 39a+8b

Question 4: John wants to generate a Fibonacci series with the first term as 3 and the second term as 4.

(a) Find the 3rd and 4th terms.

(b) He thinks that the sum of the first ten terms is equal to eleven times the seventh term of his sequence. Check if he is correct.

Solution: 

Using the 3 and 4 as first and second terms, we can calculate the rest of the terms by simply adding the last two terms.

(a) First term = 3, 

     Second term = 4, 

     Third Term = 3+4=7, 

     Forth term = 4+7 = 11

(b) On calculating the first ten terms of the series: 3,4,7,11,18,29,47,76,123,199.

      Sum of first ten terms = 3+4+7+11+18+29+47+76+123+199 = 517

      7th term = 47

      Eleven times the 7th term = 11*47 = 517

As we can see that the sum of the first ten terms is equal to eleven times the seventh term of his sequence. Therefore, John was correct.

Question 5: What is the first three-digit square number that appears on the list of Fibonacci numbers, if the first 4 terms are 0,1,1,2.

Solution: 

With the use of the Fibonacci Sequence formula, we can easily calculate the rest of the terms:

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,…

As we can see the first three-digit number which is a square that appears on the list of Fibonacci numbers is 144(square of 12).

Время на прочтение
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}. Иными словами, мы получим бесконечные в обе стороны двоичные последовательности и никакие пары из них не будут смежными. Топологическая энтропия этой динамической системы равна золотому сечению ϕ. Интересно, как это число периодически появляется в разных областях математики.

Числа Фибоначчи — это числа такой последовательности, в которой первые два элемента — 0 и 1, а каждый последующий элемент равен сумме двух предшествующих. Выглядит это так:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …

Примечание Иногда 0 опускается, и в этом случае ряд начинается с 1, но мы будем использовать последовательность с 0 на первой позиции.

Формула записывается следующим образом:

Вычисление ряда Фибоначчи — стандартная задача, которую задают на собеседованиях, чтобы проверить кандидата на понимание алгоритмов. Не так популярна, как сортировка, но всё же.

Давайте вычислим ряд и его отдельные элементы, использовав для этого язык Java.

1. Цикл
2. Рекурсия
3. Stream
4. Тест

Вычислить ряд Фибоначчи циклом

Предположим, что нам нужно вывести на экран первые десять чисел последовательности Фибоначчи. Мы помним, что:

• первый элемент ряда — 0, второй — 1;
• каждый последующий — сумма двух предыдущих.

Тогда наша последовательность будет иметь такой вид:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Но нам нужно вывести результат с использованием программы. Держите код с объяснениями в комментариях:

public class Main{
	public static void main(String[] args) {
	    
	        //Объявляем переменные при известных первых двух:
		int num0 = 0;
		int num1 = 1;
		int num2;
		
		//Первые две переменные выводим вне цикла:
		System.out.print(num0 + " " + num1 + " ");
		for(int i = 3; i <= 10; i++){
			num2 = num0 + num1;
			
			//Каждый следующий элемент выводим в цикле:
			System.out.print(num2 + " ");
			
			//Предыдущим двум переменным присваиваем новые значения:
			num0 = num1;
			num1 = num2;
		}
	}
}

Выполнение завершится на десятом элементе. Количество элементов при этом можно менять, изменив значение в условиях цикла.

Найти число Фибоначчи через рекурсию

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

Почему так происходит? Всё дело в том, что рекурсивная функция приводит к многоразовому вызову одних и тех же операций. Именно из-за этого её не рекомендуется использовать, но если уж на собеседовании прозвучит такая задача, вы будете готовы.

Рассмотрим пример, в котором нам нужно получить n-ое число в ряде Фибоначчи:

public int fibonacciValue(num) {
  if (num <= 1) {
     return 0;
  } else if (num == 2) {
     return 1;
  } else {
     return fibonacciValue(num - 1) + fibonacciValue(num - 2);
  }
}

Если в качестве num задать большое значение, программа зависнет.

Тип int в Java может хранить значения до 2147483647, так что вычислить получится лишь первые 46 чисел Фибоначчи. Тип long хранит до 9223372036854775807, а это 91 число Фибоначчи. Класс BigInteger призван работать с действительно большими значениями, вот только само выполнение программы это никак не ускорит.

Использовать для вычисления Stream

Stream в Java — это компонент для самостоятельной внутренней итерации своих же элементов. Подробнее о нём вы можете почитать в нашей статье о Java Stream API.

И, разумеется, Stream подходит для вычисления элементов последовательности Фибоначчи:

Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
    
   //Задаём лимит значений:
   .limit(num)
   
   //Отбираем по первому элементу каждого массива:
   .map(y -> y[0])
   
   //Выводим в консоль:
   .forEach(x -> System.out.println(x));

В данном примере метод iterate() будет возвращать упорядоченный поток, ограниченный лимитом в num значений и созданный с применением функции к начальному массиву arr. В консоль будет выведено следующее:

{0,1}
{1,1}
{1, 2}
{2, 3}
{3, 5}
{5, 8}
{8, 13}
{13, 21}
…

А так мы получим сумму чисел последовательности по элемент num включительно:

int fibonacciValuesSum = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(num)
     .map(y -> y[0])
     .mapToInt(Integer::intValue)
     .sum();
System.out.println(fibonacciValuesSum);

Математический тест

Любите математику? Попробуйте решить наш математический тест:

---