Часто возникает ситуации, когда нужно выполнить некоторое действие с последовательностью объектов той или иной природы. С самой простой из них мы уже давно знакомы: перебор целых чисел в арифметической прогрессии.

for n in range(start, stop, step):
    do_something(n)

Рассмотрим более сложный пример, перебор чисел Фибоначчи. Конечно же можно писать так:

def fib(n):
    fib1, fib2 = 0, 1
    for i in range(n):
        fib1, fib2 = fib2, fib1 + fib2
    return fib1

for i in range(n):
    do_something(fib(n))

ОК, можно сделать и так:

fib1, fib2 = 0, 1
for i in range(n):
    do_something(fib1)
    fib1, fib2 = fib2, fib1 + fib2

Ну ладно, тогда есть ещё одно решение: сделать список чисел Фибоначчи:

def fibonacci(n):
    fib_list = []
    fib1, fib2 = 0, 1
    for i in range(n):
        fib1, fib2 = fib2, fib1 + fib2
        fib_list.append(fib1)
    return fib_list

for fib in fibonacci(n):
    do_something(fib)

Ленивые вычисления и генераторы

Пример генератора чисел Фибоначчи и нескольких способов им воспользоваться:

def fibonacci(n):
    fib1, fib2 = 0, 1
    for i in range(n):
        fib1, fib2 = fib2, fib1 + fib2
        yield fib1

for fib in fibonacci(20):
    print(fib, end=' ')
print()

print('Сумма первых 100 чисел Фибоначчи равна', sum(fibonacci(100)))
print(list(fibonacci(16)))
print([x*x for x in fibonacci(14)])

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 
Сумма первых 100 чисел Фибоначчи равна 927372692193078999175
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
[1, 1, 4, 9, 25, 64, 169, 441, 1156, 3025, 7921, 20736, 54289, 142129]

Итак, для того, чтобы сделать из обычной функции генератор, нужно вместо return использовать yield. В результате получится не функция, которую можно вызвать и получить результат её работы, а итерируемый объект, из которого можно последовательно выдёргивать результаты его работы до тех пор, пока не будет исполнена последняя строчка кода генератора, либо не будет выполнен выход командой return. При этом после выдачи результата командой yield состояние генератора, все его внутренние переменные сохраняются. При следующей попытке выдернуть элемент из генератора работа начнётся со строчки, следующей за yield.

Чтобы изучить работу генератора чисел Фибоначчи, попробуйте запустить следующий код:

def fibonacci(n):
    print('He we start our generator')
    fib1, fib2 = 0, 1
    print('Init is ready, starting loop with n =', n)
    for i in range(n):
        if i == 0:
            print('It is our first iteration')
        fib1, fib2 = fib2, fib1 + fib2
        print('Going to yield value', fib1, 'while i =', i)
        yield fib1
        print('We are back again! i is still', i, 'and fib1 =', fib1, 'fib2 =', fib2)
    print("It's the last line of our generator... Buy!")
list(fibonacci(5))

Итак, достаточно внутри функции хоть раз воспользоваться командой yield, чтобы сделать из неё генератор. После этого её нельзя вызвать так, как обычно (попробуйте print(fibonacci(5))), но можно использовать в for, list, sorted, map, zip, enumerate и так далее.

Распаковка

def func1():
    return 2, 5, 7

def func2(x, y, z):
    print(x + y + z)

func2(*func1())

Другой пример использования распаковки --- это передача одного и того же набора параметров в разные функции:

def func1(x, y):
    print(x + y)

def func2(x, y):
    print((x ** 2 + y ** 2) ** 0.5)

pars = (3, 7)
func1(*pars)
func2(*pars)

Очень удобно использовать распаковку — внутри функции print:

def fibonacci(n):
    fib1, fib2 = 0, 1
    for i in range(n):
        fib1, fib2 = fib2, fib1 + fib2
        yield fib1
print(*fibonacci(10))

Также при помощи распаковки можно передавать числовые параметры из стандартного ввода в функцию в одну строчку:

def max(a, b, c):
    return max(max(a, b), c)
print(max(*map(int, input().split())))

01: Квадраты чисел Фибоначчи

Напишите генератор square_fibonacci(n), генерирующий последовательность квадратов чисел Фибоначчи. Выведите результат при помощи функции print и распаковки.

7

1 1 4 9 25 64 169

02: Генератор факториалов

Напишите генератор factorials(n), генерирующий последовательность факториалов натуральных чисел.

7

1 2 6 24 120 720 5040

03: Генератор треугольных чисел

Напишите генератор triangular_numbers(n), генерирующий последовательность треугольных чисел.

7

0 1 3 6 10 15 21

04: Степени числа по модулю n

Напишите генератор mod_powers(a, n), генерирующий последовательность степеней числа $a$ по модулю $n$ $a^0, a^1, \ldots, a^k \pmod{n}$ до тех пор, пока очередная степень не будет равна 1. Гарантируется, что числа $a$ и $n$ взаимно просты.

3 7

1 3 2 6 4 5 1

17 256

1 17 33 49 65 81 97 113 129 145 161 177 193 209 225 241 1

05: Биномиальные коэффициенты

Напишите генератор binomial_coefficients(n), генерирующий последовательность биномиальных коэффициентов $C^0_n, C^1_n, \ldots, C^n_n$. Запрещается использовать факториалы.

7

1 7 21 35 35 21 7 1

06: Квадратный корень и Вавилон

Еще 4000 лет назад вавилонские ученые составляли наряду с таблицами умножения и таблицами обратных величин таблицы квадратов чисел и квадратных корней из чисел. При этом они умели находить приблизительное значение квадратного корня из любого целого числа. Для извлечения корня из числа $a$ они использовали последовательность $x_1 = 1$, $x_{n+1} = \displaystyle\frac{1}{2}\left(x_n + \displaystyle\frac{a}{x_n}\right)$, предел которой как раз равен $\sqrt{a}$.

Напишите генератор babylonian_sequence(a), генерирующий данную последовательность до тех пор, пока отличие $x_n^2$ от $a$ не станет меньше $10^{-7}$.

7

1 4.0 2.875 2.654891304347826 2.64576704419029 2.6457513111113693

Генераторы и рекурсия

def abc_gen(n):
    if n == 0:
        yield ''
    else:
        for shorter in abc_gen(n - 1):
            yield 'a' + shorter
            yield 'b' + shorter
print(*abc_gen(4))
>>> 
aaaa baaa abaa bbaa aaba baba abba bbba aaab baab abab bbab aabb babb abbb bbbb

07: Двоичные последовательности

По данному натуральному n≤10 выведите все двоичные последовательности длины n в лексикографическом порядке.

3

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

08: k-ичные последовательности

По данным натуральным n и k (2≤k≤10) выведите все последовательности длины n, составленные из символов 0..k-1. в лексикографическом порядке.

Пример

2 3

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2