Перебор возможных вариантов
Презентация к уроку
Загрузить презентацию (587 кБ)
Цели урока:
- Формирование опорной системы знанийпо теме.
- Развитие логического мышления при анализе нового материала.
- Формирование интеллектуальных умений (овладение мыслительными операциями анализа, сравнения, обобщения и т.д.)
- Создание дидактических условий для обеспечения положительного эмоционального процесса обучения:
- привлечение яркого фактического материала,
- опора на явление окружающей жизни и опыт учащихся,
- побуждение их к оценке и выражению собственного отношения к изучаемым явлениям.
Программное обеспечение: мультимедийный проектор, компьютер, интерактивная доска.
Методическое обеспечение: презентация.
План урока:
- Организационный момент – 1 мин.;
- Устная работа – 3 мин.;
- Изучение нового материала – 7-8 мин.;
- Формирование умений и навыков – 26-30 мин.;
- Итоги урока – 1-2 мин.;
- Домашнее задание – 1-2 мин.
Ход урока
I. Организационный момент
II. Устная работа
Вычисли устно: (слайд 3)
III. Изучение нового материала
Перед нами нередко возникают проблемы, которые имеют не одно, а несколько различных решений. Обычно одни из них нас устраивают, а другие нет.
Рассмотрим первый пример:
1. Сколько двузначных чисел можно составить из цифр 1, 4 и 7? (слайд 4)
Решение на доске учителем и учащимися.
| 1 | 4 | 7 | |
| 1 | 11 | 14 | 17 |
| 4 | 41 | 44 | 47 |
| 7 | 71 | 74 | 77 |
2. Сколько чётных двузначных чисел можно составить из цифр 0, 1, 2, 4, 5, 9? (слайд 5)
Учитель обращает внимание на способ оформления решения с помощью таблицы. Учащимся предлагается найти сходство и различия в задачах №1 и №2.
После обсуждения строится таблица.
| 0 | 2 | 4 | |
| 1 | 10 | 12 | 14 |
| 2 | 20 | 22 | 24 |
| 4 | 40 | 42 | 44 |
| 5 | 50 | 52 | 54 |
| 9 | 90 | 92 | 94 |
5 * 3 = 15 чётных двузначных чисел
3. В алфавите племени УАУА имеются только две буквы – «а» и «у». Сколько различных слов по три буквы в каждом слове можно составить, используя алфавит этого племени?
Учитель предлагает решить учащимся самостоятельно, с проверкой на доске.
4. На завтрак Вова может выбрать плюшку, бутерброд, пряник или кекс, а запить их он может кофе, соком или кефиром. Из скольких вариантов завтрака Вова может выбрать?
Учащиеся решают вместе с учителем ( слайд 6)
| Плюшка | Бутерброд | Пряник | Кекс | |
| Кофе | Плюшка Кофе | Бутерброд Кофе | Пряник Кофе | Кекс Кофе |
| Сок | Плюшка Сок | Бутерброд Сок | Пряник Сок | Кекс Сок |
| Кефир | Плюшка Кефир | Бутерброд Кефир | Пряник Кефир | Кекс Кефир |
3 * 4 = 12 – вариантов завтрака
Выводы:
В данных примерах был осуществлен способ перебора возможных вариантов (возможных комбинаций). Поэтому данные задачи называют комбинаторными. Решения данных задач основывается на общем правиле умножения. (слайд 7)
«Правило умножения»
Для того чтобы найти число всех возможных исходов независимого проведения двух испытаний А и В, следует перемножить число всех исходов испытания А и число всех исходов испытания В
IV. Формирование умений и навыков
Реши самостоятельно (слайд 8)
Составьте все двузначные числа, в записи которых используются только цифры 3 и 7.
Сколько двузначных чисел можно составить, в записи которых используются цифры 2, 4, 7, 8? Сколько двузначных чисел можно записать, если использовать при записи числа каждую из указанных цифр только один раз? Сколько чётных двузначных чисел получится из этих цифр?
Сколькими способами можно составить патруль из двух милиционеров, если на дежурство вышли четверо: Быков, Свистунов, Умнов и Дубов?
В четверг в первом классе должно быть три урока: русский язык, математика и физкультура. Сколько различных вариантов расписания можно составить на этот день?
Указание: перебирая варианты, введите обозначения: Р – русский язык, М – математика, Ф – физкультура.
(Решение задач самостоятельное, с последующей проверкой на доске (слайды 9,10))
V. Итоги урока
VI. Домашнее задание
1. Сколько можно составить двузначных чисел, в записи которых используются только цифры 1, 5, 6, 8? Сколько двузначных чисел можно записать, если использовать при записи числа каждую из указанных цифр только один раз? Сколько получится чётных чисел? Сколько получится чисел, которые делятся на пять?
2. Сколькими способами можно выбрать два цветка, если есть васильки, маки, тюльпаны и ромашки? Сколько получится таких пар, если их составлять из двух разных цветков?
Используемая литература:
- События. Вероятности. Статистическая обработка данных: Доп. параграфы к курсу алгебры 7-9 кл. общеобразоват. учреждений / А.Г. Мордкович, П.В. Семенов. – 4-е изд. – М.: Мнемозина, 2006.
- Вероятность и статистика. 5-9 кл.: пособие для общеобразоват. учеб. заведений / Е.А. Бунимович, В.А. Булычев. – 2-е изд. стереотип. – М.: Дрофа, 2004.
- Алгебра : элементы статистики и теории вероятностей : учеб. пособие для учащихся 7-9 кл. общеобразоват. учреждений / Ю.Н. Макарычев, Н.Г. Миндюк; под ред. С.А. Теляковского. – 4-е изд. – М.: Просвещение, 2006.
- Бродский И.Л., Литвиненко Р.А. Вероятность и статистика. 7-9 классы. Решение задач из учебника под редакцией Г.В. Дорофеева. – М.: АРКТИ, 2006
- Теория вероятностей и статистика для школьников( задачи и решения)/ Учебно-практическое пособие. Г.И.Просветов.- Москва:Альфа-Пресс, 2009.
Источник
Методы решения комбинаторных задач
Методы решения комбинаторных задач
Перебор возможных вариантов
Простые задачи решают обыкновенным полным перебором возможных вариантов без составления различных таблиц и схем.
Задача 1.
Какие двузначные числа можно составить из цифр 1, 2, 3, 4, 5?
Ответ: 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.
Задача 2.
В финальном забеге на 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) Орлов.
Задача 3.
В кружок бального танца записались Петя, Коля, Витя, Олег, Таня, Оля, Наташа, Света. Какие танцевальные пары девочки и мальчика могут образоваться?
Ответ:
1) Таня — Петя, 2) Таня — Коля, 3) Таня — Витя, 4) Таня — Олег, 5) Оля — Петя, 6) Оля — Коля, 7) Оля — Витя, 8) Оля — Олег, 9) Наташа — Петя, 10) Наташа — Коля, 11) Наташа — Витя, 12) Наташа — Олег, 13) Света — Петя, 14) Света — Коля, 15) Света — Витя, 16) Света — Олег.
Дерево возможных вариантов
Самые разные комбинаторные задачи решаются с помощью составления специальных схем. Внешне такая схема напоминает дерево, отсюда и название метода — дерево возможных вариантов.
Задача 4.
Какие трехзначные числа можно составить из цифр 0, 2, 4?
Решение. Построим дерево возможных вариантов, учитывая, что 0 не может быть первой цифрой в числе. 
Ответ: 200, 202, 204, 220, 222, 224, 240, 242, 244, 400, 402, 404, 420, 422, 424, 440, 442, 444.
Задача 5.
Школьные туристы решили совершить путешествие к горному озеру. Первый этап пути можно преодолеть на поезде или автобусе. Второй этап — на байдарках, велосипедах или пешком. И третий этап пути — пешком или с помощью канатной дороги. Какие возможные варианты путешествия есть у школьных туристов?
Решение. Построим дерево возможных вариантов, обозначив путешествие на поезде П, на автобусе — А, на байдарках — Б, велосипедах — В, пешком — Х, на канатной дороге — К.
Ответ: На рисунке перечислены все 12 возможных вариантов путешествия школьных туристов.
Задача 6.
Запишите все возможные варианты расписания пяти уроков на день из предметов: математика, русский язык, история, английский язык, физкультура, причем математика должна быть вторым уроком.
Решение. Построим дерево возможных вариантов, обозначив М — математика, Р — русский язык, И — история, А — английский язык, Ф — физкультура.
Ответ: Всего 24 возможных варианта:
Источник
Элементы комбинаторики. Методы решения некоторых задач
Разделы: Математика
1) Немного истории.
В математике и ее приложениях часто приходится иметь дело с различного рода множествами и подмножествами: устанавливать их связь между элементами каждого, определять число множеств или их подмножеств, обладающих заданным свойством. Такие задачи приходится рассматривать при определении наиболее выгодных коммуникаций внутри города, при организации автоматической телефонной связи, работы морских портов, при выявлении связей внутри сложных молекул, генетического кода, а также в лингвистике, в автоматической системе управления, значит и в теории вероятностей, и в математической статистике со всеми их многочисленными приложениями.
Поговорим об одном из разделов теории вероятности – комбинаторике.
Комбинаторика — ветвь математики, изучающая комбинации и перестановки предметов. Еще комбинаторику можно понимать как перебор возможных вариантов. Комбинаторика возникла в 17 веке. Долгое время она лежала вне основного русла развития математики.
С задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов — во время работы.
Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие, в первую очередь, умения рассчитывать, составлять планы и опровергать планы противника.
Со временем появились различные игры (нарды, карты, шашки, шахматы и т.д.). В каждой из этих игр приходилось рассматривать различные сочетания фигур, и выигрывал тот, кто их лучше изучил, знал выигрышные комбинации и умел избегать проигрышных. Не только азартные игры давали пищу для комбинаторных размышлений математиков. Еще с давних пор дипломаты, стремясь к тайне переписки, изобретали сложные шифры, а секретные службы других государств пытались эти шифры разгадать. Стали применять шифры, основанные на комбинаторных принципах, например, на различных перестановках букв, заменах букв с использованием ключевых слов и т.д.
Комбинаторика как наука стала развиваться в 18 веке параллельно с возникновением теории вероятностей, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов. Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж.Кардано, Н.Тарталье (1499-1557), Г.Галилею (1564-1642) и французс- ким ученым Б.Паскалю (1623-1662) и П.Ферма.
Комбинаторику как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г.Лейбниц в своей работе “ Об искусстве комбинаторики ”, опубликованной в 1666 году. Он также впервые ввел термин “комбинаторика”. Значительный вклад в развитие комбинаторики внес Л.Эйлер. В современном обществе с развитием вычислительной техники комбинаторика “добилась” новых успехов. В настоящее время в образовательный стандарт по математике включены основы комбинаторики, решение комбинаторных задач методом перебора, составлением дерева вариантов (еще его называют “дерево возможностей”) с применением правила умножения. Так, например, “дерево возможностей” помогает решать разнообразные задачи, касающиеся перебора вариантов происходящих событий. Каждый путь по этому “дереву” соответствует одному из способов выбора, число способов выбора равно числу точек в нижнем ряду “дерева”. Правило умножения заключается в том, что для того, чтобы найти число всех возможных исходов независимого проведения двух испытаний А и В, следует перемножить число всех исходов испытания А и число всех исходов испытания В. В задачах по комбинаторике часто применяется такое понятие как факториал (в переводе с английского “factor” — “множитель”).
Итак, произведение всех натуральных чисел от 1 до n включительно называют n-факториалом и пишут: n!=1 2 3 … (n-1) n
В комбинаторике решаются задачи, связанные с рассмотрением множеств и составлением различных комбинаций из элементов этих множеств. В зависимости от правил составления можно выделить три типа комбинаций: перестановки, размещения, сочетания.
2) ЗАДАЧИ
1. В школьной столовой на первое можно заказать борщ, солянку, грибной суп, на второе — мясо с макаронами, рыбу с картошкой, курицу с рисом, а на третье — чай и компот. Сколько различных обедов можно составить из указанных блюд?
1 способ. Перечислим возможные варианты
Источник
