|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Занятие 14. Рекурсия - 2. Перебор.
Существует класс задач, в которых необходимо выбрать по какому-то критерию один из конечного числа вариантов. Для их решения можно перебрать все варианты и выбрать из них тот, который отвечает заданному критерию. Зачастую это удобно делать с помощью рекурсивных методов.
Например, в задаче нужно выбрать из N чисел K с максимальной суммой.В этом случае можно перебрать все возможные комбинации К чисел из заданных N и на каждом шаге проверять, является ли сумма текущей комбинации больше, чем ранее найденный максимум.
Эту задачу, конечно, можно решить гораздо проще, отсортировав числа по невозрастанию и взяв из них К первых, но бывают задачи, которые не имеют решения, отличного от переборного.
| Задача 14-1. Монетки |
| Задача 14-2. Сумма кубов |
| Задача 14-3. Резисторы |