Задачи решаемые способом перебора

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

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

Просмотр содержимого документа
«Решение задач на перебор вариантов»

Тема урока: Решение задач на перебор вариантов

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

метод перебора (подбираются задачи на развитие мышления);

табличный метод (все условия вносятся в таблицу, в ней же выполняется решение);

построение дерева возможных вариантов решений;

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

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

Способ перебора может применяться в простых задачах, например в таких, как эта:

Задача 1. Для своих двух книг Маша купила три разные обложки. Сколькими различными способами она может обернуть книги купленными обложками?

Ответ: Для решения обозначим обложки буквами а, б, в. Составим из букв всевозможные пары: аб, ав, бв, ба, ва, вб. Всего получилось 6 способов.

Задача 2. Какие двузначные числа можно составить из цифр 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.

Задача 3. В финальном забеге на 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) Орлов.

Задача 4. В кружок бального танца записались Петя, Коля, Витя, Олег, Таня, Оля, Наташа, Света. Какие танцевальные пары девочки и мальчика могут образоваться?

Ответ: 1) Таня — Петя, 2) Таня — Коля, 3) Таня — Витя, 4) Таня — Олег, 5) Оля — Петя, 6) Оля — Коля, 7) Оля — Витя, 8) Оля — Олег, 9) Наташа — Петя, 10) Наташа — Коля, 11) Наташа — Витя, 12) Наташа — Олег, 13) Света — Петя, 14) Света — Коля, 15) Света — Витя, 16) Света — Олег.

Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ?

Сколько различных коктейлей можно составить из четырёх напитков, смешивая их в равных количествах по два?

Сколькими способами можно составить патруль из двух

милиционеров, если на дежурство вышли четверо: Быков, Свистунов, Умнов и Дубов?

Источник

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

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

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

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

Тема и номер урока в теме : гл. 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 возможных варианта:

Источник

Задачи на перебор
план-конспект занятия (6 класс) на тему

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

Скачать:

Вложение	Размер
zadachi_na_perebor.docx	64.08 КБ

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

Тема: Задачи на перебор

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

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

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

развивающие : развитие познавательного интереса учащихся.

Планируемые результаты изучения темы:

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

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

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

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

1) Определить арифметическое действие, с помощью которого из двух крайних чисел получено среднее, и вместо знака «?» вставить пропущенное число.

42(47)5 6(66)11 36(25)11 48(4)12
31(?)8 5(?)12 48(?)12 100(?)5
Ответ: 39, 60, 36, 20.

1. Требуется распилить бревно на 6 частей. Каждый распил занимает 2 минуты. Сколько времени потребуется на эту работу?

Ответ: 10 минут.
3) Сколькими способами можно уплатить без сдачи 28 копеек, имея только монеты 1-и 5- копеечного достоинства?

1. Изучение нового материала

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

Задача 1 . Государственные флаги многих стран состоят из горизонтальных или вертикальных полос разных цветов. Сколько существует различных флагов, состоящих из двух горизонтальных полос одинаковой ширины и разного цвета, при этом используются цвета — белый, красный и синий.
Решение . Пусть верхняя полоска флага белая (Б). Тогда нижняя полоса может быть красной (К) или синей (С). Получили две комбинации — два варианта флага. Если верхняя полоса флага — красная, то нижняя может быть белой или синей. Получим еще два варианта флага. Пусть, наконец, верхняя полоса — синяя, тогда нижняя может быть белой или красной. Это еще два варианта флага. Всего получили 3∙2 = 6 комбинаций — шесть вариантов флагов.

Задача 2 . Сколько трехзначных цифр можно составить из цифр «1», «3», «5», «7», используя в записи числа каждую цифру не более одного раза?
Решение . Способ I. Чтобы ответить на этот вопрос, выпишем все такие числа. Пусть на первом месте стоит «1». На втором месте может быть записана любая из цифр «3», «5», «7». Запишем, например, на втором месте цифру «3». Тогда в качестве третьей цифры можно взять «5» или «7». Получим два числа 135 и 137. Если на втором месте написать цифру «5», то в качестве третьей цифры можно взять цифру «3» или «7». В этом случае получим числа 153 и 157. Если же, наконец, на втором месте записать цифру «7», то получим числа 173 и 175. Итак, мы составили все числа, которые начинаются с «1». Таких чисел шесть: 135, 137, 153, 157, 173, 175. Аналогичным способом можно составить числа, которые начинаются с цифры «3», с цифры «5», с цифры «7». Полученные результаты запишем в четыре строки, в каждой из которых шесть чисел:

Таким образом, из цифр «1», «3», «5», «7» (без повторения цифр) можно составить 24 трехзначных числа.

3) В финальном забеге на 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) Орлов.

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

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

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

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

Решение . Путь из A в B туристы могут выбрать двумя способами. Далее, в каждом случае они могут проехать из B в C тремя способами. Значит, имеются 2∙3 вариантов маршрута из A в C. Так как из города C на пристань можно попасть двумя способами, то всего существует 2∙3∙2, то есть 12 способов выбора туристами маршрута из города A к пристани.

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

1. Формирование умений и навыков

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Итог урока

• Какие задачи называются комбинаторными?
• Что означает слово «комбинаторика»?
• Как формулируется комбинаторное правило умножения?

1. Задание на дом
   Придумать задачу на комбинаторное правило умножения. Решить ее и оформить решение на альбомном листе.

По теме: методические разработки, презентации и конспекты

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

Презентация к уроку математики по учебнику С. А. Козлова, А. Г. Рубин МАТЕМАТИКА, 5 класс, БАЛАСС, 2012.

«Логика перебора» — урок по теории вероятностей

Конспект урока содержит подборку упражнений по теме «Логика перебора» , решения к ним и итоги урока.

Презентация к уроку 5 класс 2100 «Перебор возможных вариантов»

Презентаци к уроку по математике в 5 классе по программе «Школа 2100″. Тема урока :»Перебор возможных вариантов» (1 четверть).

Подготовка школьников к олимпиадам по программированию: решение задач на полный перебор

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

Галимова Р.А. Урок математики в 6 классе с применением структур Сингапурской системы «Решение комбинаторных задач.Перебор возможных вариантов.»

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

занятие внеурочной деятельности «Полный перебор» (7 класс)

Подборка задач на создание и решение Диофантовых уравнений.

Источник