Числа Фибоначчи

Ряд чисел Фибоначчи представляет собой последовательность. Первый и второй элементы последовательности равны единице. Каждый последующий элемент равен сумме двух предыдущих. Рассмотрим разные способы нахождения элементов по номеру и генерацию списка с помощью Python 3.

Введение

Расчет ряда чисел Фибонначчи – один из лучших примеров программ на Python, использующих рекурсию. Хотя наиболее частый пример, рекурсии – это расчет факториала.

Рассмотрим варианты получения ряда Фибоначчи на Python 3:

• С помощью рекурсии.
• Используя оператор цикла.

Также сгенерируем список чисел и создадим генератор с помощью которого можно поочередно получать числа.

Цикл

Будем искать с помощью цикла for. В переменных prew и cur будут предыдущий элемент последовательности и текущий, их проинициализируем в 1. Если пользователь запросит первый или второй элемент, то мы так и не попадём внутрь тела цикла. И будет выведена единица из переменной cur.

Если же запросят 3-ий или какой либо последующий элемент последовательности Фибоначчи, то мы зайдем в цикл. Во временную переменную tmp сохраним следующее число последовательности. После этого заполним prew и cur новыми значениям. Когда пройдет нужное количество итераций, выведем значение cur в консоль.

prew = cur = 1
element = input('Введите номер искомого элемента : ')
element = int(element)
for n in range(int(element-2)):
    tmp = prew + cur
    prew = cur
    cur = tmp
print(str(element)+' элемент последовательности равен ' + str(cur))

Введите номер искомого элемента : 6
6 элемент последовательности равен 8

В предыдущем коде нам пришлось воспользоваться переменной tmp. Но можно код внутри цикла переписать следующим образом:

prew, cur = cur, prew + cur

Теперь вместо трех строк кода получилась одна строка! И пропала необходимость использования дополнительной переменной.

В этом примере мы использовали цикл for, но можно эту программу реализовать, немного изменив код, с помощью цикла while.

Рекурсия

В случае с рекурсией напишем функцию, аргументом которой будет требуемое число ряда Фибоначчи. Текущему значению последовательности cur вначале присвоим 1. После этого воспользуемся условным оператором языка Python – if. В нем проверим аргумент функции. Если он больше 2, то функция вызовет саму себя и вычислит предыдущее значение ряда, а так же то, которое было еще раньше и запишет в переменную cur их сумму.

def fibonacci(n):
    cur = 1
    if n > 2:
        cur = fibonacci(n-1) + fibonacci(n-2)
    return cur

element = input('Введите номер искомого элемента : ')
element = int(element)
value = fibonacci(element)
print(str(element)+' элемент последовательности равен ' + str(value))

Конечно, пример с рекурсией интересен. Но он будет работать гораздо медленнее.

А если вы решите вычислить, допустим 1000-ый элемент последовательности. Используя цикл, мы его очень быстро рассчитаем. А вот в случае с рекурсией получим ошибку превышения максимального количества рекурсий:

RecursionError: maximum recursion depth exceeded in comparison

Генератор списка

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

def fibonacci(n):
    a, b = 1, 1
    for i in range(n):
        yield a
        a, b = b, a + b

data = list(fibonacci(10))
print(data)

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Здесь fibonacci(10) это генератор объекта ряда размерностью 10. При каждом последующем вызове он будет с помощью yield возвращать очередной элемент. Мы создаём из него список. Затем выводим список в консоль с помощью функции print.

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

def fibonacci():
    a, b = 1, 1
    while True:
        yield a
        a, b = b, a + b

gen = fibonacci()
for i in range(5):
    print(next(gen))

1
1
2
3
5

Здесь мы создали с помощью Python 3 генератор чисел Фибоначчи. При помощи функции next мы получаем поочередно числа ряда.