Перебор вариантов и основы комбинаторики

Перебор вариантов и комбинаторика

Многие задачи требуют подсчитать число возможных вариантов: сколько разных паролей можно составить, сколькими способами выбрать команду, сколько маршрутов ведёт из города в город. Раздел математики, который этим занимается, называют комбинаторикой, а способ решения задачи прямым просмотром всех возможностей — полным перебором.

Правило произведения

Правило произведения: если первый выбор можно сделать m способами, а после него второй — n способами, то всю последовательность из двух выборов можно сделать m * n способами. Правило распространяется на любое число шагов: результаты просто перемножаются.

Пример: В меню 3 первых блюда и 4 вторых. Обед из первого и второго блюда можно составить 3 * 4 = 12 способами.

Правило суммы

Правило суммы: если объект можно выбрать либо из первой группы (m способов), либо из второй (n способов), и группы не пересекаются, то всего способов m + n. Ключевое слово-подсказка для суммы — «или», для произведения — «и».

Подсчёт числа строк и паролей

Если строка состоит из k символов и каждый символ выбирают из алфавита в N символов, то число различных строк равно N в степени k. Это прямое следствие правила произведения: на каждой из k позиций есть N вариантов.

Разбор: Пароль из 3 цифр. На каждой позиции 10 вариантов (от 0 до 9). Всего паролей: 10 * 10 * 10 = 10^3 = 1000.

Как быстро растёт число вариантов

Главная особенность комбинаторных задач — стремительный рост числа вариантов. Добавление всего одного символа к паролю умножает количество вариантов на размер алфавита. Эту зависимость важно понимать: то, что кажется небольшим увеличением длины, на деле многократно увеличивает число возможностей.

Полный перебор в программе

Когда число вариантов невелико, их можно перебрать вложенными циклами и проверить каждый. Например, чтобы найти все пары цифр, дающих в сумме 9, перебирают первую и вторую цифру двумя вложенными циклами и выводят подходящие пары. Именно из-за быстрого роста числа вариантов полный перебор подходит только для небольших задач: при большой длине строки даже самый быстрый компьютер не успеет просмотреть все варианты за разумное время.

Частые ошибки. Путают, когда складывать, а когда умножать: «и» — умножаем, «или» — складываем. При подсчёте строк степень — это длина строки, а основание — размер алфавита, не наоборот. Перебор удобен только при небольшом числе вариантов: оно растёт очень быстро.

Кратко о главном

• Комбинаторика считает число вариантов; полный перебор просматривает их все.
• Правило произведения (для «и»): число способов перемножают.
• Правило суммы (для «или»): число способов складывают.
• Число строк длины k из алфавита в N символов равно N в степени k.
• Полный перебор в программе реализуют вложенными циклами.