Как составить дерево возможных вариантов


Методы решения комбинаторных задач - Сайт учителя математики Кобец Анны Викторовны - Сайт учителя математики Кобец Анны Викторовны

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

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

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

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

Р
М
И
А
Ф

Р
М
И
Ф
А

Р
М
А
И
Ф

Р
М
А
Ф
И

Р
М
Ф
И
А

Р
М
Ф
А
И

И
М
Р
А
Ф

И
М
Р
Ф
А

И
М
А
Р
Ф

И
М
А
Ф
Р

И
М
Ф
Р
А

И
М
Ф
А
Р

А
М
Р
И
Ф

А
М
Р
Ф
И

А
М
И
Р
Ф

А
М
И
Ф
Р

А
М
Ф
Р
И

А
М
Ф
И
Р

Ф
М
Р
И
А

Ф
М
Р
А
И

Ф
М
И
Р
А

Ф
М
И
А
Р

Ф
М
А
Р
И

Ф
М
А
И
Р

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

Решение. Построим дерево возможных вариантов, обозначив Б - брюки, Д - джинсы, С - серая рубашка, Г - голубая рубашка, З - зеленая рубашка, Р - рубашка в клетку, Т - туфли, К - кроссовки.

 

Ответ: а) 16 дней; б) 8 дней; в) 2 дня.

Составление таблиц

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

Задача 8.
Сколько нечетных двузначных чисел можно составить из цифр 1, 3, 4, 6, 7, 8, 9?

Решение. Составим таблицу: слева первый столбец - первые цифры искомых чисел, вверху первая строка - вторые цифры.

 

Ответ: 28.

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

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

 

Ответ: Все возможные варианты перечисляются в строках и столбцах таблицы.

Правило умножения

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

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

Решение.
Трусы могут быть белого, красного, синего или зеленого цвета, т.е. существует 4 варианта. Каждый из этих вариантов имеет 4 варианта цвета майки.

4 х 4 = 16.

Ответ: 16 команд.

Задача 11.
6 учеников сдают зачет по математатике. Сколькими способами их можно расположить в списке?

Решение.
Первым в списке может оказаться любой из 6 учеников,
вторым в списке может быть любой из оставшихся 5 учеников,
третьим - любой из оставшихся 4 учеников,
четвертым - любой из оставшихся 3 учеников,
пятым - любой из оставшихся 2 учеников,
шестым - последний 1 ученик.

6 х 5 х 4 х 3 х 2 х 1 = 720.

Ответ: 720 способами.

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

Решение.
Первой в двузначном числе может быть 5 цифр (цифра 0 не может быть первой в числе), второй в двузначном числе может быть 4 цифры (0, 2, 4, 6, т.к. число должно быть четным).
5 х 4 = 20.

Ответ: 20 чисел.

Дерево возможностей. Комбинаторные задачи. Факториал

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

Пример задачи.

Как составить цифр 1, 2, 3 все варианты трехзначных чисел (цифры не должны повторяться). 

Перебираем все возможные комбинации: 123, 132, 213, 231, 312, 321

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

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

Пример составления дерева возможностей. 

Имея цифры 1,3,5,7 составить все трехзначные числа. Посмотрите, как построено дерево возможностей. Попытайся понять принцип. Если трудно, посмотри ролик.

РОЛИК 1

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

РОЛИК 2

ЧТО ТАКОЕ ФАКТОРИАЛ

решение комбинаторных задач, полный граф, граф дерево, примеры

Понятие графа

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

Граф – это абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

Граф из 6 вершин и 7 ребёр.

Например:

Сколько различных трёхзначных чисел можно написать с помощью цифр 0 и 1?

Получаем 4 числа: 100,101,110 и 111

Полный граф в комбинаторике

Полный граф– это граф со всеми возможными ребрами.

С помощью полного графа удобно решать задачи полного перебора про «всех со всеми».

Например:

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

Изобразим полный граф с 5-ю вершинами и посчитаем количество ребёр.

N = 10. Значит, было сыграно 10 матчей.

Граф-дерево

Дерево – это граф без циклов, у которого между парами вершин имеется только одно ребро.

Граф-дерево с 9 узлами и 8 ребрами.

Из каждого узла выходит не более 2 ребер.

