13 мин чтенияалгоритмырекурсияигрыдинамикасложностьКЕГЭ

Алгоритмы, исполнители и сложность

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

Открываем тему…

Анализ алгоритмов

Чтобы понять алгоритм, выполните его «вручную» на небольшом примере, записывая значения переменных в таблицу. Ищите инварианты: что не меняется на каждой итерации цикла. Для циклов со счётчиком полезно записать, как меняется переменная — арифметическая или геометрическая прогрессия.

Рекурсия

Рекурсивная функция должна иметь базу (условие остановки) и шаг, приближающий к базе.
Для быстрых вычислений используйте кэш: from functools import lru_cache.
Глубина рекурсии по умолчанию ограничена: перед глубокой рекурсией вызывайте sys.setrecursionlimit(…).

ПримерРекурсивная функция

F(1) = 1; F(n) = F(n − 1) + 2·n при n > 1. Найдите F(10).

Решение

Выпишем: F(1)=1, F(2)=5, F(3)=11, F(4)=19, … Явная формула F(n) = n² + n − 1; F(10) = 109. Код: from functools import lru_cache @lru_cache(None) def F(n): return 1 if n == 1 else F(n - 1) + 2 * n print(F(10))

Динамическое программирование

Если число способов получить результат выражается через число способов получить меньшие значения, постройте массив d, где d[i] — ответ для i. Для задач на «количество программ» из исполнителя с командами +1, +2, ×2 стоит идти от меньшего числа к большему и проверять обязательные промежуточные точки умножением результатов: путь от A до B через C = (A→C)·(C→B).

ПримерКоличество программ

Исполнитель умеет прибавлять 1 или 2. Сколько существует программ, переводящих 1 в 10 и проходящих через 5?

Решение

Количество способов дойти до n прибавлением 1 или 2 — числа Фибоначчи: ways(a→b) = Fib(b − a + 1). Из 1 в 5 расстояние 4 — это 5 способов; из 5 в 10 расстояние 5 — 8 способов. Всего 5·8 = 40.

Теория игр

Позиция выигрышная, если из неё есть ход в проигрышную; позиция проигрышная, если все ходы ведут в выигрышные. Анализируйте позиции с конца: терминальные позиции (достигнута цель) — проигрышные для того, чей ход. «Выиграть за Х ходов» формализуется введением уровня позиции: Петя выигрывает первым ходом, Ваня — вторым и т. д.

ПримерИгра с прибавлением камней

Двое игроков по очереди добавляют в кучу 1 или 2 камня. Побеждает тот, после чьего хода в куче станет не менее 12 камней. При каких начальных значениях S (1 ≤ S ≤ 11) выигрывает второй игрок?

Решение

Разбираем позиции с конца. Из S = 10 и S = 11 ходящий выигрывает немедленно (10 + 2, 11 + 1). Из S = 9 любой ход ведёт в 10 или 11 — выигрышные позиции соперника, поэтому S = 9 проигрышная. Из S = 7 и S = 8 можно сходить в 9 — выигрыш. Из S = 6 ходы ведут в 7 или 8 — оба выигрышные для соперника, значит 6 проигрышная. Аналогично проигрышна S = 3. Второй игрок выигрывает при S = 3, 6, 9 (кратных 3). Проверка кодом: from functools import lru_cache @lru_cache(None) def win(s): return any(s + d >= 12 or not win(s + d) for d in (1, 2)) print([s for s in range(1, 12) if not win(s)])

Сложность

O(n) — один проход, O(n log n) — сортировка, O(n²) — два вложенных цикла.
Для n ≈ 10⁶ допустимо O(n) и O(n log n); O(n²) уже не успеет.
Для простых чисел используйте решето Эратосфена вместо перебора делителей до n.

ПримерЧисло итераций вложенного цикла

Сколько раз выполнится оператор cnt += 1? for i in range(1, 101): for j in range(i, 101): cnt += 1

Решение

При i = 1 внутренний цикл выполняется 100 раз, при i = 2 — 99 раз, …, при i = 100 — 1 раз. Сумма арифметической прогрессии 100 + 99 + … + 1 = 100·101 / 2 = 5050. Для n повторов такая конструкция даёт n(n + 1)/2 операций, то есть порядка n².

ПримерЦикл с делением пополам

Чему равно k после выполнения? n = 10**6 k = 0 while n > 1: n //= 2 k += 1

Решение

На каждом шаге n уменьшается примерно вдвое, и цикл завершается, когда n станет равно 1. Число шагов равно ⌊log₂ n⌋. Так как 2¹⁹ = 524 288 ≤ 10⁶ < 1 048 576 = 2²⁰, получаем k = 19. Такие циклы имеют сложность O(log n).

ПримерЛестница: динамика с тремя шагами

За один шаг можно подняться на 1, 2 или 3 ступеньки. Сколькими способами можно подняться на 10-ю ступеньку, начиная с земли (ступенька 0)?

Решение

d[n] = d[n − 1] + d[n − 2] + d[n − 3], d[0] = 1 (одно «пустое» решение), d[1] = 1, d[2] = 2. Далее: d[3] = 4, d[4] = 7, d[5] = 13, d[6] = 24, d[7] = 44, d[8] = 81, d[9] = 149, d[10] = 274. Код: d = [1, 1, 2] for n in range(3, 11): d.append(d[-1] + d[-2] + d[-3]) print(d[10]) # 274

← Логика и алгебра высказываний Программирование: Python-шаблоны для КЕГЭ →