31
Решение комбинаторных задач перебором вариантов
Учебник: с. 200–202
ЦельРешай комбинаторные задачи, перечисляя все возможности по порядку и с помощью дерева вариантов.
Новые слова
комбинаторная задача · kombinatorik masalaметод перебора · tanlash (sanab chiqish) usuliдерево вариантов · variantlar daraxtiчисло возможностей · imkoniyatlar soni
Объяснение
В комбинаторных задачах нужно найти число всех способов (вариантов), удовлетворяющих условию. Чтобы не пропустить ни один вариант и не повторить ни одного, их записывают упорядоченно, например в порядке возрастания или группируя по первому элементу. Другое удобное средство — дерево вариантов: из корня проводят ветвь для каждой возможности первого выбора, а из каждой из них — ветви для следующего выбора; число конечных вершин дерева равно числу всех вариантов. Когда составляют числа из цифр, условие говорит, разрешены ли повторения.
Примеры
Выбор капитана и помощника из четырёх учеников A, B, D, G (порядок важен): AB, AD, AG, BA, BD, BG, DA, DB, DG, GA, GB, GD — всего 12.
Четыре одноклассника A, B, C, D выбирают пару дежурных по классу (порядок не важен): AB, AC, AD, BC, BD, CD — 6 пар.
Работа в классе
«Нарисуй дерево»: группы рисуют на доске дерево вариантов обеда из двух соков и трёх видов выпечки и считают все виды обеда.
Упражнения
1
Запиши все трёхзначные числа из цифр 1 и 2 (повторения разрешены) и скажи, сколько их.
111, 112, 121, 122, 211, 212, 221, 222 — 8 чисел
2
Сколькими способами могут сесть на три места Али, Вали и Сами? Перечисли их.
6
3
Выбирают две из 3 видов конфет (порядок не важен). Сколько есть способов?
3
4
Почему важно перечислять варианты упорядоченно?
Если перечислять по порядку, ни один вариант не будет пропущен или повторён.