Такое дерево называют бинарным.

С помощью дерева удобно составлять упорядоченные комбинации элементов.

Например:

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

По правилу произведения число возможных вариантов: $3 \cdot 2 = 6$. Поскольку, порядок выбора неважен, остаётся $\frac{6}{2} = 3$ варианта. Построим граф:

3 варианта: 1) апельсиновый + яблочный, 2)апельсиновый + виноградный, 3) виноградный + яблочный.

Примеры

Пример 1. Вася, Петя, Коля и Толя хотят быть дежурными в столовой. Но можно выбрать только троих. Сколько вариантов выбора есть?

Построим полный граф.

Каждая тройка ребят соответствует треугольнику в этом графе.

Например, Вася образует три треугольника с оставшимися тремя ребятами:

$ \frac{3\cdot 2}{2} = 3$ - ВПК, ВТК и ВТП

Без Васи есть только один треугольник – ПКТ

Общее количество треугольников 3+1=4

Ответ: 4 варианта

Пример 2. Под рукой есть 6 видов овощей (капуста, морковь, лук, помидоры, огурцы и перец). Для салата нужно 3 вида овощей. Сколько всего различных салатов можно приготовить?

Построим полный граф.

Каждые три овоща на полном графе образуют треугольник.

Например, капуста образует треугольники с оставшимися 5 овощами. Таких треугольников $ \frac{5\cdot 4}{2} = 10$, где деление на 2 учитывает повторение ребра в каждой паре («лук-огурец» = «огурец-лук» и т.д.).

Количество треугольников, в которые не входит капуста: $ \frac{4\cdot 3}{2} = 6$

Количество треугольников, в которые не входят капуста и морковь: $ \frac{3\cdot 2}{2} = 3$

Количество треугольников, в которые не входят капуста, морковь и перец: $ \frac{2\cdot 1}{2} = 1$

Итого 10+6+3+1 = 20 различных треугольников.

Ответ: 20 салатов

Примечание: по расчетной формуле $C_6^3 = \frac{6\cdot 5 \cdot 4}{1\cdot 2 \cdot 3} = 20$ - ответ правильный.

Пример 3*. Сколько существует способов занять 1,2 и 3 места на чемпионате, в котором участвуют 11 команд? Решите задачу с помощью полного графа.

Если построить полный граф с 11-ю вершинами, каждая тройка команд в нём образует треугольник.

По аналогии с примерами 1 и 2, общее количество треугольников:

$$N = \left(\frac{10\cdot 9}{2} + \frac{9\cdot 8}{2}\right) + \left(\frac{8\cdot 7}{2} + \frac{7\cdot 6}{2}\right) + \left(\frac{6\cdot 5}{2} + \frac{5\cdot 4}{2}\right) + \left(\frac{4\cdot 3}{2} + \frac{3\cdot 2}{2}\right) + \frac{2\cdot 1}{2} = $$

$$ = 9 \frac{(10+8)}{2} + 7 \frac{(8+6)}{2} + 5 \frac{(6+4)}{2} + 3 \frac{(4+2)}{2} +1 = $$

$$ = 9^2+7^2+5^2+3^2+1 = 165 $$

Так, как порядок мест важен, в каждом треугольнике $– 3\cdot2 = 6$ вариантов распределения медалей.

По правилу произведения: $6\cdot165 = 990$ - общее количество способов.

Ответ: 990 вариантов

Примечание: по расчетной формуле $A_3^{11} = 11\cdot10\cdot9 = 990 $ - ответ правильный.

Пример 4. В столовой есть на выбор

Сколько вариантов обедов можно составить из этих блюд и каких?

По правилу произведения общее количество вариантов обедов: $2\cdot3\cdot2 = 12$

Построим дерево для перечисления вариантов:

Ответ: 12 вариантов

конспект открытого урока математики в 5 классе по теме "Дерево возможных вариантов" | Методическая разработка по алгебре (5 класс) по теме:

Конспект урока математики в 5 классе

Учитель математики МБОУ СОШ № 1 Слюнко О.В.

Тема: Дерево возможных вариантов.

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

Задачи:

·        развивать логическое мышление, память, внимание, умение сравнивать и обобщать;

·         воспитание интереса к предмету, культуры умственного труда.

 Оборудование:

