Алгоритмы и программы (функция, рекурсия, работа со строками, работа с файлами, сортировка, граф)

Разбор темы

Функции: def, параметры, return 10 класс

Функция — это кусок программы, которому дали имя. Объявляем один раз, вызываем сколько угодно. Схема: def имя(параметры):, затем тело с отступом 4 пробела. Слово return завершает функцию и возвращает результат туда, откуда её вызвали.

def area(a, b=2):
    return a * b

print(area(3))        # b взят по умолчанию: 6
print(area(3, 5))     # 15
print(area(b=4, a=10))  # именованные аргументы: 40

Параметр со значением по умолчанию (b=2) можно не передавать. Параметры по умолчанию пишутся после обычных: def f(a, b=2) — правильно, def f(a=1, b) — ошибка. При вызове можно указывать аргументы по имени, тогда порядок не важен.

Функция может вернуть сразу несколько значений: return a + b, a * b — получится кортеж, его удобно «распаковать»: s, p = f(2, 3). После return код в функции уже не выполняется.

Если return нет (или он пустой), функция возвращает None. Это и есть процедура: она что-то делает (например, печатает), но значения не отдаёт. Классическая ловушка ЕНТ: r = show(7) напечатает 14, а print(r) напечатает None.

Встроенные функции, которые полезно знать: len, abs, max, min, sum, sorted, int, str, round, ord (код символа), chr (символ по коду), range.

Область видимости: локальные и глобальные переменные 10 класс

Переменная, созданная внутри функции, — локальная: она живёт только во время вызова и снаружи не видна. Переменная основной программы — глобальная: функция может её читать, но присваивание внутри функции создаёт новую локальную переменную с тем же именем.

x = 10

def f():
    x = 5          # локальная x, глобальную не трогает
    print(x)

def g():
    global x       # теперь работаем с глобальной x
    x = x + 1

f()        # 5
print(x)   # 10
g()
print(x)   # 11

Правило для задач: если в функции есть присваивание x = ... без global x — это другая, локальная x. Если есть global x — функция меняет «общую» переменную.

Параметры функции — тоже локальные переменные. Числа и строки внутрь функции «копируются по смыслу»: изменить их снаружи через параметр нельзя. А вот список, переданный в функцию, можно изменить методами (a.append(...), a[0] = ...) — изменения видны снаружи, поэтому в сортировках часто делают копию a = a[:].

Рекурсия: базовый случай и стек вызовов 10–11 класс

Рекурсивная функция вызывает саму себя для задачи поменьше. Обязательно два элемента: базовый случай (когда отвечаем сразу) и рекурсивный шаг (сводим задачу к меньшей). Без базового случая будет бесконечная рекурсия и ошибка RecursionError (в Python по умолчанию предел глубины около 1000).

def fact(n):            # n! = 1·2·…·n
    if n <= 1:          # базовый случай
        return 1
    return n * fact(n - 1)

def power(a, n):        # a в степени n
    if n == 0:
        return 1
    return a * power(a, n - 1)

def digsum(n):          # сумма цифр
    if n < 10:
        return n
    return n % 10 + digsum(n // 10)

def fib(n):             # 1, 1, 2, 3, 5, 8, 13, ...
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)

Как это работает: каждый вызов кладётся в стек вызовов (как тарелки в стопку) и ждёт, пока вернётся вызов поменьше. fact(4) ждёт fact(3), тот ждёт fact(2), тот — fact(1). fact(1) сразу возвращает 1, и стек «разматывается» обратно: $2\cdot1=2$, $3\cdot2=6$, $4\cdot6=24$.

Если внутри функции два рекурсивных вызова (как в fib), вызовы ветвятся деревом и их число растёт очень быстро: fib(6) вызывает функцию 15 раз, fib(7) — 25 раз. Счёт вызовов удобно вести по формуле $C(n)=C(n-1)+C(n-2)+1$ с $C(1)=C(2)=1$.

