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

webmaster

Опубликован:  2021-04-20T05:27:03.890116Z
Отредактирован:  2021-04-20T05:25:00.155278Z
25
0
0
Вы неавторизованы, рекомендую зарегистрироваться и авторизоваться.

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

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

nvim 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 и сохраняю его.

refKpE3oEn.png

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

>>> 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 
>>> 

5bjYOnuMIh.png

Так как использованное в примере в качестве ограничения число 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
        # и уходим на следующий шаг бесконечного цикла

UXThHoaixU.png

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

>>> import fibo 
>>> fibo.find_fib(1) 
0 
>>> fibo.find_fib(2) 
1 
>>> fibo.find_fib(25) 
46368 
>>> 

xYPhIYzHua.png

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

8FRSUAICkQ.png

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

FSCCIJ5EGO.png

Wow!

1. Важная информация для постоянных читателей

Уважаемый читатель, списки auriz.ru не имеет спонсоров и финансирования, и чтобы выжить мы можем рассчитывать только на поддержку своих постоянных читателей и их пожертвования. Если вам оказалась полезна эта или другая статья этого сайта, и вы хотите больше интересных материалов на auriz.ru, поддержите нас рублём, ваша поддержка даст нам шанс выжить, оплатить продление домена и VDS, написать и опубликовать для вас другие интересные материалы.

Поддержать нас можно переводом любой приемлемой для вас суммы на мой кошелёк yoomoney. Важно помнить, что перевод на пять рублей - лучше, чем никакого перевода, а без вашей помощи проект почти наверняка загнётся и прекратит существование очень скоро.

Важное замечание: оригинальные статьи блогов auriz.ru являются авторским контентом и защищены авторским правом, не допускается копирование и тиражирование материалов сайта на других ресурсах сети или в печатных изданиях без согласования с автором блога и администратором этого сайта, не воруйте у нас оригинальные материалы, мы создаём их только и исключительно для читателей нашего сайта.

Комментарии: