Решение комбинаторных задач способом дерева

Методы решения комбинаторных задач

Методы решения комбинаторных задач

Перебор возможных вариантов

Простые задачи решают обыкновенным полным перебором возможных вариантов без составления различных таблиц и схем.

Задача 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 возможных варианта:

Источник

Занятие математического кружка в 3 классе по теме: «Решение комбинаторных задач с помощью дерева возможностей».

Занятие математического кружка в 3 классе по теме:«Решение комбинаторных задач с помощью дерева возможностей».

Цели занятия : закрепить представление о систематическом переборе вариантов и сформировать умение в простейших случаях использовать дерево возможностей для решения комбинаторных задач.

-научиться применять приёмы перебора различных вариантов; определять число вариантов с помощью умножения;

-познакомиться с понятием «дерево возможностей»:

-способствовать созданию ситуации успеха, воспитывать интерес к математике.

-развивать вариативное мышление.

В ид занятия : постановка и решение учебно-практической задачи; конкретизация и освоение способа действий.

Оборудование: карточки, презентация

Осознавать познавательную задачу, целенаправленно слушать, решая её.

Выделение и формулирование познавательных целей и задач, выбор наиболее эффективных способов решения с помощью учителя.

Построение логической цепочки рассуждений.

Анализ объектов с целью выделения признаков.

Выдвижение гипотезы и её обоснование.

Установление причинно-следственных связей.

Анализ результатов элементарных исследований; фиксировать их результаты;

воспроизведение по памяти информации, необходимой для решения учебной задачи.

Добывать новые знания; делать выводы в результате совместной работы класса. Расширение понятийной базы и использование новых понятий за счёт средств речевого отображения нового способа предметных действий с моделями.

Осуществлять действия по образцу и заданному правилу, обозначая информацию моделью пирамидки.

Осуществление анализа объектов с выделением существенных признаков.

Умение удерживать цель деятельности до получения ее результата.

Прогнозирование. Построение логической цепи рассуждений.

Умение планировать решение учебной задачи: выстраивать последовательность необходимых операций (алгоритм действий);

оценивать весомость приводимых доказательств и рассуждений.

– корректировать деятельность: вносить изменения в процесс с учетом возникших трудностей и ошибок; намечать способы их устранения;

– анализировать эмоциональные состояния, полученные от успешной (неуспешной) деятельности, оценивать их влияние на настроение человека.

Самостоятельное создание способов решения проблемы поискового характера.

Выделять, фиксировать и проговаривать последовательность операций предметного способа действия в диалоге с учителем и одноклассниками.

Умение корректировать деятельность: вносить изменения в процесс с учетом возникших трудностей и ошибок; намечать способы их устранения.

Умение конструировать способ решения задач в сотрудничестве с учителем и другими учащимся класса.

Участие в учебном диалоге.

П редставление цели и задачи конкретного содержания в устной речи с помощью учителя и пошаговое их выполнение. следование психологическим принципам общения, владея адекватным межличностным восприятием.

Регулировать своё поведение на основе усвоенных норм и правил; проявлять интерес к способам решения задачи; оформлять свою мысль в устной и письменной речи; слушать и понимать речь других; договариваться с одноклассниками и отвечать на их обращение в ходе общеклассной дискуссии.

Мотивация к учебной деятельности

Занимай свои места,

Чтоб от безделья не зевать,

Полезно задачи решать.

Кому ум служит, тот с задачами дружит.

Предлагаю вам сегодня подружиться с необычными задачами. А помогут нам знакомые герои.

Улыбаются друг другу, желают удачи.

Актуализация знаний и затруднение в деятельности.

Медленно текло время с Простоквашино.

Кот Матроскин задумался, как открыть сейф, где хранится фоторужьё Шарика. Составьте из цифр 1, 2, 3 все возможные числа так, чтобы цифры в записи чисел не повторялись. Помогите ему. Работайте в парах.

Сколько вариантов(комбинаций) получилось. Как искали варианты? (перебором) Задачи, к которых составляют различные комбинации по заданным условиям, называются комбинаторными.

Вот ещё такая задача:

