Итеративно, рекурсивно, генеративно …

В этой статье я поделюсь несколькими способами решения на языке python одной классической математической задачи — получения чисел последовательности Фибонначи.

В 12-13 вв в Европе жил математик Леонардо Пизанский, более известный как Фибоначчи. Как-то на досуге он задумался о скорости размножения кроликов и, пронаблюдав за ними, пришел к выводу, что любая пара кроликов производит на свет другую пару каждый месяц, начиная со второго месяца своего существования. Он решил рассчитать сколько кроликов будет через год и нашел ответ (377 пар), получив числовой ряд: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610… Этот ряд, названный его именем тесно связан с золотым сечением и огромным числом природных и социальных явлений вокруг нас. Расчет его значений производится по следующему уравнению:

Посмотрим, какими путями можно рассчитать эти числа имея под рукой python.

Итеративно

def fib_iter(n):
    a, b = 1, 1
    for i in range(n):
        a, b = b, a + b
    return a
for i in range(0, 10):
    print(i, fib_iter(i))

def fib_iter(n):

a, b = 1, 1

for i in range(n):

a, b = b, a + b

return a

for i in range(0, 10):

print(i, fib_iter(i))

Самый простой и очевидный способ расчета. Расчет числа через цикл, линейное время выполнения. Среди недостатков – расчет одного и того же числа по несколько раз, хотя для каждого следующего нужно всего лишь два предыдущих.

Рекурсивно

def fib_rec(n):
    if n < 2:
        return 1
    return fib_rec(n-1) + fib_rec(n-2)
for i in range(0, 10):
    print(i, fib_rec(i))

def fib_rec(n):

if n < 2:

return 1

return fib_rec(n-1) + fib_rec(n-2)

for i in range(0, 10):

print(i, fib_rec(i))

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

fib_rec = lambda n: fib_rec(n - 1) + fib_rec(n - 2) if n > 1 else 1

1	fib_rec = lambda n: fib_rec(n - 1) + fib_rec(n - 2) if n > 1 else 1

Генеративно

def fib_generator():
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a + b
gen = fib_generator()
for i in range(0, 10):
    print(i, next(gen))

def fib_generator():

a, b = 0, 1

while True:

yield b

a, b = b, a + b

gen = fib_generator()

for i in range(0, 10):

print(i, next(gen))

Используя генератор, при каждом вызове next() выдается новое число ряда. Довольно красиво, просто и быстро.

Сохраняя

Метод подсчета последовательности с сохранением промежуточных элементов называется мемоизацией.

def fib_mem(x, memo):
    if x == 0 or x == 1:
        return 1
    if x in memo:
        return memo[x]
    result = fib_mem(x-1, memo) + fib_mem(x-2, memo)
    memo[x] = result
    return result
for i in range(0, n):
    print(i, fib_mem(i, {}))

def fib_mem(x, memo):

if x == 0 or x == 1:

return 1

if x in memo:

return memo[x]

result = fib_mem(x-1, memo) + fib_mem(x-2, memo)

memo[x] = result

return result

for i in range(0, n):

print(i, fib_mem(i, {}))

Каждое число сохраняется в словарь, и возвращается оттуда по надобности. На расчет уходит линейное время.

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