Без темы
<<  Дистанционная Акмуллинская олимпиада по музыке для одаренных детей Дугина Ирина Радиковна  >>
Дистанционная подготовка к Всероссийской олимпиаде по информатике
Дистанционная подготовка к Всероссийской олимпиаде по информатике
Занятие 8. Алгоритмы комбинаторики
Занятие 8. Алгоритмы комбинаторики
Правило суммы
Правило суммы
Правило произведения
Правило произведения
Правило произведения
Правило произведения
Перестановки (без повторений)
Перестановки (без повторений)
Размещения (без повторений) из n по k
Размещения (без повторений) из n по k
Сочетания (без повторений) из n по k
Сочетания (без повторений) из n по k
Перестановки с повторениями
Перестановки с повторениями
Размещения с повторениями
Размещения с повторениями
Сочетания с повторениями
Сочетания с повторениями
Биноминальные коэффициенты
Биноминальные коэффициенты
Счастливые билеты
Счастливые билеты

Презентация: «Дистанционная подготовка к Всероссийской олимпиаде по информатике». Автор: Юрий. Файл: «Дистанционная подготовка к Всероссийской олимпиаде по информатике.ppt». Размер zip-архива: 79 КБ.

Дистанционная подготовка к Всероссийской олимпиаде по информатике

содержание презентации «Дистанционная подготовка к Всероссийской олимпиаде по информатике.ppt»
СлайдТекст
1 Дистанционная подготовка к Всероссийской олимпиаде по информатике

Дистанционная подготовка к Всероссийской олимпиаде по информатике

Преподаватели: к.ф.-м.н., заведующий кафедрой «САПР» ДВГУПС Пономарчук Юлия Викторовна E-mail: yulia.ponomarchuk@gmail.com преподаватель кафедры «САПР» ДВГУПС Сухобок Юрий Андреевич E-mail: khvyus@gmail.com

2 Занятие 8. Алгоритмы комбинаторики

Занятие 8. Алгоритмы комбинаторики

3 Правило суммы

Правило суммы

Допустим, существует некоторое количество различных способов выполнить заданное действие: выбрать книгу с полки; ввести пароль; вытащить шар заданного цвета из урны и т.п. Пусть все способы выполнить действия делятся на n групп так, что каждый конкретный способ относится только к одной из этих групп. Пусть каждая группа содержит k1, k2, …, kn способов. Тогда общее количество способов выполнить действие равно K=k1+k2+…+kn. При этом неважно, каким именно из K способов будет выполнено действие. Пример. Есть 2 зеленые и 3 красные чашки. Сколькими способами можно выбрать чашку (или зеленую, или красную)? Решение. Можно выбрать любую зеленую или любую красную чашку. Поэтому, существует 2+3 = 5 способов выбора.

4 Правило произведения

Правило произведения

Обычно правило рассматривается на примере двух эквивалентных задач. Задача 1. Пусть сложное действие состоит из n последовательных этапов, и первый этап можно выполнить любым из k1 способов, второй – любым из k2 способов независимо от способов выполнения первого этапа и т.д. Тогда число способов выполнить действие в целом равно K= k1*k2*…*kn. Задача 2. Пусть выбирается последовательность из n объектов разного рода, причем в качестве первого можно взять любой из k1 объектов одного класса, в качестве второго – любой из k2 объектов другого класса независимо от выбора первого объекта и т.д. Тогда всю последовательность можно собрать k1*k2*…*kn способами. Т.е. все n объектов выбираются одновременно, но принадлежат разным классам.

5 Правило произведения

Правило произведения

Пример 1. Есть две тарелки и две ложки. Сколько наборов можно собрать, состоящих из тарелки и ложки? Решение. Можно выбрать любую из двух тарелок и любую из трех ложек. Поэтому в целом можно собрать 2*3 = 6 различных наборов. Пример 2. Из города A в город D можно проехать либо через город B, либо через город C. Проехать из A в B можно k1 способами, из A в C – k2 способами, из B в D – k3 способами, из C в D – k4 способами. Сколько существует способов проехать из A в D? Решение. Т.к. все пути проходят либо через B, либо через C используем правило суммы. По правилу произведения есть k1*k3 различных путей из A в D через B и k2*k4 различных путей из B в D. Тогда существует K=k1*k3+k2*k4 маршрутов.

