Задания в классе

Тема занятия - Формулирование абстракций с помощью процедур высшего порядка.

На предыдущих занятиях мы строил абстракции на процедурах. То есть писали и тестировали некоторые процедуры, которые решали определенную задачу. Далее их могли бы использовать другие программисты в своих целях: определять простое ли число, искать сумму цифр числа. В итоге мы написали даже целую утилиту для шифра Виженера.

Но процедурной абстракции не достаточно для построения серьезных систем. Нужен еще один уровень - уровень абстракции процедур высшего порядка.

Рассмотрим следующие задачи:

1. Сумма чисел от 1 до $N$.
2. Сумма кубов чисел от 1 до $N$.
3. Сумма термов следующего вида: $\frac{1}{1 \cdot 3} + \frac{1}{5 \cdot 7} + \frac{1}{9 \cdot 11} + ... \to \frac{\pi}{8}$

Очевидно, что за этими задачами стоит одна общая абстракция - суммирование последовательностей. В математике мы знакомы с сигма нотацией, реализующей эту абстракцию: $\sum_{n=a}^b{f(n)} = f(a) + ... + f(b)$.

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

# Абстрагируем функцию возведения в квадрат.

def plus_one(x):
    return x + 1
def power2(function, x):
    return function(x) * function(x)

# Можем возводить в квадрату сумму    
power2(plus_one, 4) == (4+1)*(4+1) == 5*5 == 25
# lambda - это однострочная функция без имени
power2(lambda x: x*2, 4) == (4*2)*(4*2) == 8*8 == 64
# Длину строки!!
power2(lambda x: len(x), 'hello') == len('hello') * len('hello') == 5 * 5 == 25

Приступим к заданиям

Абстрактная сумма последовательности

$$ \sum_{n=a}^b{f(n)} = f(a) + ... + f(b) $$

Контракт функции, который необходимо реализовать:

def summa(f, start, stop, step):
    """
    :param f: функция из 1 аргумента, которую нужно применить над каждым элементом
    :param start: начинаем сумму с числа start
    :param step: ссылка на функцию которая возвращает следующее число
    :param stop: заканчиваем суммирование на числе stop
    """
    return 0

# Пример использования - сумма остатков от деления на три каждого второго числа от 1 до 100
summa(lambda x: x % 3, 1, 100, lambda x: x + 2)

# Сумма квадратов чисел от 1 до 5
summa(lambda x: x**2, 1, 5, lambda x: x + 1) == 1**1 + 2**2 + 3**2 + 4**2

Далее напишите вычисление числа $\pi$ используя формулу из начала практики и абстрактную сумму.

Абстракция накопления данных

Кроме суммы у нас существует еще и проивзедение элементов последовательностей. Абстракцией над этими частными случаями является общее понятие Накопление.

Тогда получаем следуюущую сигнатуру метода: