«Примеры комбинаторных задач» Урок-дуэт математика-информатика

Цели: Развитие умения решать комбинаторные задачи методом полного перебора вариантов на персональных компьютерах в программе Microsoft Word при помощи схематических диаграмм. Развитие умения решать комбинаторные задачи методом полного перебора вариантов на персональных компьютерах в программе Microsoft Word при помощи схематических диаграмм. Совершенствовать навыки работы с ПК Совершенствовать навыки работы с ПК Воспитывать познавательный интерес к учебным предметам. Воспитывать познавательный интерес к учебным предметам.

В науке и практике часто встречают задачи, решая которые приходится составлять различных комбинации из конечного числа элементов и подсчитывать число комбинаций. Такие задачи получили название комбинаторных задач, а раздел математики, в котором рассматриваются подобные задачи, называют комбинаторикой. Итак, комбинаторика – наука о переборе и подсчете комбинаций. Слово «комбинаторика» происходит от латинского слова combinare, которое означает «соединять, сочетать». Методы комбинаторики находят широкое применение в физике, химии, биологии, экономике и других областях знаний.

Пример 1. Из группы теннисистов, в которую входят четыре человека – Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Из группы теннисистов, в которую входят четыре человека – Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары? Сколько существует вариантов выбора такой пары?

Пример 2. Сколько трехзначных чисел можно составить из цифр 1, 3, 5, 7, используя в записи числа каждую из них не более одного раза? Сколько трехзначных чисел можно составить из цифр 1, 3, 5, 7, используя в записи числа каждую из них не более одного раза?

Решение 135, 137, 153, 157, 173, 175, 135, 137, 153, 157, 173, 175, 315, 317, 351, 357, 371, 375, 315, 317, 351, 357, 371, 375, 513, 517, 531, 537, 571, 573, 513, 517, 531, 537, 571, 573, 713, 715, 731, 735, 751, , 715, 731, 735, 751, 753.

Дерево возможных вариантов *

Комбинаторное правило умножения Пусть имеется n элементов и требуется выбрать один за другим некоторые k элементов. Если первый элемент можно выбрать n1 способами, после чего второй элемент можно выбрать из оставшихся элементов n2 способами, затем третий элемент - n3 способами и т.д., то число способов, которыми могут быть выбраны все k элементов, равно произведению Пусть имеется n элементов и требуется выбрать один за другим некоторые k элементов. Если первый элемент можно выбрать n1 способами, после чего второй элемент можно выбрать из оставшихся элементов n2 способами, затем третий элемент - n3 способами и т.д., то число способов, которыми могут быть выбраны все k элементов, равно произведению

Пример 3. На обед в школьной столовой предлагают 2 супа, 3 вторых блюда и 4 разных сока. Сколько различных вариантов обеда из трех блюд можно составить по предложенному меню?

Дерево различных вариантов обеда из 3 блюд

Дерево различных вариантов обеда из 3 блюд *

Пример 4. От турбазы к горному озеру ведут 4 тропы. Сколькими способами туристы могут отправиться в поход к озеру, если они не хотят спускаться по той же тропе, по которой поднимались? От турбазы к горному озеру ведут 4 тропы. Сколькими способами туристы могут отправиться в поход к озеру, если они не хотят спускаться по той же тропе, по которой поднимались?

Дерево различных вариантов похода туристов *

На первом уровне дерева 4 «узла» (подъем по любой из 4 троп). Из каждого узла выходят 3 ветки (спуск по 3 остальным тропам). Всего получилось 4 3 = 12 маршрутов подхода к озеру. На первом уровне дерева 4 «узла» (подъем по любой из 4 троп). Из каждого узла выходят 3 ветки (спуск по 3 остальным тропам). Всего получилось 4 3 = 12 маршрутов подхода к озеру. Представим, что к озеру ведут не 4, а 10 троп. Сколько в этом случае существует маршрутов, если по-прежнему решено спускаться не по той тропе, по которой поднимались? Представим, что к озеру ведут не 4, а 10 троп. Сколько в этом случае существует маршрутов, если по-прежнему решено спускаться не по той тропе, по которой поднимались? Изобразить дерево возможных вариантов в такой ситуации сложно. Гораздо легче решить эту задачу с помощью рассуждений. Изобразить дерево возможных вариантов в такой ситуации сложно. Гораздо легче решить эту задачу с помощью рассуждений. Подниматься к озеру можно по любой из троп, а спускаться по любой из оставшихся 9 троп. Таким образом, всего получим 10 * 9 = 90 различных маршрутов похода. Подниматься к озеру можно по любой из троп, а спускаться по любой из оставшихся 9 троп. Таким образом, всего получим 10 * 9 = 90 различных маршрутов похода.

Диапазон использования правила умножения Комбинаторное правило умножения можно использовать только если дерево вариантов «правильное»: из каждого узла одного уровня выходит одно и тоже число веток. Комбинаторное правило умножения можно использовать только если дерево вариантов «правильное»: из каждого узла одного уровня выходит одно и тоже число веток. Заметим, что если надо проверить, является ли дерево правильным, то не обязательно строить дерево целиком. Достаточно изобразить его фрагмент. По нему нетрудно увидеть, что в данной ситуации дерево «правильное». Заметим, что если надо проверить, является ли дерево правильным, то не обязательно строить дерево целиком. Достаточно изобразить его фрагмент. По нему нетрудно увидеть, что в данной ситуации дерево «правильное».

Правильное дерево построено не целиком

Правильное дерево построено не целиком *

Пример 5. Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут? Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут?

Решение не построением дерева, а рисунком по условию задачи

Неправильное дерево Не в каждой комбинаторной задаче дерево возможных вариантов будет правильным. Если дерево неправильное, то в данной задаче правильно умножения неприменимо. Как же тогда решать такие задачи? Не в каждой комбинаторной задаче дерево возможных вариантов будет правильным. Если дерево неправильное, то в данной задаче правильно умножения неприменимо. Как же тогда решать такие задачи?

Пример 6. Из 4 ребят надо выделить двоих для дежурства по классу. Из 4 ребят надо выделить двоих для дежурства по классу. Сколькими способами это можно сделать? Сколькими способами это можно сделать?

Итог урока Тест самооценки ученика Задачи Ответы Задача 1 8 вариантов Задача 2 8 вариантов Задача 3 12 вариантов Задача 4 12 вариантов Задача 5 6 вариантов Итог: