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

Решение задач на перебор вариантов
план-конспект по алгебре

Скачать:

Вложение	Размер
30._primery_kombinatornyh_zadach.ppt	1.74 МБ
30.doc	35.5 КБ

Предварительный просмотр:

Подписи к слайдам:

Примеры комбинаторных задач

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

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

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

Ответ: 24 трехзначных числа. Пример 2. Сколько трехзначных чисел можно составить из цифр 2 , 4 , 6 , 8 , используя в записи числа каждую из них не более одного раза? Решение:

Решение: Пример 3. Из города А в город B ведут 3 дороги, из города B в город C — 4 дороги, из города C до пристани – 2 дороги. Туристы хотят проехать из города А через город B и C к пристани. Сколькими способами они могут выбрать маршрут. Ответ: 24 способа.

Предварительный просмотр:

30. Примеры комбинаторных задач

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

Рассмотрим некоторые комбинаторные задачи.

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

Решение. Составим сначала пары, в которые входит Андреев. Для краткости будем писать первые буквы фамилий. Получим три пары: Андреев-Гришин, Андреев-Степанов, Андреев-Николаев.

Выпишем теперь пары, в которые входит Гришин, но не входит Андреев. Таких пар две: Гришин-Степанов, Гришин-Николаев.

Далее составим пары, в которые входит Степанов, но не входят Андреев и Гришин. Такая пара одна: Степанов-Николаев.

Других вариантов составления пар нет, потому что все пары, в которые входит Николаев, уже составлены.

Итак, получили шесть пар: Андреев-Гришин, Андреев-Степанов, Андреев-Николаев, Гришин-Степанов, Гришин-Николаев, Степанов-Николаев.

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

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

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

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

Итак, мы составили все числа, которые начинаются с цифры два. Таких чисел шесть…..

Аналогичным способом можно составить числа, которые начинаются с цифры четыре, с цифры шесть, с цифры восемь.

Полученные результаты запишем в четыре строки, в каждой из которых шесть чисел…..

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

Проведенный перебор вариантов проиллюстрирован на схеме. Такую схему называют деревом возможных вариантов….

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

Мы нашли ответ на поставленный во втором примере вопрос, используя комбинаторное правило умножения.

Сформулируем это правило в общем виде.

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

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

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

Источник

Задачи на перебор всех возможных вариантов

ФИО: Тютюгина Н. А.

Место работы: ГБУ РК «КСС «Симеиз»

Должность: учитель математики

Тема и номер урока в теме : гл. 1 , уроки № 29, 30

Тип урока: комбинированный (изучение нового материала; закрепление знаний и умений).

Конспект урока по теме «Задачи на перебор всех возможных вариантов»

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

Актуализация опорных знаний.

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

Решение задач с помощью схем, таблиц.

Решение задачи обучающимися (самостоятельно).

Подведение итогов, домашнее задание.

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

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. Самые разные комбинаторные задачи решаются с помощью составления специальных схем. Внешне такая схема напоминает дерево, отсюда и название метода — дерево возможных вариантов.

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

Решение задач методом полного перебора всех возможных вариантов:

4) Какие трехзначные числа можно составить из цифр 0, 2, 4?

Ответ: 200, 202, 204, 220, 222, 224, 240, 242, 244, 400, 402, 404, 420, 422, 424, 440, 442, 444.

Сколько двузначных чисел можно составить, используя цифры 1; 4; 7?

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

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

Суп х 2, в торые блюда х3, сок х4

Решение : 2 x 3 x 4 = 24

Ответ : Можно составить 24 варианта различных обедов.

Андрей, Борис и Василий входят в комнату по одному. Сколько у них есть способов это сделать?

Решение . Пусть первым войдёт Андрей, но тогда вторым может войти Борис или Василий, то есть имеются две возможности. Аналогично есть две возможности, если первым войдёт Борис и если первым войдёт Василий.

2 x 3 =6. Таким образом, 6 возможностей.

Ответ : 6 способов.

5 . Решение задач самостоятельно.

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

2) Маша, Оля, Вера, Ира, Андрей, Миша и Игорь готовились стать ведущими на Новогоднем празднике. Назовите возможные варианты, если ведущими могут быть только одна девочка и один мальчик.

Источник

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

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

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

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

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

Источник

Конспект урока на тему «Задачи на перебор всевозможных вариантов»

Тема урока: Задача на перебор всех возможных вариантов.

Общеобразовательная (формирование познавательных УУД): сформировать основные умения находить возможные комбинации, составленные из чисел, слов, предметов, отвечающие условию задачи;

Воспитательная (формирование коммуникативных и личностных УУД): воспитывать умение слушать и вступать в диалог, участвовать в коллективном обсуждении проблемы, объединяться в группы и строить продуктивное взаимодействие, воспитывать ответственность и аккуратность.

развивающая:(формирование регулятивных УУД): развивать умение анализировать, сравнивать, обобщать, делать выводы, развивать внимание, формировать коммуникативную компетенцию учащихся; выбирать способы решения задач в зависимости от конкретных условий, контроль и оценка процесса и результатов деятельности.

предметные: метапредметные:уметь определять тему и цель урока,следовать этапам урока.

личностные: развитие качеств личности,адекватно оценивать результаты учебной деятельности.

Задача урока: Находить возможные комбинации, составленные из чисел, слов, предметов, отвечающие условию задачи;

Оборудование: тетрадь, учебник, доска.

Тип урока: комбинированный.

Организационный момент : Приветствие, проверка готовности класса к уроку.

Проверка домашнего задания:( самопроверка): обучащиеся зачитывают свои творч.задачи.

Устный счет : (фронтальная форма работы):

100×100, 100:100,2*3+5, 40:8, 50:2, 23+23, 44:11, 15+3,

Актуализация опорных знаний : Матем.диктант.(да или нет)

Пропорция-это равенство 2 величин, процент- это 1/100 часть числа, диаграмма-это рисунок, который наглядно показывает отношение между числами, нат число- это 0,1,2,3,…. вся величина составляет 100%. А теперь проверяем ответы.

Постановка цели и задач урока:

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

«На завтрак Митя может выбрать плюшку, бутерброд, пряник или кекс, а запить их он может кофе, соком или кефиром. Из скольких вариантов завтрака Вова может выбрать?» Как вы думаете ,чем мы сегодня будем заниматься? Какие решать задачи?

Первичное усвоение новых знаний:

Задача 1 . В алфавите племени АБ имеются только две буквы – «а» и «б». Сколько различных слов по три буквы можно составить, используя алфавит этого племени?

Способ перебора – выпишем слова в алфавитном порядке.

ааа, ааб, аба, абб,ббб,бба,баб,баа. Получили 8 слов.

Сколько двузначных чисел можно составить, используя цифры 1, 4 и 7?

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

11, 14, 17,41,44,47,71,74,77.

Из данных трех цифр можно составить 9 чисел.

В данных примерах был осуществлен способ перебора возможных вариантов (возможных комбинаций). Поэтому данные задачи называют комбинаторными.

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

Первичная проверка понимания: №148.

Первичное закрепление понимания:

№ 144 (а,в): а) 13,31,39,19,91,93. в) 24,42,46,26,62,64.

Итог урока: Обсуждение ошибок, выполнение задач урока

Итак,какие задачи наз.комбинаторные? Чему мы сегодня научились?

Рефлексия: Понравился урок….

Все получилось…. захотелось……………….

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Российские школьники завоевали пять медалей на олимпиаде по физике

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

Российский совет олимпиад школьников намерен усилить требования к олимпиадам

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

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

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

В Пензенской области запустят проект по снижению административной нагрузки на учителей

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

Правительство предложило потратить до 1 млрд рублей на установку флагов РФ у школ

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

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

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

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

Источник