6.4А-5. Решение комбинаторных задач методом перебора.

6.4.2.1
решать комбинаторные задачи методом перебора.

2

Учащиеся
знают:
Как решать комбинаторные задачи методом перебора;
умеют:
решать комбинаторные задачи методом перебора.

3

Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Начальнику цеха надо распределить несколько видов работ между имеющимися станками, агроному – разместить посевы сельскохозяйственных культур на нескольких полях, заместителю директора школы – составить расписание уроков, ученому- химику – рассмотреть возможные связи между атомами и молекулами, лингвисту- учесть различные варианты значений букв незнакомого языка и т.д.
Очень часто и нам в жизни приходится делать выбор, принимать решение. Это сделать очень трудно, потому что приходится выбирать из множества возможных вариантов, различных способов, комбинаций. И нам всегда хочется, чтобы этот выбор был правильным. В этом нам помогают комбинаторные задачи, решая которые мы учимся думать необычно, оригинально, смело.

Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой.
Слово «комбинаторика» происходит от латинского слова combinate, которое означает «соединять», «сочетать».
Комбинаторные задачи – это задачи, требующие осуществления перебора всех возможных вариантов или подсчета их числа.

Простые задачи решают обыкновенным полным перебором возможных вариантов без составления различных таблиц и схем.
Задача.
Какие двузначные числа можно составить из цифр 1, 3, 4, 5?
Решение:
11, 13, 14, 15, 31, 33, 34, 35, 41, 43, 44, 45, 51, , 53, 54, 55.

Сколько двузначных чисел можно составить, используя цифры 1; 4; 7?
Решение: Для того, чтобы не пропустить и не повторить ни одного из чисел, будем выписывать их в порядке возрастания:
11;14;17;(начали с 1)
41;44;47;(начали с 4)
71;74;77;(начали с 7)
Таким образом, из трёх данных цифр можно составить всего 9 различных двузначных чисел.
Ответ: 9 чисел.

8

9

5 · 3 = 15 двузначных чисел

Задача 1. Из дома Буратино в театр ведут три дороги, а из театра в школу еще три дороги. Сколькими способами может Буратино пройти в школу, посетив театр?Решение.




11; 12; 13; 21; 22; 23; 31; 32; 33 – способ перебора
3 · 3 = 9 Ответ: 9.

Задача 2. Буратино пришел в школу и встретил своих друзей Арлекин, Пьеро, Мальвину. Они все обменялись рукопожатиями. Сколько всего рукопожатий было? Решение.

Граф – дерево.
БА; БП; БМ; АП; АМ; ПМ – метод перебора.
3 + 2 + 1 = 6
Ответ: 6.

Задача 3. У Мальвины было четыре яблока. Она решила угостить своих друзей. Сколькими способами Мальвина может это сделать, если она может все отдать одному или распределить их по своему желанию?

Решение. Ответ: 15.

Задача 4. В финальном забеге на 100 м участвуют Буратино, Арлекин и Пьеро. Назовите возможные варианты распределения призовых мест.

Ответ:Вариант 1: 1) Буратино, 2) Арлекин, 3) Пьеро.Вариант 2: 1) Буратино, 2) Пьеро, 3) Арлекин.Вариант 3: 1) Пьеро, 2) Буратино, 3) Арлекин.Вариант 4: 1) Пьеро, 2) Арлекин, 3) Буратино.Вариант 5: 1) Арлекин, 2) Пьеро, 3) Буратино.Вариант 6: 1) Арлекин, 2) Буратино, 3) Пьеро.