Семинар 2: функции

Проверяем знания с лекции

https://docs.google.com/forms/d/e/1FAIpQLSekcCnsKxhM23-CAwrypOiLvQtiNrzXpdkVfVPs0VTl9cz46g/viewform

Power

Давайте попробуем решить следующую задачу: Напишите функцию power(a, n), которая вычисляет $a$ в степени $n$. Встроенной в питон функцией при этом пользоваться нельзя. Учтите, что степень может быть отрицательной.

def power(a, n):
    # YOUR CODE HERE

Стремная строка

Пусть есть файл strings.txt, в котором на каждой новой строке находится слово.

Стремной строкой будем называть слово из 4 букв, которое начинается на “f”, а заканчивается на “k”.

Найдите среди файла самое маленькое лексикографически “стремное” слово и его индекс. Если таких слов несколько, то выведите самое раннее.

Проверку “стремности” оформите в виде функции is_weird.

Has negative

Напишите функцию has_negative_number, которая принимает на себя произвольное количество чисел, а возвращает True, если среди них есть отрицательное число и False иначе.

Примеры вызова: has_negative_number(1, 2, -1, -2, 3), has_negative_number(1, 2, 2) и так далее.

Лямбды

В питоне есть достаточно интересный инструмент для работы с так называемыми “анонимными” функциями. Они могут присваиваться в переменную (хотя это плохой тон), но чаще всего используются просто как аргументы для других функций.

Например, в методе .sort() (или функции sorted) у списка есть аргумент key, который позволяет отсортировать как-то особенно, допустим:

values = ["abcd", "aab", "bda", "0xabadbabe", "0xdeadbeef"]

print(sorted(values, key=lambda s: len(s)))

Такой код отсортирует строки по длине, а при равенстве, уже лексикографически.

Здесь лямбда имеет следующий синтаксис: после слова lambda идут через запятую (если их несколько) аргументы функции (поддерживаются также *args и **kwargs), а после двоеточие – что возвращает функция.

Все то же самое можно написать чуть проще:

values = ["abcd", "aab", "bda", "0xabadbabe", "0xdeadbeef"]

print(sorted(values, key=len)

Потому что len – это тоже функция и она тоже возвращает то, что можно скормить сортировке (то есть число, а числа можно сравнивать).

Задача

А пусть теперь у нас есть числа, и мы хотим отсортировать их по возрастанию длины, а при равенстве длин – по убыванию самих этих чисел.

Рекурсия

Функция может вызывать саму себя, и это абсолютно часто ожидаемое поведение. Например,

def dummy_sum(n):
    if n == 0:
        return 0
    return n + dummy_sum(n - 1)

Такая функция просуммирует все числа от одного до n рекурсивно, то есть вызывая каждый раз саму себя от n - 1.

Понятно, что для такой суммы есть и формула, и другие способы подсчета (например, цикл), но тут это скорее просто тривиальный пример, на котором достаточно просто рассматривать данное явление.

По сути у нас получается некоторая цепочка вызовов:

dummy_sum(4) -> 4 + dummy_sum(3)
dummy_sum(3) -> 3 + dummy_sum(2)
dummy_sum(2) -> 2 + dummy_sum(1)
dummy_sum(1) -> 1 + dummy_sum(0)
dummy_sum(0) -> 0

Получается, что раньше всего мы посчитаем dummy_sum(0), а дальше уже снизу вверх будем “раскручивать” эту цепочку обратно.

Заметьте, что условие

if n == 0:
    return 0

очень критично, поскольку если его не написать, что рекурсия будет выполняться бесконечно, что скорее всего сожрет всю память либо отведенную питону на глубину рекурсии, либо компьютера.

Из факультативного: максимальную глубину рекурсии можно получить так:

import sys

print(sys.getrecursionlimit())

А поменять – вот так, к примеру:

import sys

sys.setrecursionlimit(10 ** 5)

Рассмотрим другой пример, числа Фибоначчи – одна и самых стандартных задач на рекурсию.

Пусть есть последовательность $f_n$ вида \(f_0 = f_1 = 1 \\ f_n = f_{n - 1} + f_{n - 2},\; n > 1\)

Вычислим ее с помощью рекурсии:

def fib(n):
    if n <= 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Получилось очень элегантно и просто.

Для любознательных, тут есть нюанс. Попробуйте нарисовать себе дерево вызовов, что получится, когда мы вызовем f(10), например. Вы увидите, что чтобы посчитать f(5), f(6), f(7) (и так далее), вам придется очень много раз вызывать, к примеру f(4), что плохо и влечет за собой лишние вычисления.

И правда, такая функция для сравнительно небольших $n$ работает крайне медленно и плохо, но благо, это исправляется всего двумя строками:

from functools import lru_cache  # еще также можно использоваться просто cache, без lru

@lru_cache
def fib(n):
    if n <= 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Эта “собачка” над функцией – декоратор. Если коротко, то она позволяет “обернуть” функцию, слегка поменяв ее поведение. Конкретно сейчас, мы сказали питону запоминать все возможные результаты работы нашей функции fib от разных $n$. Таким образом, не придется много раз пересчитывать одно и то же.

Задача на рекурсию

Пусть есть какой-то словарь вида

d = {
    "key1": "value1",
    "key2": {
        "key3": "value3",
        "key4": {
            "key5": "value5",
        }
    }
}

В общем, какой-то словарь любой вложенности, где на самом нижнем уровне – строки. Требуется написать функцию

def find_largest(d):
    ...

которая принимает на себя такой словарь и находит в нем самую большую лексикографически такую строчку.