ПК или ноутбук, проектор, экран.

Программное  обеспечение: ОС Windows, MS Power Point, презентация к уроку.

Ход урока

  1. Организационный момент, сообщение темы и цели урока.

(Слайд 1)

   

 II. Объяснение нового материала

        В старинных русских сказаниях повествуется, как богатырь или другой добрый молодец, доехав до распутья, читает на камне: “Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься”. А дальше уже говорится, как он выходит из того положения, в которое попал в результате выбора (Слайд 2)

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

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

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

Задачей комбинаторики можно считать задачу размещения объектов по специальным правилам и нахождение числа способов таких размещений.

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

Эти методы носят следующие названия: метод перебора, дерево возможных вариантов.

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

Решение. Для того чтобы не пропустить и не повторить ни одно из чисел, будем выписывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4 и, наконец, с цифры 7. Получаем следующий расклад.

 

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

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

Вернемся к задаче о составлении двузначных чисел из цифр 1, 4 и 7. Для ее решения можно построить специальную схему. (Слайд 4)

                                                                    

 

Первая цифра         1                               4                                   7

 

Вторая цифра 1         4       7         1          4           7            1        4            7

 

Число               11    14       17      41         44       47          71        74         77  

 

 Эта схема действительно похожа на дерево, правда, "вверх ногами" и без ствола. Знак “*” изображает корень дерева, ветви дерева – различные варианты решения. Чтобы получить двузначное число, надо сначала выбрать первую его цифру, а для нее есть три варианта: 1, 4 или 7. Поэтому из точки * проведены три отрезка и на концах поставлены цифры 1, 4 и 7.

Теперь надо выбрать вторую цифру, а для этого также есть три варианта: 1, 4 или 7. Поэтому от каждой первой цифры проведено по три отрезка, на концах которых снова записано 1, 4 или 7. Итак, получено всего 9 различных двузначных чисел. Других двузначных чисел из этих трех цифр составить невозможно.

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

Построим схему – дерево возможных вариантов:

                                 

 

 

 

 

¤

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

а

 

 

 

у

 

 

 

 

 

 

 

 

 

 

 

 

а

 

у

а

у

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

а

у

а

у

а

у

а

у

 

 

 

 

 

 

 

 

 

 

 ааа

аау

ауа

ауу

уаа

уау

ууа

ууу

 

 

                                                                       

Первая буква                          

 

 

Вторая буква

 

Третья буква

 

Слово (Слайд 6)

 

 

Задача 3. Служитель зоопарка должен дать зайцу два различных овоща. Сколькими различными способами он может это сделать, если у него есть морковь, свекла и капуста? (Слайд 7)

                                                                              ¤

 

Первый овощ                 М                                   С                                       К

 

Второй овощ        С                 К                    М               К                   М                С

                             МС               МК             СМ           СК               КМ                 КС

В итоге получаем 6 вариантов при учете, что мы делаем различие между МС и СМ и другими аналогичными парами. Но, если смотреть на то, что три из них эквивалентны трем другим парам (МС – СМ, МК – КМ, СК – КС), то получаем, что различных вариантов только три.

 

Задача 4.  На прямой отметили 4 точки: А, В,С,Д. Сколько получилось отрезков? (Слайд 8)

 

А                    В        С                Д

•                     •         •                  •                      

Построим дерево вариантов.

                                         *

         А                             В                     С

 

В      С     Д                  С     Д                  Д                                  

Отрезки АВ, АС, АД, ВС, ВД, СД

III. Закрепление нового материала

Решение задач

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

Ответ: 8

2. Андрей зашел в магазин, чтобы купить майки. В магазине оказались майки четырех цветов: белые, голубые, красные, черные.

а) Сколько вариантов покупки есть у Андрея, если он хочет купить две майки?

Подсказка: обозначьте цвета маек буквами Б, Г, К, Ч. Составьте дерево возможных вариантов

б) Сколько вариантов покупки есть у Андрея, если он хочет купить две майки разного цвета?

 IV. Итог урока.

Ответить на вопросы:

1). Что изучает комбинаторика?

2).Что такое дерево возможных вариантов?

V. Домашнее задание: придумать свою комбинаторную задачу и решить её.

 