6 Перестановки (без повторений)

Перестановки (без повторений)

Перестановки (без повторений) – это последовательности элементов (объектов), принадлежащих одному и тому же множеству, причем они отличаются расположением элементов. Все элементы в перестановках различны – не повторяются. Пример. Допустим, дано множество {1, 2, 3}. Тогда перестановки из трех элементов можно записать в лексикографическом порядке: <1 2 3>, <1 3 2>, <2 1 3>, <2 3 1>, <3 1 2>, <3 2 1> Количество перестановок n элементов множества равно: Pn = 1*2*3*…*n = n!

7 Размещения (без повторений) из n по k

Размещения (без повторений) из n по k

Размещения k объектов (элементов), принадлежащих множеству из n элементов, без повторений – последовательности, образованные k попарно различными элементами из n возможных. Пример. Допустим, дано множество {1, 2, 3}. Размещения из 3 по 2 (состоят из двух элементов, выбранных из множества из трех элементов): <1 2>, <1 3>, <2 1>, <2 3>, <3 1>, <3 2> Количество размещений из n по k:

Программировать лучше по этой формуле при n>>k

8 Сочетания (без повторений) из n по k

Сочетания (без повторений) из n по k

Сочетания (без повторений) из n по k – это подмножества, образованные k элементами из n возможных (т.е. в отличие от размещений, при рассмотрении сочетаний не важен порядок следования элементов) Пример. Допустим, дано множество {1, 2, 3}. Сочетания из 2 по 3: <1 2>=<2 1> <1 3> <2 3> Количество сочетаний (см. биномиальные коэффициенты): При программировании лучше вычислять так:

9 Перестановки с повторениями

Перестановки с повторениями

(n, m) состав - последовательность чисел (k1, k2, …, kn), в которой k1, k2, …, kn ? 0, k1+k2+…+kn = m. Перестановки с повторениями состава (k1, k2, …, kn) – последовательности длины k1+k2+…+kn, которые содержат k1 элементов первого типа, k2 – второго, …, kn – n-го типа и отличаются порядком следования элементов. Количество перестановок с повторениями состава (k1, k2, …, kn): Пример: сколько различных слов можно образовать, переставляя буквы слова АБРАКАДАБРА? Решение. В последовательности из 11 букв имеем 5 букв А, 2 буквы Б, 2 – Р и по одной букве К, Д. Тогда число слов, которые можно образовать, равно 11!/(5!*2!*2!*1!*1!) = 83160

10 Размещения с повторениями

Размещения с повторениями

Размещения с повторениями из n по m – последовательности длины m, в которых n возможных элементов могут повторяться. Размещения элементов множества {1, 2, 3} по 2: <1 1>, <1 2>, <1 3>, <2 1>, <2 2>, <2 3>, <3 1>, <3 2>, <3 3> Количество размещений: nm

11 Сочетания с повторениями

Сочетания с повторениями

Сочетания с повторениями из n (типов) по m (элементов) – множество, содержащее m элементов, каждый из которых имеет один из типов t1, t2, …, tn. Количество различных сочетаний с повторениями: Пример. Есть неограниченный запас шариков, отличающихся только цветом – белым или черным. Сколько наборов цветов можно получить, взяв любые три шарика? Решение. Четыре набора: {Б Б Б}, {Б Б Ч}, {Б Ч Ч}, {Ч Ч Ч}

12 Биноминальные коэффициенты

Биноминальные коэффициенты

Бином Ньютона: Треугольник Паскаля:

13 Счастливые билеты

Счастливые билеты

В городе Глупове общепринята p-ричная система счисления (вместо десятичной), а номера троллейбусных билетов состоят из 2k разрядов (каждый разряд – одна p-ричная цифра). Билет считается счастливым, если сумма первых k разрядов равна сумме последних k разрядов. Даны значения p и k. Рассчитайте количество счастливых билетов.

«Дистанционная подготовка к Всероссийской олимпиаде по информатике»
http://900igr.net/prezentacija/fizkultura/distantsionnaja-podgotovka-k-vserossijskoj-olimpiade-po-informatike-261251.html
cсылка на страницу

Без темы

165 презентаций
Урок

Физкультура

35 тем
Слайды
900igr.net > Презентации по физкультуре > Без темы > Дистанционная подготовка к Всероссийской олимпиаде по информатике