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

Учебниковая опора

• Кадиркулов Р. А., Нурмуханбетова Г. К. «Информатика. Учебник для 10 классов ЕМН», 10 класс, Алматыкітап баспасы, 2019, с. 61–104 (§§ 1–14)
• Кадыркулов Р., Нурмуханбетова Г. «Информатика. 9 класс», 9 класс, Алматыкітап, 2019, с. 96–100
• Кадиркулов Р. А., Рыскулбекова А. Д., Нурмуханбетова Г. К. «Информатика. 7 класс», 7 класс, Алматыкітап баспасы, 2023, с. 105–114

Главное

• Функция объявляется через def, результат возвращает return; без return функция возвращает None (процедура).
• Параметры — в заголовке функции, аргументы — значения при вызове. Локальные переменные живут внутри функции, глобальные — global.
• Рекурсия — функция вызывает саму себя; обязателен базовый случай, иначе RecursionError.
• Строки неизменяемы: s[0] = 'a' — ошибка. s[::-1] — разворот.
• Файл: открыть → читать/писать → закрыть. Режимы 'r', 'w' (перезапись), 'a' (дописывание).
• Сортировки $O(N^2)$: пузырёк, выбор, вставки; $O(N \log N)$: быстрая (Хоар, 1960), слиянием.
• Граф $G = (V, E)$; DFS — стек (LIFO) или рекурсия, BFS — очередь (FIFO), BFS находит кратчайший путь в невзвешенном графе.

Теория

Функции. Модульный принцип: программа разбивается на подпрограммы — меньше дублирования, проще отладка.

Строки — индексы и методы

Запись	Результат
len(s)	длина
s[1:4]	символы с индексами 1, 2, 3
s.find(x) / s.rfind(x)	индекс первого/последнего вхождения, −1 если нет
s.count(x)	число непересекающихся вхождений
s.replace(a, b)	замена всех вхождений
s.split(sep) / sep.join(lst)	строка → список / список → строка
s.strip()	убрать пробелы по краям
s.lower(), s.upper()	регистр
s.isdigit(), s.isalpha()	только цифры / только буквы

Файлы. Файл — именованная область диска для долгого хранения; бывают текстовые и двоичные. open(имя, режим):

Режим	Действие
'r'	чтение (по умолчанию); ошибка, если файла нет
'w'	запись; существующий файл очищается, нет — создаётся
'a'	добавление в конец
'r+'	чтение и запись
't' / 'b'	текстовый / двоичный

Методы: read() — весь файл, readline() — строка (readline(n) — n символов), readlines() — список строк, write(text) — запись строки (числа сначала через str), seek(n) — курсор в позицию n, close() — закрыть (без него данные могут не сохраниться). with open(...) as f: закрывает файл автоматически.

Сортировки

Алгоритм	Идея	Сложность
Пузырёк	соседи сравниваются и меняются; за проход наибольший «всплывает» в конец; $N-1$ проходов	$O(N^2)$
Выбор	ищется минимум неотсортированной части и ставится на её первое место	$O(N^2)$
Вставки	элементы по очереди вставляются в отсортированную левую часть; хороша для почти упорядоченных	$O(N^2)$
Быстрая (Хоар, 1960)	опорный элемент: меньшие слева, большие справа	$O(N \log N)$

При $N = 100$ простые сортировки делают около 10 000 операций, быстрая — около 700. В Python: sorted(A) — новый список, A.sort() — на месте, reverse=True — по убыванию. K-й максимум: отсортировать по убыванию и взять индекс $K-1$.

Графы. Ориентированный (рёбра-стрелки), неориентированный, взвешенный (у ребра вес). Представление: матрица смежности ($N \times N$, на пересечении 1 или вес) и список смежности ({'A': ['B', 'C']}). DFS идёт вглубь до тупика и возвращается (поиск циклов, проверка связности); BFS обходит вершины слоями.

Примеры

1. Рекурсивный факториал и НОД

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

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(factorial(5), gcd(48, 18))   # 120 6

2. Строки: палиндром и разбиение

text = "  Астана, Алматы, Шымкент  "
print(text.strip().split(", "))    # ['Астана', 'Алматы', 'Шымкент']
w = "Шалаш".lower()
print(w == w[::-1])                # True

3. Файлы: сумма чисел из файла

with open("numbers.txt", "w", encoding="utf-8") as f:
    for n in [12, 45, 78, 23, 56]:
        f.write(str(n) + "\n")
total = 0
with open("numbers.txt", "r", encoding="utf-8") as f:
    for line in f:
        total += int(line.strip())
print(total)                       # 214

4. 2-й максимум. [8, 14, 52, 14, 25, 35, 67, 41, 25, 30] по убыванию → [67, 52, 41, …]; ответ 52.

Типичные ошибки на ЕНТ

• Режим 'w' стирает содержимое файла — для дописывания нужен 'a'.
• Ждут, что функция без return вернёт значение — она вернёт None.
• Пишут рекурсию без базового случая.
• Путают sorted(A) (новый список, A не меняется) и A.sort() (меняет A, возвращает None).
• Путают структуры: DFS — стек, BFS — очередь; кратчайший путь (по числу рёбер) даёт BFS.
• s.find() при отсутствии подстроки возвращает −1, а не ошибку.

Самопроверка

1. Что вернёт "информатика".count("а")? — 2.
2. Какая сортировка самая быстрая по учебнику и кто её автор? — Быстрая (Quicksort), Ч. Хоар, 1960.
3. Что выведет "abc"[::-1]? — cba.
4. Чем режим 'a' отличается от 'w'? — 'a' дописывает в конец, 'w' перезаписывает файл.
5. Какая структура данных используется в BFS? — Очередь (FIFO).