Урок алгебры по теме: " Дерево возможных вариантов".

Урок алгебры по тем: "Дерево возможных вариантов".

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

Ход урока

I. Организационный момент.

II. Устная работа.

1. Три друга при встрече обменялись рукопожатиями. Сколько всего было сделано рукопожатий? (3.)

2. Есть помидоры, огурцы и лук. Сколько различных салатов можно приготовить, если в каждый из них должны входить в равных долях 2 различных вида овощей? (3.)

3. Перечислить все возможные способы разложения по двум вазам одного яблока и одной груши. (4.)

4. Сколькими способами Петя и Вова могут занять 2 места за одной двухместной партой? (2.)

5. Сколько подарочных наборов можно составить:

1) из одного предмета; (1.)

2) из двух предметов, если в наличии имеются одна ваза и одна ветка сирени? (3.)

III. Объяснение нового материала.

1. Чтобы подвести учащихся к «открытию» комбинаторного правила умножения, целесообразно начать объяснение нового материала с проверки решения задачи № 714 (домашнее задание) с выносом графа-дерева решения на доску:

Замечаем, что можно было решить эту задачу даже устно. Рассуждаем так. Первое блюдо можно выбрать двумя способами. Для каждого первого блюда можно подобрать второе четырьмя способами. Эти выборы независимы друг от друга, так как каждый осуществляется из своего множества вариантов. Значит, общее число вариантов обеда равно произведению 2 4, то есть 8.

В о п р о с у ч а щ и м с я: а если бы на обед было предложено выбрать еще одно третье блюдо из пяти: чай, кофе, сок, компот, кисель? Тогда для каждого варианта обеда мы могли бы предложить пять вариантов третьего блюда и получили бы 8 5 или 40 вариантов обеда из трех блюд.

2. Решая эту задачу, мы использовали так называемое комбинаторное правило умножения.

Формулируем его в общем виде, обращая особое внимание на условие его применения – выбор из независимых наборов вариантов:

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

3. П р и м е р 3 рассматриваем из учебника со с. 173.

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

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

1. Перечисление (полный перебор) вариантов.

2. Подсчет вариантов с помощью графов.

2.1. Полные графы.

2.2. Дерево возможных вариантов (граф-дерево).

На этом уроке добавляются еще два способа:

3. Составление таблицы возможных вариантов.

4. Непосредственное применение комбинаторного правила умножения.

Упражнения:

№ 727, № 728. На непосредственное применение комбинаторного правила умножения.

О б р а з е ц о ф о р м л е н и я решения задачи.

№ 728.

В задаче 4 последовательных выбора, каждый из своего множества вариантов. Общее количество различных карнавальных костюмов равно:

5 6 3 2 = 180.

О т в е т: 180 различных костюмов.

№ 722.

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

Составим таблицу возможных вариантов, отмечая крестиком игру между командами.

Команда

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

Можно просто посчитать количество крестиков, но это не рационально. Заметим, что количество игр представляет собой арифметическую прогрессию (ап), где а1 = 1, d = 1, п = 11. Значит, нам надо найти S11.

.

Это мы посчитали количество игр, проведенных командами на своем поле. Значит, столько же игр сыграно на поле противника. Итого – 132 игры.

№ 723.

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

I с п о с о б. Составление таблицы возможных вариантов.

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

(ап) – арифметическая прогрессия.

а1 = 1, d = 1, п = 7;

О т в е т: 28 рукопожатий.

II с п о с о б. Применение комбинаторного правила умножения.

Каждый человек пожимает руку семи оставшимся. Но так как порядок выбора не имеет значения (если Иванов пожимает руку Петрову, то одновременно и Петров пожимает руку Иванову), то общее число рукопожатий равно = 28.

О т в е т: 28 рукопожатий.

№ 725. Применение комбинаторного правила умножения.

Всего 10 цифр, каждая цифра комбинируется с оставшимися девятью (причем важен порядок, так как 2–3 и 3–2 разные коды) и с самой собой (возможен код 1–1, 3–3 и т. д.). Значит, вариантов 10 10 = 100. Так как в доме 96 квартир, то кодов хватит для всех.

V. Итоги урока.

В о п р о с ы у ч а щ и м с я:

– Какие способы решения комбинаторных задач вы знаете?