У друга дяди Фёдора день рождения и нужно красиво упаковать подарок. Продавец предложил на выбор три вида бумаги: синюю, красную и зеленую и четыре вида бантиков: белый, голубой, желтый и розовый. Запишите все сочетания бумаги и бантиков.

Что нового в этом задании?

Попробуйте выполнить это задание — работаем в парах.

Каждый цвет обозначайте первой буквой его названия.

Учитель ограничивает их во времени.

Сколько вариантов вы составили?

Что вы не смогли сделать?

Кто смог выполнить задание, сколько сочетаний получилось?

Дети записывают числа

123, 132, 213, 231, 312, 321

Дети ищут варианты

Нужно составить комплекты из бумаги и бантиков.

Ученики выполняют задание на бланках.Не смогли составить все сочетания бантиков с бумагой.

Не можем объяснить, как правильно выполнить задание.

Разобраться, в чем у нас затруднение.

Постановка учебной задачи.

Почему вы смогли составить быстро все возможные трехзначные числа из цифр, а при составлении из семи цветов всех возможных сочетаний возникли затруднения?

Что же нам поможет не пропустить варианты и сосчитать их?

Составить все возможные сочетания бантиков с бумагой.

В том задании было три элемента, а здесь семь.

Мы знаем способ сочетания из трех элементов, а из семи не знаем.

«Открытие» детьми нового знания.

Разобраться в этом нам поможет …дерево. Оно так и называется ДЕРЕВО ВОЗМОЖНОСТЕЙ. Это тема нашего занятия. Что вы представляете, когда слышите слово «дерево»?

Как растет дерево?

Математическое дерево может расти и снизу вверх, и сверху вниз.

Ветви дерева изображают способы выбора вариантов.

Предлагаю сначала построить дерево для составления трехзначных чисел, а потом для нашего задания.

Черчу вместе с детьми на доске.

Начинаем наше построение от корня (точка вверху). Сколько цифр могут занимать сотни?

Поэтому от корня идут три веточки.

Подписываем три цифры – 1,2, 3

Теперь рассмотрим случай, когда число сотен равно 2. Чему в этом случае равно число десятков?

Отметим это на ветках нашего дерева.

Когда дерево полностью заполнено-посчитайте, следуя по веточкам, все варианты трехзначных чисел.

Соответствует ли это вашему способу, который был у вас в самом начале?

Таким образом, сколько у вас получилось «веточек» с вариантами?

Сколько точек на концах веточек?

Какой вывод сделаем?

Теперь попробуйте нарисовать дерево возможностей для вашей подарочной упаковки и выяснить, сколько способов сочетания цвета и бумаги существует.

Выдаю новые листы.

Если возникли затруднения, объясняю фронтально.

На середине строки поставьте точку-корень.

Сколько вариантов бумаги предложил продавец? Назовите эти цвета.

Сколько веточек нарисуете от корня?

Обозначьте их буквами, соответствующими названию цветов.

Что делаем дальше?

Сколько нарисуете веточек от каждого цвета бумаги?

Нарисуйте и обозначьте цвета бантиков.

Сколько вариантов сочетания бумаги и бантика получилось?

Что нужно сделать, чтобы ответить на этот вопрос?

Какой ошибки помогает избежать новый способ?

Дерево возможностей помогает отыскать все варианты решения, не пропуская ни одного.

Обведите красным карандашом то сочетание цветов, которое вы выбрали для упаковки подарка другу.

Итак, как же правильно построить дерево возможностей?

В центре изобразить корень дерева — поставить точку.

От корня пустить первый ряд веточек. От каждой веточки еще веточки, получится второй ряд. От чего зависит количество веточек?

Как узнать, сколько всего вариантов? А как можно догадаться, сколько вариантов получиться?(умножить количество признаков друг на друга)

«Открыть» способ построения всех вариантов сочетания элементов, когда их больше, чем три.

Многолетнее растение с твердым стволом, ветками с листьями, образующими крону.

Мы должны построить дерево возможностей.

Количество вариантов равно количеству веточек или точек на их концах-6.

Три цвета – синий, красный, зеленый.

К бумаге каждого цвета подбираем бантики.

Посчитать количество точек на концах веточек.

Пропуска и повторения вариантов сочетания.

От количества признаков.

Работа в группах.

