Постановка задачи: вход, выход и шаги
Прежде чем писать код, точно опишите задачу. Это называется спецификация.
- Вход: какие данные мы получаем, их тип и ограничения (например, «n целых чисел, 1 ≤ n ≤ 1000»).
- Выход: что нужно вернуть (например, «самое большое из них»).
- Условия: что верно до работы (предусловие) и после неё (постусловие).
Запись шагов
Алгоритм — это конечный список чётких шагов, который превращает любые допустимые входные данные в правильный результат. Его можно записать так:
- словами: «Смотри на каждое число; если оно больше лучшего на данный момент, запомни его».
- нумерованным списком: 1. best ← первое число. 2. Для каждого следующего числа x: если x > best, то best ← x. 3. Вывести best.
- псевдокодом или блок-схемой — когда нужна точность.
Проверьте алгоритм вручную на маленьких данных, в том числе на подвохах (все числа равны, отрицательные числа, всего одно число).
Проектирование сверху вниз и снизу вверх
Сверху вниз (пошаговая детализация): берём всю задачу, делим на несколько крупных шагов, потом каждый шаг делим снова, пока каждую часть не станет легко запрограммировать. Пример: «Сделать табель» → прочитать оценки → посчитать средние → поставить итоговые оценки → напечатать.
Снизу вверх: сначала пишем и проверяем маленькие повторно используемые кусочки (функцию поиска максимума, функцию сортировки), затем соединяем их в целую программу.
В реальных проектах используют оба способа: планируют сверху вниз, а пишут и проверяют снизу вверх.
Разделяй и властвуй и метод деления пополам
У метода разделяй и властвуй три хода: разделить задачу на меньшие части того же вида, решить каждую часть (часто рекурсией), объединить ответы.
- Бинарный поиск (деление пополам): в отсортированном списке сравниваем со средним элементом и отбрасываем половину. Для n элементов нужно примерно log₂ n проверок: 16 → 4, 1 000 000 → 20.
- Сортировка слиянием: делим список на две части, сортируем каждую, сливаем их: O(n log n).
- Быстрое возведение в степень: a⁸ = ((a²)²)²: 3 умножения вместо 7.
- Поиск корня методом бисекции: делим пополам отрезок, на котором функция меняет знак.
Жадные алгоритмы
Жадный алгоритм делает выбор, который сейчас выглядит лучшим, и никогда его не меняет.
- Сдача монетами 50, 20, 10, 5, 2, 1: сначала самая крупная монета. Для такой системы монет это оптимально.
- Чтобы успеть больше дел за день, всегда выбираем то, что заканчивается раньше всех. Это оптимально.
- Дробный рюкзак: сначала берём предметы с наибольшей ценой за килограмм. Это оптимально.
Но жадный метод не всегда верен: с монетами 1, 3, 4 сумма 6 жадно выдаётся как 4 + 1 + 1 (3 монеты), а 3 + 3 — всего 2. Чтобы доверять жадному методу, его нужно доказать или сравнить с надёжным методом.
Динамическое программирование и поиск с возвратом
Динамическое программирование (DP)
Если одни и те же маленькие задачи повторяются, решаем каждую один раз и храним ответ в таблице. Наименьшее число монет для суммы a: best[a] = 1 + min(best[a - c]) по всем монетам c ≤ a, начиная с best[0] = 0. Для монет 1, 3, 4: best = 0, 1, 2, 1, 1, 2, 2. Заполнять таблицу от малого к большому — это снизу вверх; рекурсия с памятью — это сверху вниз (мемоизация). Подробнее смотрите в отдельном уроке о динамическом программировании.
Поиск с возвратом
Строим решение по одному выбору. Если выбор нарушает правило или ведёт в тупик, отменяем его и пробуем следующий вариант. Так решают лабиринты, судоку, задачу о N ферзях и перечисляют все подмножества. Это аккуратный перебор: он пропускает целые ветви, которые не могут подойти.
Перебор
Пробуем все возможные ответы. Всегда правильно, но часто слишком медленно (2ⁿ подмножеств, n! порядков).
Выбор приёма: правильность, эффективность и структуры данных
| Приём | Когда применять | Пример | Обычное время |
|---|---|---|---|
| Перебор | данных совсем мало | перебрать все пароли из 3 цифр | часто 2ⁿ или n! |
| Разделяй и властвуй | части независимы | бинарный поиск, сортировка слиянием | O(log n), O(n log n) |
| Жадный метод | лучший локальный выбор доказанно безопасен | выбор занятий, сдача | O(n log n) |
| Динамическое программирование | подзадачи повторяются | размен монет, кратчайшие пути | размер таблицы |
| Поиск с возвратом | поиск по правилам | лабиринт, судоку | экспоненциальное, но с отсечением |
Обоснуйте выбор
Правильность: покажите, что алгоритм всегда завершается и даёт верный результат (инвариант цикла, доказательство или тесты на крайних случаях). Эффективность: посчитайте число шагов при росте n (O-большое) и сравните с другими методами.
Помогают структуры данных
Массивы для таблиц (DP), стеки для поиска с возвратом (помнить, куда вернуться), очереди для поиска по уровням. Двоичное дерево хранит элементы так, что у каждого узла не больше двух потомков; в двоичном дереве поиска меньшие ключи идут влево, а большие вправо, поэтому поиск на каждом уровне сокращает работу вдвое, как и бинарный поиск.
Попробуйте сами: монеты и игра в угадайку
- Сыграйте с другом в игру «угадай число от 1 до 100». Всегда спрашивайте про середину. Всегда ли можно выиграть за 7 вопросов? (2⁷ = 128.)
- Для монет 1, 3, 4 запишите на бумаге таблицу DP для сумм от 0 до 10. Где жадный метод ошибается?
- Откройте последний шаг 3D. Попробуйте монеты 1, 7, 10 и сумму 14. Жадный метод даёт 10 + 1 + 1 + 1 + 1; DP даёт 7 + 7.
- Запишите список шагов для задачи «найти наименьшее число в списке» и проверьте его на 5, 5, 5 и на одном числе.
Главные формулы и определения
- Спецификация = вход + выход + условия
- Деление пополам: примерно log₂ n шагов (16 → 4, 1024 → 10)
- DP для монет: best[0] = 0; best[a] = 1 + min best[a - c]
- Разделяй и властвуй = разделить + решить + объединить
- Жадный метод быстр, но его оптимальность нужно доказать
Разобранные примеры
1. Напишите спецификацию и список шагов для поиска наибольшего из n чисел.
Вход: n ≥ 1 чисел. Выход: наибольшее. Шаги: 1. best ← первое число. 2. Для каждого другого числа x: если x > best, то best ← x. 3. Вывести best. Для 4, 9, 2, 7, 12, 5, 10, 3 результат равен 12 после 7 сравнений.
2. Сколько вопросов нужно при делении пополам, чтобы найти число от 1 до 1000?
Каждый вопрос сокращает диапазон вдвое: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Это 10 вопросов (2¹⁰ = 1024 ≥ 1000).
3. Выдайте 87 жадным способом монетами 50, 20, 10, 5, 2, 1.
50 (осталось 37), 20 (17), 10 (7), 5 (2), 2 (0): 50 + 20 + 10 + 5 + 2 = 5 монет.
4. Заполните таблицу DP для монет 1, 3, 4 до суммы 7.
best[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(best4, best2, best1)+1=2, [6]=min(best5, best3, best2)+1=2, [7]=min(best6, best4, best3)+1=2 (3 + 4).
5. Занятия (начало-конец): A 9-11, B 10-12, C 11-13, D 12-14, E 13-15. Выберите наибольшее число занятий, которые не пересекаются.
Жадно по самому раннему окончанию: A (кончается в 11), затем C (начало 11, конец 13), затем E (начало 13). Всего 3 занятия: A, C, E.
6. Спланируйте сверху вниз программу, которая сообщает классу средний балл и лучшего ученика.
Уровень 1: прочитать данные → вычислить → напечатать. Уровень 2: прочитать имена и оценки в списки; найти сумму и среднее; найти максимальную оценку и имя; напечатать оба результата. Затем каждую часть программируют и проверяют снизу вверх.
Частые ошибки
- Начинать писать код, не определив вход и выход. Многие «ошибки» на деле — нечёткая спецификация.
- Считать, что жадный метод всегда оптимален. Он работает, только если это можно доказать (монеты 1, 3, 4 это ломают).
- Применять бинарный поиск к неотсортированному списку. Деление пополам требует отсортированных данных.
- Путать DP с методом разделяй и властвуй. DP нужен для перекрывающихся подзадач, которые мы храним; разделяй и властвуй делит задачу на независимые части.