Рекурсия и итераторы

Долги за прошлый раз

Про рекурсию

Про генераторы

Вычислимые последовательности.

Itertools (сколько успеем)

Бесконечные последовательности и частичные вычисления, itertools

Д/З

TODO

  1. Прочитать что Гвидо думает о хвостовых рекурсивных вызовах, про итераторы и генераторы, про yield from и про itertools

  2. (это не рекурсия, а вот итератор применить можно ☺)

    EJudge: UniInterval 'Объединение отрезков'

    Вводится кортеж пар натуральных чисел. Это координаты отрезков на прямой. Рассмотрим объединение этих отрезков и найдём длину этого объединения (т. е. совокупную длину всех «закрашенных» нашими отрезками отрезков на прямой).

    Input:

    (66, 91), (152, 230), (21, 81), (323, 342), (158, 211), (286, 332), (294, 330), (18, 58), (183, 236)
    Output:

    213
  3. EJudge: BinPow 'Бинарное возведение в степень'

    Написать рекурсивную функцию BinPow(), которая принимает три параметра: python3-объект a, натуральное число 0<N<1000000, и некоторую ассоциативную бинарную функциюf(). Функция BinPow() реализует алгоритм бинарного возведения в степень (кроме нулевой степени). Результатом BinPow(a, n, f) будет применение f(x) к a n-1 раз. Более точно, BinPow(a, 1, f) == a, BinPow(a, 2, f) == f(a,a), BinPow(a, 3, f) == f(a,f(a, a)) == f(f(a, a), a) (в силу ассоциативности), … BinPow(a, n, f) == f(f(…f(a, a), …), a).

    Input:

    print(BinPow(2,33,int.__mul__), 2**33)
    print(BinPow("Se", 7, str.__add__))
    Output:

    8589934592 8589934592
    SeSeSeSeSeSeSe
  4. EJudge: IterPi 'Пи /кродёться/'

    Пользуясь формулой Лейбница для вычисления числа Пи:

    • LeibnitzPi.png

    написать бесконечный генератор pigen(), возвращающий последовательно 4, 4-4/3, 4-4/3+4/5, 4-4/3+4/5-4/7…;

    Input:

    P=pigen()
    print(next(P), next(P), next(P), next(P), sep="\n")
    Output:

    4.0
    2.666666666666667
    3.466666666666667
    2.8952380952380956
  5. EJudge: ChainSlice 'Режем лазанью'

    Написать функцию chainslice(begin, end, seq0, seq1, …), которая принимает не менее трёх параметров: два целых числа и не менее одной последовательности. Рассмотрим последовательность seq, образованную всеми элементами seq0, затем — всеми элементами seq1, и т. д. Вернуть эта функция должна итератор, пробегающий элементы последовательности seq с №begin до №end-1 включительно.

    Input:

    print(*(chainslice(17, 33, range(7),  range(8),  range(6),  range(9),  range(5))))
    Output:

    2 3 4 5 0 1 2 3 4 5 6 7 8 0 1 2

Д/З мне:

вместо

LecturesCMC/PythonIntro2019/05_RecursionAndIterators (последним исправлял пользователь FrBrGeorge 2020-09-29 12:36:28)