– Охарактеризуйте каждый способ решения.

– Сформулируйте комбинаторное правило умножения.

Домашняя работа: № 724, № 726, № 834, № 730 (а), № 731 (в).

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

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

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

Задача 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
Запишите все возможные варианты расписания пяти уроков на день из предметов: математика, русский язык, история, английский язык, физкультура, причем математика должна быть вторым уроком.

Решение. Построим дерево возможных вариантов, обозначив М - математика, Р - русский язык, И - история, А - английский язык, Ф - физкультура.

 Ответ: Всего 24 возможных варианта:

Р
М
И
Ф
А

Р
М
А 
И 
Ф

Р
М
А 
Ф
И

Р
М
Ф 
И 
А

Р
М
Ф 
А 
И

И
М
Р 
А 
Ф

И
М
Р 
Ф 
А

И
М
А 
Р 
Ф

И
М
А 
Ф 
Р

И
М
Ф 
Р 
А

И
М
Ф 
А 
Р

А
М
Р 
И 
Ф

А
М
Р 
Ф 
И

А
М
И 
Р 
Ф

А
М
И 
Ф 
Р

А
М
Ф 
Р 
И

А
М
Ф 
И 
Р

Ф
М
Р
И 
А

Ф
М
Р 
А 
И

Ф
М
И 
Р 
А

Ф
М
И 
А 
Р

Ф
М
А 
Р 
И

Ф
М
А 
И 
Р

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

Решение. Построим дерево возможных вариантов, обозначив Б - брюки, Д - джинсы, С - серая рубашка, Г - голубая рубашка, З - зеленая рубашка, Р - рубашка в клетку, Т - туфли, К - кроссовки.

 Ответ: а) 16 дней; б) 8 дней; в) 2 дня.

Составление таблиц

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

Задача 8. 
Сколько нечетных двузначных чисел можно составить из цифр 1, 3, 4, 6, 7, 8, 9?

Решение. Составим таблицу: слева первый столбец - первые цифры искомых чисел, вверху первая строка - вторые цифры.

 Ответ: 28.

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

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

Ответ: Все возможные варианты перечисляются в строках и столбцах таблицы.

Правило умножения

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

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

Решение.
Трусы могут быть белого, красного, синего или зеленого цвета, т.е. существует 4 варианта. Каждый из этих вариантов имеет 4 варианта цвета майки.

4 х 4 = 16.

Ответ: 16 команд.

Задача 11. 
6 учеников сдают зачет по математатике. Сколькими способами их можно расположить в списке?

Решение.
Первым в списке может оказаться любой из 6 учеников, 
вторым в списке может быть любой из оставшихся 5 учеников,
третьим - любой из оставшихся 4 учеников,
четвертым - любой из оставшихся 3 учеников,
пятым - любой из оставшихся 2 учеников,
шестым - последний 1 ученик.

6 х 5 х 4 х 3 х 2 х 1 = 720.

Ответ: 720 способами.

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

Решение.
Первой в двузначном числе может быть 5 цифр (цифра 0 не может быть первой в числе), второй в двузначном числе может быть 4 цифры (0, 2, 4, 6, т.к. число должно быть четным). 
5 х 4 = 20.

Ответ: 20 чисел.

python - сколько способов построить идеально сбалансированное дерево?

Переполнение стека
  1. Около
  2. Продукты
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии Программирование и связанные с ним технические возможности карьерного роста
  4. Талант Нанимайте технических специалистов и создайте
.Алгоритм

- Как можно построить суффиксное дерево за линейное время?

Переполнение стека
  1. Около
  2. Продукты
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии Программирование и связанные с ним технические возможности карьерного роста
  4. Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
  5. Реклама Обратитесь к разработчикам и технологам со всего мира
.

1.10. Деревья решений - документация scikit-learn 0.24.1

Деревья решений (DT) - это используемый непараметрический метод обучения с учителем для классификации и регрессии. Цель состоит в том, чтобы создать модель, которая предсказывает ценность целевая переменная путем изучения простых правил принятия решений, выведенных из данных функции. Дерево можно рассматривать как кусочно-постоянное приближение.

Например, в приведенном ниже примере деревья решений обучаются на основе данных аппроксимировать синусоидальную кривую с набором правил принятия решения «если-то-иначе».Глубже чем выше дерево, тем сложнее решающие правила и тем лучше модель.