1.Помогаем папе дяде Фёдора выбрать составить меню для обеда: «Имеется 2 первых блюда — борщ и щи, 3 вторых — рыба, гуляш, плов, 2 третьих-компот и чай. Сколькими способами можно составить набор блюд для обеда. Постройте «дерево возможностей» Сравните ответы в группе и выработайте общее решение. Подумайте, как можно было узнать число вариантов с помощью арифметического действия. (2·3·2=12 способов)

2.Подбираем одежду для мамы: «У мамы 4 кофты – красная, жёлтая, голубая и зелёная и две юбки синяя и белая. Закончите составление дерева и узнайте, сколькими способами мама может составить себе костюм? Постройте «дерево возможностей» Сравните ответы в группе и выработайте общее решение. Подумайте, как можно было узнать число вариантов с помощью арифметического действия. (4·2=8 способов)

3. Дядя Фёдор ходит в школу в брюках или джинсах, к ним одевает рубашки серого, голубого, зеленого цвета или в клетку, а в качестве сменной обуви берет туфли или кроссовки. (2·4·2=16 способов)

Закончите составление дерева и узнайте, сколькими способами дядя Фёдор может одеться в школу костюм?. Сравните ответы в группе и выработайте общее решение. Подумайте, как можно было узнать число вариантов с помощью арифметического действия.

4. У Матроскина есть кувшин, банка и бутылка. Сколькими способами он может налить в них молоко, простоквашу и кефир.(3·3=9способов)

Закончи заполнение «Дерева возможностей» и установи, сколько вариантов получиться. Сравни свой ответ с ответами в группе и выберите в группе общий ответ. Какой из вариантов больше понравился? Обведи его. Подумайте, как можно было узнать число вариантов с помощью арифметического действия.

Источник

Презентация на тему «Комбинаторные задачи. Дерево возможных вариантов»

Описание презентации по отдельным слайдам:

Комбинаторные задачи: дерево возможных вариантов

ИМЯ УРОКА: КОМБИНАТОРИКА ДЕВИЗ УРОКА: «УСЛЫШАЛ – ЗАБЫЛ, УВИДЕЛ – ЗАПОМНИЛ, СДЕЛАЛ – ПОНЯЛ» КИТАЙСКАЯ ПОГОВОРКА

В странных русских сказаниях повествуется, как богатырь или другой добрый молодец, доехав до распутья, читает на камне: Вперёд поедешь – голову сложишь. Налево поедешь – меча лишишься. А дальше говорится, как он выходит из того положения, в которое попал в результате выбора. Направо поедешь – коня потеряешь. Но выбирать разные пути или варианты приходится и современному человеку. Эти пути и варианты складываются в самые разнообразные комбинации.

Что такое КОМБИНАТОРИКА? Задачи, в которых требуется осуществить перебор всех возможных вариантов, или, как обычно говорят в таких случаях, всех возможных комбинаций, называют комбинаторными. Область математики, изучающая комбинаторные задачи, называется комбинаторикой. Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить.

Задача №1 Запишите все трёхзначные числа, для записи которых употребляются только цифры 1 и 2. 1 2 1 1 2 2 1 1 1 1 2 2 2 2 Ответ: 111, 112, 121, 122, 211, 212, 221, 222 – восемь чисел. Такой метод решения комбинаторных задач называется деревом выбора(дерево возможных вариантов)

Задача №2 Запишите все трёхзначные числа, для записи которых употребляются только цифры 0,7.

ЗАДАЧА 3 В 5 «А» классе в среду 4 урока: математика, информатика, русский язык, английский язык. Сколько можно составить вариантов расписания на среду? Решение: построим картину-схему. Для удобства закодируем названия предметов: математика – м, информатика – и, русский язык – р, английский язык – а.

РЕШЕНИЕ ЗАДАЧИ 3 Расписание 1 урок м и р а 2 урок и р а м р а м и а м и р 3 урок р а и а и р р а м а м р и а м а м и и р м р м и 4 урок а р а и р и а р а м р м а и а м и м р и р м и м Ответ: 24 варианта: мира, миар, мриа, мраи, маир, мари, имра, имар, ирма, ирам, иамр, иарм, рмиа, рмаи, рима, риам, рами, раим, амир, амри, аимр, аирм, арми, арим.