Порядок вывода. Если print стоит ДО рекурсивного вызова, числа печатаются «на спуске» (в прямом порядке); если ПОСЛЕ — «на подъёме» (в обратном). Пример: def g(n): print(n); if n > 1: g(n // 2); print(n) при g(10) выведет 10 5 2 1 1 2 5 10.

Любую рекурсию можно заменить циклом (итерацией) и наоборот. Цикл обычно быстрее и не тратит стек; рекурсия короче записывается для «самоподобных» задач — обхода деревьев и графов (DFS), быстрой сортировки, вычисления по рекуррентной формуле.

Строки: индексы, срезы, перебор 10 класс

Строка — последовательность символов. Нумерация с 0 слева и с −1 справа. Для s = "informatika" (11 символов): s[0] = i, s[4] = r, s[-1] = a, len(s) = 11. Индекс за пределами строки (например s[11]) даёт ошибку IndexError.

Срез s[start:stop:step] берёт символы с номера start до stop, НЕ включая stop, с шагом step. Пропущенный start — с начала, пропущенный stop — до конца. s[2:5] = for, s[:4] = info, s[7:] = tika, s[-3:] = ika, s[::2] = ifraia, s[1::3] = nrta, s[::-1] = akitamrofni (строка задом наперёд). Срез за пределами строки ошибки не даёт — просто вернёт то, что есть.

Строки неизменяемы: s[0] = "I" — ошибка. Чтобы «изменить» строку, строят новую: s = "I" + s[1:]. Операции: + склеивает, * повторяет ("ab" * 3 = ababab), in проверяет вхождение ("for" in s → True), строки сравниваются посимвольно по кодам ("apple" < "banana", но "Z" < "a", потому что заглавные буквы имеют меньшие коды).

Перебор строки: for ch in s: — по символам; for i in range(len(s)): — по индексам (нужно, когда важна позиция, например сравнить s[i] и s[i+1]). Коды символов: ord("A") = 65, ord("a") = 97, chr(66) = B.

Методы строк, палиндромы, подсчёт символов, словари и множества 10 класс

Методы не меняют строку, а возвращают новую: s.upper() / s.lower() — регистр; s.strip() — убрать пробелы по краям; s.replace(a, b) — заменить все вхождения a на b (s.replace(a, b, 1) — только первое); s.find(x) — индекс первого вхождения или −1, если нет; s.count(x) — число непересекающихся вхождений; s.split(sep) — разрезать в список; sep.join(список) — склеить список строк; s.isdigit() / s.isalpha() — состоит ли строка только из цифр / букв.

t = "Astana, Almaty, Shymkent"
parts = t.split(", ")     # ['Astana', 'Almaty', 'Shymkent']
print("-".join(parts))     # Astana-Almaty-Shymkent
print(t.find("Almaty"))    # 8
print(t.lower().count("a")) # 5
print("aaaa".count("aa"))  # 2 (не 3!)

Палиндром — строка, которая читается одинаково слева направо и справа налево: level, kazak, 12321. Проверка в одну строку: s == s[::-1]. Если регистр не важен, сначала s = s.lower(); если надо игнорировать пробелы — s.replace(" ", "").

Подсчёт символов. Цифры: if ch.isdigit(): total += int(ch). Частоты букв удобно хранить в словаре: freq[ch] = freq.get(ch, 0) + 1; для "banana" получится {'b': 1, 'a': 3, 'n': 2}. Словарь (dict) хранит пары «ключ: значение», доступ по ключу d["a"], len(d) — число ключей.

Множество (set) хранит только уникальные элементы без порядка: set("banana") = {'a', 'b', 'n'}, len(set(s)) — число различных символов. Операции: | объединение, & пересечение, - разность.

Работа с файлами 7, 10 класс

Файл открывают функцией open(имя, режим). Режимы: "r" — чтение (по умолчанию; файла нет — ошибка), "w" — запись (файл создаётся, а если был — полностью ОЧИЩАЕТСЯ), "a" — дозапись в конец (старое содержимое сохраняется). Конструкция with open(...) as f: сама закроет файл после блока — так писать правильнее, чем вручную вызывать f.close().

Чтение: f.read() — весь файл одной строкой; f.readline() — одна следующая строка вместе с символом \n в конце; f.readlines() — список всех (оставшихся) строк; for line in f: — перебор строк по одной. Запись: f.write(текст) пишет только строку и сам перенос НЕ добавляет — \n нужно писать явно; числа перед записью переводят в строку: f.write(str(x) + "\n").

with open("data.txt", "w") as f:
    f.write("5\n12\n7\n20\n3\n")

with open("data.txt") as f:
    nums = [int(line) for line in f]   # int сам отбросит \n

print(sum(nums), max(nums))   # 47 20

Типичная задача: «в файле записаны числа по одному в строке, найдите сумму / количество чётных / максимум». Шаблон: прочитать строки, превратить каждую в число (int(line) или int(line.strip())), дальше обычный цикл со счётчиком. Если числа записаны в одной строке через пробел: nums = list(map(int, f.read().split())).

Файл читается последовательно, как магнитофон: после readline() «указатель» стоит на следующей строке, и readlines() вернёт уже только оставшиеся строки. Повторное чтение с начала — заново открыть файл.

Сортировка и поиск 9–10 класс

Пузырьковая сортировка: проходим по массиву, сравниваем соседей и меняем местами, если левый больше правого. После первого прохода самый большой элемент «всплывает» в конец; после $k$-го прохода на местах стоят $k$ последних. Для $n$ элементов: $n-1$ проход, сравнений $(n-1)+(n-2)+\dots+1=\frac{n(n-1)}{2}$. Число обменов равно числу «инверсий» — пар, стоящих в неправильном порядке.

Сортировка выбором: на шаге $i$ ищем минимум среди элементов с $i$-го до конца и меняем его с $i$-м. Сравнений тоже $\frac{n(n-1)}{2}$, но обменов не больше $n-1$. Сортировка вставками: берём очередной элемент и сдвигаем его влево, пока слева стоит больший, — как сортируют карты в руке; на почти отсортированных данных работает очень быстро.

for i in range(n - 1):              # пузырёк
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]