1.10.1. Классификация

DecisionTreeClassifier - это класс, способный выполнять мультиклассы классификация по набору данных.

Как и другие классификаторы, DecisionTreeClassifier принимает на вход два массива: массив X, разреженный или плотный, формы (n_samples, n_features) , содержащий обучающие образцы и массив Y целочисленных значений, форма (n_samples,) , с метками классов для обучающих выборок:

 >>> из дерева импорта sklearn >>> X = [[0, 0], [1, 1]] >>> Y = [0, 1] >>> clf = дерево.DecisionTreeClassifier () >>> clf = clf.fit (X, Y) 

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

 >>> clf.predict ([[2., 2.]]) массив ([1]) 

В случае наличия нескольких классов с одинаковым и самым высоким вероятность, классификатор предскажет класс с наименьшим индексом среди этих классов.

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

 >>> clf.pred_proba ([[2., 2.]]) массив ([[0., 1.]]) 

DecisionTreeClassifier поддерживает как двоичные (где метки - это [-1, 1]) классификация и мультикласс (где метки [0,…, K-1]) классификация.

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

 >>> из sklearn.datasets import load_iris >>> из дерева импорта sklearn >>> X, y = load_iris (return_X_y = True) >>> clf = tree.DecisionTreeClassifier () 
.

Руководство по XGBoost для новичков. В этой статье будут деревья…. много… | Джордж Сейф

В этой статье будут деревья…. много деревьев

Деревьев… много из них

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

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

В этом посте мы рассмотрим основы библиотеки XGBoost. Мы начнем с практического объяснения того, как на самом деле работает повышение градиента, а затем рассмотрим пример Python, показывающий, как XGBoost делает это так быстро и легко.

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

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

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

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

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

Давайте начнем использовать это чудовище из библиотеки - XGBoost.

Первое, что мы хотим сделать, это установить библиотеку, что проще всего сделать через pip. Это также может быть безопаснее делать в виртуальной среде Python.

 pip install xgboost 

Настройка наших данных с помощью XGBoost

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

  из  sklearn  import  datasets 
import xgboost as xgb

iris = datasets.load_iris ()
X = iris.data
y = iris.target

Давайте настроим все наши данные . Мы начнем с создания разделения на поезд и тест, чтобы увидеть, насколько хорошо работает XGBoost. На этот раз мы будем делить 80% -20%.

 из sklearn.model_selection import train_test_split 

X_train, X_test, Y_train, Y_test = train_test_split (X, y, test_size = 0.2)

Чтобы XGBoost мог использовать наши данные, нам необходимо преобразовать их в определенный формат, который может обрабатывать XGBoost. Этот формат называется DMatrix . Очень просто однолинейно преобразовать массив данных в формат DMatrix:

 D_train = xgb.DMatrix (X_train, label = Y_train) 
D_test = xgb.DMatrix (X_test, label = Y_test)

Определение XGBoost model

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

 param = {
'eta': 0.3,
'max_depth': 3,
'objective': 'multi: softprob',
'num_class': 3}

шагов = 20 # Количество итераций обучения

Самыми простыми параметрами являются max_depth (максимальная глубина обучаемых деревьев решений), target (используемая функция потерь) и num_class (количество классов в наборе данных).Особого внимания требует алгоритм eta .

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

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

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

Обычно используются небольшие значения в диапазоне от 0,1 до 0,3. Меньший вес этих остатков по-прежнему поможет нам обучить мощную модель, но не позволит этой модели уйти в глубокую сложность, где с большей вероятностью произойдет переобучение.

Обучение и тестирование

Наконец-то мы можем обучить нашу модель аналогично тому, как мы это делаем с помощью Scikit Learn:

 model = xgb.train (param, D_train, steps) 

Теперь проведем оценку. Опять же, процесс очень похож на процесс обучения моделей в Scikit Learn:

  import  numpy  as  np 
from sklearn.metrics import precision_score, repl_score, precision_score

preds = model.predict (D_test)
best_preds = np.asarray ([np.argmax (line) для , строка в preds])

