Перебираем числа Фибоначчи с функцией-генератором Python3
newbie
Опубликован: | 2020-04-25T08:35:53.046087Z |
Отредактирован: | 2020-04-25T08:35:53.046087Z |
Числа Фибоначчи — достаточно удобная последовательность для демонстрации одной весьма интересной фичи Питона, а именно функции-генератора. В этом обзоре попробуем разобраться, чем функция-генератора отличается от обычной функции Питона, я продемонстрирую две функции, перебирающие последовательность Фибоначчи:
- первая — функция-генератор, с помощью которой можно создать итератор, возвращающий последовательно на каждой итерации число из последовательности Фибоначчи до определённого предела, предел задан любым целым числом;
- вторая — обычная функция, с помощью которой можно вывести число из последовательности Фибоначчи в соответствии с заданным порядковым номером этого числа в последовательности, порядковые номера начинаются с единицы и следуют до 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!