Построенная схема напоминает перевернутое дерево: от ствола («расписание») отходят ветки, сначала четыре (м, и, р, а), от каждой из четырех веток – еще по три, затем еще по две и еще по одной. Видимо поэтому такую схему называют деревом возможных вариантов. Дерево возможных вариантов можно считать геометрической моделью рассматриваемой ситуации.

Задача №4 В правление фирмы входят 5 человек. Из своего состава правления должно выбрать президента и вице-президента. Сколькими способами это можно сделать? Президент 1 Вице – президент 2 3 4 5 2 1 3 4 5 3 1 2 4 5 4 1 2 3 4 5 1 2 3 5 Такой метод решения комбинаторных задач называется правилом умножения. Выбрать президента можно пятью способами, а для каждого выбранного президента четырьмя способами можно выбрать вице-президента . Следовательно, общее число способов выбрать президента и вице-президента фирмы равно: 5*4=20.

Можно решить Задачу 3 короче, если применить правило умножения. Существует 4 варианта выбора первого урока. Для выбора второго урока есть только три варианта, так как один из четырех уроков мы уже выбрали. Тогда для третьего урока существует два варианта, а для четвертого только один. Применив правило умножения, получим 4 ∙ 3 ∙ 2 ∙1= 24 Ответ: 24 варианта.

Задача №5 В классе 15 мальчиков и 10 девочек. Сколькими способами можно выбрать двух дежурных(одну девочку и одного мальчика)?

ЗАДАЧА 2. В 6 классе в четверг 5 уроков: математика, информатика, русский язык, английский язык, физкультура. а) Сколько имеется вариантов расписания при условии, что физкультура – последний урок? б) Сколько имеется вариантов расписания при условии, что физкультура – последний урок, а математика – первый?

ЗАДАЧА 2 (ПРОДОЛЖЕНИЕ). В 6 классе в четверг 5 уроков: математика, информатика, русский язык, английский язык, физкультура. в) Сколько всего можно составить вариантов расписания на четверг? г) Сколько времени потратит завуч на запись всех вариантов, если известно, что на запись одного варианта у него уходит 30 секунд?

Задача №1 Запишите все трёхзначные числа, для записи которых употребляются только цифры 0,7. Задача №2 Сколько двузначных чисел можно составить, используя цифры 1, 4 и 7? Нарисуйте дерево выбора на альбомном листе. Задача №3 Составьте комбинаторную задачу, которая решается с помощью правила умножения. Сделайте к ней рисунок. Задача № 4 Тренер попросил Филю составить трехзначное число из цифр 1, 2, 3, 4, причем цифры в числе могут повторяться. Сколько чисел может составить Филя? Задача № 5 Тренер попросил Филю составить трехзначное число из цифр 1, 2, 3, 4 так, чтобы цифры в числе не повторялись. Сколько чисел может составить Филя? Домашнее задание

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

• Сейчас обучается 801 человек из 76 регионов

Курс повышения квалификации

Методика обучения математике в основной и средней школе в условиях реализации ФГОС ОО

• Сейчас обучается 283 человека из 69 регионов

Курс профессиональной переподготовки

Математика: теория и методика преподавания в образовательной организации

• Сейчас обучается 605 человек из 75 регионов

Ищем педагогов в команду «Инфоурок»

Номер материала: ДБ-409677

Международная дистанционная олимпиада Осень 2021

Не нашли то что искали?

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Безлимитный доступ к занятиям с онлайн-репетиторами

Выгоднее, чем оплачивать каждое занятие отдельно

Рособрнадзор откажется от ОС Windows при проведении ЕГЭ до конца 2024 года

Время чтения: 1 минута

В 16 регионах ввели обязательную вакцинацию для студентов старше 18 лет

Время чтения: 1 минута

Минпросвещения разрабатывает образовательный минимум для подготовки педагогов

Время чтения: 2 минуты

Минпросвещения будет стремиться к унификации школьных учебников в России

Время чтения: 1 минута

Шойгу предложил включить географию в число вступительных экзаменов в вузы

Время чтения: 1 минута

В Осетии студенты проведут уроки вместо учителей старше 60 лет

Время чтения: 1 минута

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Источник