print ("Precision = {}". format (precision_score (Y_test, best_preds, average = 'macro')))
print ("Напомнить = {}".формат (оценка_позвала (Y_test, best_preds, average = 'macro')))
print ("Accuracy = {}". format (precision_score (Y_test, best_preds)))

Отлично!

Если вы выполнили все шаги до этого момента, вы должны получить точность не менее 90%!

Это почти подводит итог основам XGBoost. Но есть еще несколько интересных функций, которые помогут вам максимально эффективно использовать свои модели.

  из  sklearn.model_selection  import  GridSearchCV 

clf = xgb.XGBClassifier () Параметры
= {
"eta": [0,05, 0,10, 0,15 , 0.20, 0.25, 0.30],
«max_depth»: [3, 4, 5, 6, 8, 10, 12, 15],
«min_child_weight»: [1, 3, 5, 7],
«гамма» : [0.0, 0,1, 0,2, 0,3, 0,4],
«colsample_bytree»: [0,3, 0,4, 0,5, 0,7]
}

сетка = GridSearchCV (clf, параметры
, n_jobs = 4,
scoring = «neg_log_loss»,
cv = 3)

grid.fit (X_train, Y_train)

Делайте это только с большим набором данных, если у вас есть время убить - выполнение поиска по сетке по сути многократно тренирует ансамбль деревьев решений!

 model.dump_model ('dump.raw.txt') 

Вот и все!

.Алгоритм

- возможно ли построить дерево Фенвика за O (n)?

Переполнение стека
  1. Около
  2. Продукты
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии Программирование и связанные с ним технические возможности карьерного роста
.

Алгоритм Мо на деревьях [Учебное пособие]

Введение

Алгоритм Мо стал довольно популярным в последние несколько лет и теперь считается довольно стандартной техникой в ​​мире соревновательного программирования. В этом блоге будет описан метод обобщения алгоритма Мо для хранения информации о путях между узлами в дереве.

Предварительные требования

Алгоритм Мо - Если вы еще этого не знаете, прочтите эту замечательную статью, прежде чем продолжить этот блог.

Предварительный обход или порядок DFS дерева.

Проблема 1. Обработка запросов к поддереву

Рассмотрим следующую проблему. Вам будет предоставлено корневое дерево T из N узлов, где каждый узел связан со значением A [ узел ]. Вам необходимо обработать запросы Q , каждый из которых содержит одно целое число и . В каждом запросе вы должны указать количество различных значений в поддереве с корнем и . Другими словами, если вы сохраните все значения в поддереве с корнем и в наборе, каков будет размер этого набора?

Ограничения

1 ≤ N , Q ≤ 10 5

1 ≤ A [ node ] ≤ 10 9

Решение (я)

Выглядит довольно просто, не правда ли? т это? Один из простых способов решить эту проблему - превратить дерево в массив, выполнив обход Preorder, а затем реализовать алгоритм Мо.Поддерживайте таблицу поиска, которая поддерживает частоту каждого значения в текущем окне. Сохраняя это, ответ можно легко обновить. Сложность этого алгоритма будет

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

Задача 2 - Обработка запросов пути

Теперь давайте немного изменим Задачу 1. Вместо вычисления количества различных значений в поддереве вычислите количество различных значений в уникальном пути от u до v .Я рекомендую вам остановиться здесь и попробовать решить проблему на время. Ограничения этой проблемы те же, что и в задаче 1.

Проблема

Важной причиной того, почему проблема (1) сработала прекрасно, было то, что обход dfs-order сделал возможным представить любое поддерево как непрерывный диапазон в массиве. Таким образом, проблема была сведена к «поиску количества различных значений в подмассиве [ L , R ] из A, []. Обратите внимание, что это невозможно сделать для запросов пути, поскольку узлы, которые являются O Расстояние ( N, ) в дереве может составлять O (1) расстояние друг от друга в уплощенном дереве (представленное массивом A []).Так что сделать обычный dfs-порядок не получится.

Наблюдения

Пусть узел и имеет k дочерних узлов. Пронумеруем их как v 1 , v 2 ... v k . Пусть S ( u ) обозначает поддерево с корнем u .

