Перебираем числа Фибоначчи с функцией-генератором Python3

Числа Фибоначчи — достаточно удобная последовательность для демонстрации одной весьма интересной фичи Питона, а именно функции-генератора. В этом обзоре попробуем разобраться, чем функция-генератора отличается от обычной функции Питона, я продемонстрирую две функции, перебирающие последовательность Фибоначчи:

• первая — функция-генератор, с помощью которой можно создать итератор, возвращающий последовательно на каждой итерации число из последовательности Фибоначчи до определённого предела, предел задан любым целым числом;
• вторая — обычная функция, с помощью которой можно вывести число из последовательности Фибоначчи в соответствии с заданным порядковым номером этого числа в последовательности, порядковые номера начинаются с единицы и следуют до 800 включительно, как увидим чуть позже, восьмисотое по счёту число последовательности имеет просто гигантское с точки зрения обычного человека значение.

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

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

Для реализации задуманного мне понадобится новый модуль, создаю файл с именем fibo.py и открываю его в любом тестовом редакторе. Начнём с первой функции.

Функция-генератор всегда возвращает итератор. От обычной функции она отличается тем, что не использует return, и вместо этого использует yield. Кроме этого, функция-генератор сохраняет значения локальных переменных между итерациями. Посмотрим, как эти свойства функции-генератора можно использовать для нашего примера, чтобы воспроизвести с её помощью последовательность Фибоначчи. Создаю в файле fibo.py функцию fibs.

def fibs(n):
    # у нас есть два числа, a и b,
    a, b = 0, 0
    # начинаем бесконечный цикл с этими числами,
    while True:
        # проверяем значения a и b,
        if not a and not b:
            # если условие выполняется,
            # изменяем значение b,
            b += 1
            # отдаём в итератор 0
            yield 0
            # и уходим на следующий шаг
            # бесконечного цикла,
        # на следующем шаге бесконечного цикла
        # первое условие не выполнится, так как
        # b имеет значение 1
        # проверяем второе условие
        if not a and b == 1:
            # если условие выполняется, отдаём в
            # итератор единицу
            yield 1
            # и уходим на следующий шаг
            # бесконечного цикла,
        # на следующем шаге бесконечного цикла
        # первые два условия не будут выполнены,
        # создаём переменную c и присваиваем ей
        # сумму значений a и b,
        c = a + b
        # проверяем значение переменной c,
        if c <= n:
            # если условие выполняется,
            # отдаём в итератор значение c,
            yield c
            # даём переменным a и b новые значения
            a, b = b, c
            # и уходим на следующий шаг
            # бесконечного цикла,
        else:
            # если же условие не выполняется,
            # прерываем бесконечный цикл
            break

Пишу код этой функции в файл fibo.py и сохраняю его.

Давайте посмотрим, как это работает, запускаю в терминале интерпретатор Python3, импортирую созданный модуль и пробую получить искомую последовательность до 500 включительно, чуть выше в этом тексте видно, что такая последовательность должна закончиться числом 377, так как следующее за ним число 610 уже больше, чем 500.

$ python3 
Python 3.7.3 (default, Dec 20 2019, 18:57:59)  
[GCC 8.3.0] on linux 
Type "help", "copyright", "credits" or "license" for more information. 
>>> import fibo               
>>> iterator = fibo.fibs(500) 
>>> while True: 
...     try: 
...         print(next(iterator)) 
...     except StopIteration: 
...         break 
...  
0 
1 
1 
2 
3 
5 
8 
13 
21 
34 
55 
89 
144 
233 
377 
>>> 

Так как использованное в примере в качестве ограничения число 500 не является числом Фибоначчи, мой созданный функцией fibs итератор дошёл в переборе до 377 включительно, а затем сгенерировал исключение StopIteration. Показанный в интерактивной сессии пример использует протокол итерации, который предполагает, что встроенная функция next возвращает следующее значение итератора, или генерирует исключение StopIteration, если итератор достиг своего предела.

Во втором примере я покажу обычную функцию Питона, которая по условию задачи должна возвратить соответствующее заданному порядковому номеру число Фибоначчи. Создаю в файле fibo.py новую функцию - find_fib.

def find_fib(n):
    # ограничиваем значение n заданными пределами,
    if n < 1 or n > 800:
        raise ValueError(f'{n} is a bad value')
    # создаём два первых числа последовательности,
    a, b = 0, 1
    # проверяем первое условие,
    if n == 1:
        # если оно выполняется,
        # возвращаем первое число последовательности,
        return a
    # проверяем второе условие,
    if n == 2:
        # если оно выполняется,
        # возвращаем второе число последовательности,
        return b
    # создаём переменную i,
    i = 3
    # начинаем перебор значений в бесконечном цикле
    while True:
        # создаём переменную c, как сумму
        # первых двух чисел последовательности,
        c = a + b
        # задаём переменным a и b
        # текущие значения последовательности,
        a, b = b, c
        # проверяем условие,
        if i == n:
            # если оно выполняется, возвращаем
            # значение переменной c,
            return c
        # если же оно не выполняется,
        # изменяем значение переменной i
        i += 1
        # и уходим на следующий шаг бесконечного цикла

В итоге у нас получилась довольно простая функция. Иду в интерактивную сессию и пробую find_fib в деле.

$ python3 
Python 3.7.3 (default, Dec 20 2019, 18:57:59)  
[GCC 8.3.0] on linux 
Type "help", "copyright", "credits" or "license" for more information. 
>>> import fibo 
>>> fibo.find_fib(1) 
0 
>>> fibo.find_fib(2) 
1 
>>> fibo.find_fib(25) 
46368 
>>> 

Таким образом у меня есть две полезные функции, обе перебирают числа Фибоначчи, но при этом качественно отличаются друг от друга. Первая — функция-генератор — возвращает итератор, содержащий ограниченную заданным пределом последовательность чисел Фибоначчи. А вторая — обычная функция — возвращает единственное число из последовательности Фибоначчи, соответствующее заданному порядковому номеру. Имея эти две функции я могу без особого труда вывести на экран, например, первые 30 чисел Фибоначчи.

В заданных пределах (до восьмисотого числа Фибоначчи включительно) такой код работает приемлемо быстро. Давайте посмотрим на восьмисотое число Фибоначчи.

Wow!