Встроенные средства: sorted(a) возвращает НОВЫЙ отсортированный список, a.sort() сортирует сам список и возвращает None. Параметры: reverse=True — по убыванию; key=функция — сортировать по признаку: sorted(words, key=len) — по длине, a.sort(key=abs) — по модулю. Сортировка в Python устойчивая: равные по ключу элементы сохраняют исходный порядок.

Линейный поиск — просматриваем элементы по порядку; в худшем случае $n$ сравнений, работает для любого массива. Двоичный (бинарный) поиск — только для ОТСОРТИРОВАННОГО массива: сравниваем с серединой mid = (lo + hi) // 2, отбрасываем половину, где искомого быть не может; шагов не больше $\lceil\log_2(n+1)\rceil$ (для 1000 элементов — 10, для миллиона — 20).

Графы: представление, обходы, кратчайший путь, деревья 10 класс

Граф — вершины и рёбра. Неориентированный граф: ребро A–B можно пройти в обе стороны (дороги). Ориентированный: дуга A→B ведёт только в одну сторону (улицы с односторонним движением, подписки). Взвешенный граф: у каждого ребра есть число — вес (расстояние, время, стоимость). Путь — последовательность вершин, соединённых рёбрами; длина пути — число рёбер или сумма весов; цикл — путь, который возвращается в начальную вершину.

Степень вершины — число рёбер, выходящих из неё (петля даёт 2). Сумма степеней всех вершин равна $2|E|$, поэтому число вершин нечётной степени всегда чётно. В ориентированном графе различают полустепени входа и выхода.

Матрица смежности — таблица $n\times n$: в клетке [A][B] стоит 1 (или вес), если есть ребро A–B, иначе 0 или прочерк. У неориентированного графа матрица симметрична относительно главной диагонали; степень вершины = сумма её строки. Список смежности — для каждой вершины перечисляем соседей; в Python удобно словарём: g = {"A": ["B", "C"], "B": ["A", "D"], ...}.

Обход в ширину (BFS) — «волной»: сначала все соседи стартовой вершины, потом их соседи и т.д. Использует очередь; находит путь с наименьшим числом рёбер. Обход в глубину (DFS) — идём как можно дальше по одной ветке, упираемся — возвращаемся назад; удобно писать рекурсией.

Кратчайший путь во взвешенном графе (алгоритм Дейкстры, решается по таблице вручную): 1) стартовой вершине ставим 0, остальным ∞; 2) выбираем непосещённую вершину с наименьшей меткой и «фиксируем» её; 3) для каждого её соседа пробуем улучшить метку: новая = метка текущей + вес ребра, если меньше старой — заменяем; 4) повторяем до финиша. Главное правило: прямое ребро не обязательно самое короткое — путь в обход через другие вершины может быть дешевле.

Дерево — связный граф без циклов; в дереве на $n$ вершинах ровно $n-1$ ребро и между любыми двумя вершинами ровно один путь. Корневое дерево: корень, родители, потомки, листья (вершины без потомков). Деревом изображают структуру папок, родословную, дерево рекурсивных вызовов. Число путей в ориентированном графе без циклов считают так: количество путей в вершину = сумма количеств путей во все вершины, из которых в неё ведут дуги.