Предположим, что dfs () посетит u ' s потомков в порядке v 1 , v 2 ... v k . Пусть x будет любым узлом в S ( v i ) и y будет любым узлом в S ( v j ) и пусть i < j . Обратите внимание, что dfs ( y ) будет вызываться только после завершения dfs ( x ) и исследования S ( x ). Таким образом, прежде чем мы вызовем dfs ( y ), мы должны войти и выйти из S ( x ).Мы воспользуемся этим, казалось бы, очевидным свойством dfs (), чтобы изменить наш существующий алгоритм и попытаться представить каждый запрос как непрерывный диапазон в плоском массиве.

Modified DFS-Order

Давайте изменим порядок dfs следующим образом. Для каждого узла и установите время начала и окончания S ( и ). Назовем их ST ( u ) и EN ( u ). Единственное изменение, которое вам нужно сделать, это то, что вы должны увеличивать глобальную переменную хронометража даже после завершения обхода некоторого поддерева ( EN ( u ) = ++ cur ).Короче говоря, мы будем поддерживать 2 значения для каждого узла и . Один будет обозначать время, когда вы вошли в S ( и ), а другой - время, когда вы вышли из S ( и ). Рассмотрим дерево на картинке. Ниже приведены значения узлов ST () и EN ().

ST (1) = 1 EN (1) = 18

ST (2) = 2 EN (2) = 11

ST (3) = 3 EN (3) = 6

ST (4) = 4 EN (4) = 5

ST (5) = 7 EN (5) = 10

ST (6) = 8 EN (6) = 9

ST (7) = 12 EN (7) = 17

ST (8) = 13 EN (8) = 14

ST (9) = 15 EN (9) = 16

A [] = {1, 2, 3, 4, 4, 3, 5, 6, 6, 5, 2, 7, 8, 8 , 9, 9, 7, 1}

Алгоритм

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

Пусть запрос будет ( u , v ). Мы попытаемся сопоставить каждый запрос с диапазоном в сглаженном массиве. Пусть ST ( u ) ≤ ST ( v ), где ST ( u ) обозначает время посещения узла u в T . Пусть P = LCA ( u , v ) обозначает наименьшего общего предка узлов u и v . Возможны два случая:

Случай 1: P = u

В этом случае диапазон нашего запроса будет [ ST ( u ), ST ( v )] .Почему это сработает?

Рассмотрим любой узел x , который не находится в пути ( u , v ).
Обратите внимание, что x встречается дважды или ноль раз в нашем указанном диапазоне запросов.
Следовательно, узлы, которые встречаются в этом диапазоне ровно один раз, - это именно те узлы, которые находятся на пути ( u , v )! (Попытайтесь убедить себя в том, почему это так: все из-за свойств dfs ().)

Это составляет суть нашего алгоритма.При реализации Mo, наша функция добавления / удаления должна проверять, сколько раз конкретный узел появляется в диапазоне. Если это происходит дважды (или ноль раз), то мы не принимаем во внимание это значение! Это можно легко реализовать, перемещая левый и правый указатели.

Случай 2: P u

В этом случае диапазон нашего запроса будет [ EN ( u ), ST ( v )] + [ ST ( P ), ST ( P )].

Здесь применима та же логика, что и в случае 1. Единственное отличие состоит в том, что нам нужно учитывать значение P , то есть LCA, отдельно, поскольку оно не будет учитываться в диапазоне запроса.

Та же проблема имеется на SPOJ.

Если вы не уверены в некоторых элементах этого алгоритма, взгляните на этот аккуратный код.

Заключение

Нам эффективно удалось свести проблему (2) к количеству различных значений в подмассиве путем тщательного учета.Теперь мы можем решить проблему. Этот модифицированный порядок DFS отлично работает для обработки запросов путей любого типа и хорошо работает с алгоритмом Мо. Мы можем использовать аналогичный подход для решения многих типов задач запроса пути.

Например, рассмотрим вопрос о нахождении количества инверсий в пути ( u , v ) в дереве T , где каждый узел имеет значение, связанное с ним. Теперь эту проблему можно решить, используя описанную выше технику и поддерживая BIT или дерево сегментов.

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

Примеры задач

1) Счет на дереве II
2) Фрэнк Синатра - Задача F
3) Вася и Медвежонок

Спасибо за внимание!

Оригинальное сообщение
Блог по теме

.

Смотрите также

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

Содержание, карта сайта.