12 мин чтениядинамикажадные алгоритмысортировкапрефиксные суммызадание 26задание 27КЕГЭ

Динамика, жадные алгоритмы и сортировка (задания 23, 26, 27)

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

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

Динамическое программирование (задание 23)

В задании 23 исполнитель имеет несколько команд (+1, +2, ×2 …); нужно найти число программ, переводящих a в b, часто с обязательной точкой и запрещённой точкой. Если d[n] — количество программ, приводящих к числу n, то d[n] равно сумме d[m] по всем числам m, из которых за одну команду можно получить n. Путь через обязательную точку c — это произведение d(a→c)·d(c→b); запрещённая точка просто обнуляется (d[x] = 0).

ПримерПрограммы с командами +1 и ×2

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

Решение

d[1] = 1. Для n > 1: d[n] = d[n − 1] + (d[n / 2], если n чётно). d[2] = 1 + 1 = 2; d[3] = 2; d[4] = d[3] + d[2] = 4; d[5] = 4; d[6] = d[5] + d[3] = 6; d[7] = 6; d[8] = d[7] + d[4] = 10; d[9] = 10; d[10] = d[9] + d[5] = 14. Код: d = {1: 1} for n in range(2, 11): d[n] = d[n - 1] + (d[n // 2] if n % 2 == 0 else 0) print(d[10]) # 14

ПримерЛестница с шагами 1, 2 и 3

Сколькими способами можно подняться на 7-ю ступеньку, если за шаг можно подняться на 1, 2 или 3 ступени?

Решение

d[0] = 1, d[1] = 1, d[2] = 2, d[n] = d[n − 1] + d[n − 2] + d[n − 3]: d[3] = 4, d[4] = 7, d[5] = 13, d[6] = 24, d[7] = 44. Ответ — 44.

Жадные алгоритмы и сортировка (задание 26)

Жадный алгоритм на каждом шаге выбирает локально лучший вариант. В задании 26 это почти всегда «отсортировать данные по подходящему ключу и пройти один раз». Ключ сортировки определяет правильность: для набора максимального числа непересекающихся интервалов нужно сортировать по времени окончания, для максимального числа файлов на диске — по размеру по возрастанию.

ПримерМаксимум непересекающихся интервалов

Заявки (начало; конец): [1; 3], [2; 5], [4; 6], [5; 7], [6; 8]. Концы и начала могут совпадать. Какое наибольшее число заявок можно выполнить?

Решение

Сортируем по концу: [1; 3], [2; 5], [4; 6], [5; 7], [6; 8]. Берём [1; 3]. Следующая заявка должна начинаться не раньше 3: [2; 5] — нет, [4; 6] — берём (последний конец 6). Далее [5; 7] — нет, [6; 8] — берём. Итого 3 заявки. Код: iv = sorted([(1, 3), (2, 5), (4, 6), (5, 7), (6, 8)], key=lambda x: x[1]) last = -1 cnt = 0 for s, e in iv: if s >= last: cnt += 1 last = e print(cnt) # 3

ПримерФайлы на диске

На диск объёмом 20 Мбайт нужно записать как можно больше файлов размерами 4, 9, 2, 7 и 5 Мбайт. Сколько файлов поместится и какой объём они займут?

Решение

Сортируем: 2, 4, 5, 7, 9. Накопленные суммы: 2, 6, 11, 18, 27. Сумма 18 ≤ 20, а 27 > 20, поэтому помещается 4 файла общим объёмом 18 Мбайт.

Префиксные суммы и остатки (задание 27)

Для файлов до 10⁷ чисел нужен один проход. Если pref[k] — сумма первых k элементов, то сумма фрагмента (i, j] равна pref[j] − pref[i]. Условие «сумма делится на m» означает pref[i] ≡ pref[j] (mod m): достаточно хранить, сколько раз встретился каждый остаток (для подсчёта числа фрагментов) или где он встретился впервые (для самого длинного фрагмента). Для пар элементов с условием на сумму или разность хранят минимумы и максимумы по остаткам.

ПримерЧисло фрагментов с суммой, кратной 3

Дана последовательность 2, 1, 3, 4, 2. Сколько существует непрерывных фрагментов, сумма элементов которых делится на 3?

Решение

Префиксные суммы по модулю 3 (с нулевой в начале): 0, 2, 0, 0, 1, 0. Остаток 0 встречается 4 раза, 1 — один раз, 2 — один раз. Число пар равных остатков: C(4, 2) + 0 + 0 = 6. Код: from collections import Counter c = Counter([0]) s = 0 for x in [2, 1, 3, 4, 2]: s = (s + x) % 3 c[s] += 1 print(sum(v * (v - 1) // 2 for v in c.values())) # 6 Фрагменты: [2, 1], [3], [4, 2], [2, 1, 3], [3, 4, 2], [2, 1, 3, 4, 2].

ПримерКогда жадный алгоритм не работает: размен монет

Монеты номиналов 1, 3 и 4. Каково наименьшее количество монет, которыми можно набрать сумму 6? Что даст жадный выбор «самая крупная монета, пока можно»?

Решение

Жадный алгоритм берёт 4, затем 1 и 1: 3 монеты. Но 3 + 3 — всего 2 монеты, поэтому для произвольных номиналов нужна динамика: dp[s] — минимальное число монет для суммы s, dp[s] = 1 + min(dp[s − c]) по монетам c ≤ s. dp = [0] + [10**9] * 6 for s in range(1, 7): for c in (1, 3, 4): if c <= s: dp[s] = min(dp[s], dp[s - c] + 1) Таблица dp[0..6] = 0, 1, 2, 1, 1, 2, 2. Ответ: 2. Для набора номиналов 1, 5, 10, 50 жадный метод верен, для произвольного набора — нет. Доказывайте жадность или используйте динамику.

← Строки и анализ файлов: шаблоны для задания 24 Исполнители: Чертёжник, Робот, Черепаха и Редактор →