Комбинаторика и программирование
презентация к уроку по информатике и икт на тему

Слайд 1

Комбинаторика и программирование Учебное пособие и приложения в виде программ Курилов И.А.

Слайд 2

Содержание: Что такое комбинаторика Факториал. Перестановки. Программы Размещение. Программы Сочетание. Программы Виды задач из ЕГЭ по информатике Вывод

Слайд 3

Что такое Комбинаторика Комбинаторика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества ( сочетания, перестановки, размещения и перечисления элементов ) и отношения на них (например, частичного порядка). Комбинаторика связана с математикой — алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например, в генетике, информатике, статистической физике ). Термин « комбинаторика » был введён в математический обиход Лейбницем , который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов (изучаем в информатике) .

Слайд 4

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

Слайд 5

Разновидности комбинаций Перестановка Размещение Сочетание

Слайд 6

Факториал Факториал. Перестановки Факториа́л числа n (лат. factorialis — действующий, производящий, умножающий; обозначается n ! , произносится эн факториа́л ) — произведение всех натуральных чисел от 1 до n включительно N!=1*2*3*4*….*N 5!=1*2*3*4*5=120 В комбинаторике факториал натурального числа n интерпретируется как количество перестановок - P ( упорядочиваний ) множества из n элементов. Например , для множества { A , B , C , D } из 4-х элементов существует 4! = 24 перестановки ABCD BACD CABD DABC ABDC BADC CADB DACB ACBD BCAD CBAD DBAC ACDB BCDA CBDA DBCA ADBC BDAC CDAB DCAB ADCB BDCA CDBA DCBA

Слайд 7

Пример 1: В семье – шесть человек, а за столом в кухне – шесть стульев. В семье решили каждый вечер, ужиная, рассаживаться на эти шесть стульев по- новому. Сколько дней члены семьи смогут делать это без повторений? Для удобства будем считать, что семья (бабушка, дедушка, мама, папа, дочь, сын) будет рассаживаться поочередно. У бабушки – 6 вариантов выбора стульев. У дедушки – 5 вариантов выбора стульев. У мамы – 4 варианта выбора стульев. У папы – 3 варианта выбора стульев. У дочери – 2 варианта выбора стульев. У сына – 1 вариант выбора стульев. По правилу умножения: 6×5×4×3×2×1 = 720 (дней).

Слайд 8

Пример 2: В 10 классе в среду семь уроков: алгебра, геометрия, литература, русский язык, английский язык, биология и физкультура. Сколько можно составить вариантов расписания на среду? Для алгебры – 7 вариантов расположения в расписании Для геометрии – 6 вариантов Для литературы – 5 вариантов и т.д. По правилу умножения получаем = 7! = 5040

Слайд 9

Пример 3:Сколько различных четырёхзначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 2, 4, 6? Решение. Из цифр 0, 2, 4, 6 можно получить Р4 перестановок. Из этого числа надо исключить те перестановки, которые начинаются с 0, так как натуральное число не может начинаться с цифры 0. Число таких перестановок равно Р3. Значит, искомое число четырёхзначных чисел (без повторения цифр), которые можно составить из цифр 0, 2, 4, 6, равно Р4 - Р3 = 4! – 3! = 24 – 6 = 18.

Слайд 10

Факториал в программировании Нахождение факториала на языке Pascal Var factorial : longint ; n, i: byte ; begin write (' n = '); readln (n); factorial := 1; for i := 2 to n do factorial := factorial * i; writeln (' n! = ', factorial ); end .

Слайд 11

Нахождения факториала с помощью рекурсивной функции на языке Pascal . var n : integer ; function fact ( n :integer ): integer ; Begin if n = 1 then fact := 1 else fact := fact (n - 1) * n; end ; begin write (' vvedi chislo : '); readln ( n ); o := fact(n); writeln (' otvet : ', o); end .

Слайд 12

Программа вывода перестановок (уже для 4 элементов выглядит неэффективно) const n=4; a:array[1..n] of integer =(1,2,3,4); var i,j,k,l:integer ; begin writeln (' Перестановки:'); for i:=1 to n do for j:=1 to n do for k:=1 to n do for l:=1 to n do if ( i <>j) and ( i <>k)and ( i <>l)and (j<>k)and (j<>l)and (k<>l) then write(a[ i ],a[j],a[k],a[l],' '); end.

Слайд 13

Размещение Комбинаторике размещением (из n по k ) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов. Пример: 1,3,2,5 — это 4-элементное размещение из 6-элементного множества 1,2,3,4,5,6 Пример: некоторые размещения элементов множества {1,2,3,4,5,6} по 2: 1,2 ; 1,3 ; 1,4 ; 1,5 … 2,1 ... 2,3 ... 2,4 … 2,6… В отличие от сочетаний ( смотрите далее ), размещения учитывают порядок следования предметов . Так, например, наборы 2,1,3 и 3,2,1 являются различными, хотя состоят из одних и тех же элементов 1,2,3 (то есть совпадают как сочетания).

Слайд 14

Задачи Пример 1: Боря , Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт) I способ - P 36 =34*35*36=42840 способами можно раздать 3 карты игрокам . I I способ – по формуле размещений A 36 = m!/(m-n)! = 36!/33!= 42840 II I способ * - C 36 = m!/(m-n)!*n! = 36!/ 33!*3!=7140 способами можно извлечь 3 карты из колоды Теперь давайте рассмотрим, какую-нибудь одну из семи тысяч ста сорока комбинаций, например: король пик, 9 червей , 7 червей. Выражаясь комбинаторной терминологией, эти 3 карты можно «переставить» между Борей, Димой и Володей P 3 =3!=6 способами : КП , 9Ч, 7Ч; КП, 7Ч, 9Ч; 9Ч, КП, 7Ч; 9Ч, 7Ч, КП; 7Ч, КП, 9Ч; 7Ч, 9Ч, КП. И аналогичный факт справедлив для любого уникального набора из трёх карт. А таких наборов, не забываем, мы насчитали 7140 . Не нужно быть профессором, чтобы понять, что найденное количество комбинаций (*сочетаний) следует умножить на шесть: 7140*6=42840 Ответ:42840 способов ЭТОТ СПОСОБ через сочетания ДОСТАТОЧНО ЕМКИЙ! Про сочетания смотрите дальше.

Слайд 15

Задачи Пример 2: Сколько существует вариантов распределения трех призовых мест, если в розыгрыше участвуют 7 команд? I способ - P 36 =7*6*5=210 вариантов тройки лучших команд . I I способ – по формуле размещений A 36 = m!/(m-n)! = 7 !/4!= 210 2 способ сводится к первому! 7!/3!= 7*6*5*4*3*2*1/4*3*2*1=7*6*5

Слайд 16

Паскаль примеры Число размещений из n элементов по k элементов var i,r,k,n:integer ; begin writeln ('k of n'); readln ( k,n ); r:=1; for i:=1 to k do r:=r*(n-i+1); writeln (r); end. Можно также с использованием специальной формулы размещений.

Слайд 17

Фрагмент программы вывода размещений (1 : С повторениями*, 2: Без повторений) 1: for i:=1 to n do for j:=1 to n do begin write(a[ i ],a[j],' '); writeln (b[ i ],b[j]); end; 2: for i:=1 to n do for j:=1 to n do if i <>j then begin write(a[ i ],a[j],' '); writeln (b[ i ],b[j]); end; Пояснения*: Мы рассматривали задачи согласно обычной теории - размещения без повторений, так как имеются ввиду задачи с размещением групп людей … Но имеет место и задачи переборы комбинаций, например, цифр из 2, … в этом случае назовем такие размещения с повторениями! Полный листинг

Слайд 18

Сочетание Сочетание В комбинаторике сочетанием из n по k называется набор {k} элементов, выбранных из данного множества, содержащего {n} различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. Так, например, наборы (3-элементные сочетания, подмножества, {k=3}) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} ({n=6}) являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}. В общем случае число, показывающее, сколькими способами можно выбрать {k} элементов из множества, содержащего {n} различных элементов, стоит на пересечении {k}-й диагонали и {n}-й строки треугольника Паскаля.

Слайд 19

Задачи Здесь, конечно же, не нужно ворочать огромные числа. 11 !=39916800 15!=1307674368000 В похожей ситуации я советую использовать следующий приём: в знаменателе выбираем наибольший факториал (в данном случае 11! ) и сокращаем на него дробь. Для этого числитель следует представить в виде 15!=11!*12*13*14*15 С 36 = m!/(m-n)!*n! = 11 !*12*13*14*15/11!*4!=12*13*14*15/24=1365 Ответ :1365 способов Пример 2: Чемпионат России по шахматам проводится в один круг. Сколько играется партий, если участвуют 18 шахматистов? Первый способ . Каждый участник должен сыграть 17 партий, в каждой партии играют двое. Поэтому всего партий 18·17 : 2 = 153. Второй способ* . В каждой партии разыгрывается одно очко. Предположим, что все партии закончатся вничью. Тогда каждый участник наберет 17 : 2 = 8,5 очков. А всего очков, а значит, и партий – 18·8,5 = 153. / Пример 1: В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?

Слайд 20

Подсчет сочЕтаниЙ Число размещений из n элементов по k элементов var i,s:longint ; n,k:integer ; begin writeln ('k of n'); readln ( k,n ); s:=1; if k=0 then s:=1 else for i :=1 to n-k do s:=s*( k+i ) div i ; writeln (s); end. Можно также с использованием специальной формулы сочетаний.

Слайд 21

Фрагмент программы вывода сочетаний (1 : С повторениями*, 2: Без повторений) 1 : for i:=1 to n do for j:= i to n do begin write(a[ i ],a[j],' '); writeln (b[ i ],b[j]); end; 2 : for i:=1 to n-1 do for j:=i+1 to n do begin write(a[ i ],a[j],' '); writeln (b[ i ],b[j]); end; Пояснения*: (Аналогично размещениям) Мы рассматривали задачи согласно обычной теории - сочетания без повторений, так как имеются ввиду задачи с размещением групп людей … Но имеет место и задачи переборы комбинаций, например, цифр из 2, … в этом случае назовем такие сочетания с повторениями! Полный листинг

Слайд 22

Полный листинг программы «Размещения и сочетания» program kombin ; const n=4; var a:array[1..n] of integer; b:array[1..n] of string; i,j:integer ; q,w:byte ; begin for i:=1 to n do a[i]:=i-1; w:=64; for i:=1 to n do b[i]:=chr(w+i); writeln ('Выберите, что хотите получить:'); writeln ('1: размещения с повторениями'); writeln ('2: размещения без повторений'); writeln ('3: сочетания с повторениями'); writeln ('4: сочетания без повторений'); readln (q); case q of 1:for i:=1 to n do for j:=1 to n do begin write(a[ i ],a[j],' '); writeln (b[ i ],b[j]); end; 2: for i:=1 to n do for j:=1 to n do if i <>j then begin write(a[ i ],a[j],' '); writeln (b[ i ],b[j]); end; 3: for i:=1 to n do for j:= i to n do begin write(a[ i ],a[j],' '); writeln (b[ i ],b[j]); end; 4: for i:=1 to n-1 do for j:=i+1 to n do begin write(a[ i ],a[j],' '); writeln (b[ i ],b[j]); end; end; end.

Слайд 23

Задачи из ЕГЭ по Информатики (№10) 1.Все 5-буквенные слова, составленные из букв В, Е, К, Н, О, записаны в алфавитном порядке и пронумерованы . Вот начало списка : 1. ВВВВВ 2. ВВВВЕ 3. ВВВВК 4. ВВВВН... Заменим буквы В, Е, К, Н, О на 0, 1, 2, 3, 4 соответственно (для них порядок очевиден — по возрастанию ). Выпишем начало списка , заменив буквы на цифры: 1. 00000 2. 00001 3. 00002 4. 00003 Полученная запись есть числа, записанные в пятеричной системе счисления в порядке возрастания . Первое слово, начинающееся с "О" — 40000 переведём его в десятичную : 4 · 5^4 + 0 · 5^3 + 0 · 5^2 + 0 · 5^1 = 2500. Не забу­дем о том, что есть слово номер 1, записывающееся как 0, а значит , 2500 — число, соответствующее номеру 2501. Ответ: 2501.

Слайд 24

Задачи из ЕГЭ по Информатики (№10) 2.Некоторый алфавит содержит 4 различных символа. Сколько трех­буквенных слов можно составить из символов этого алфавита, если символы в слове могут по­вторяться? Пояснение: Если в алфавите символов, то количество всех возможных «слов» (сооб­щений) длиной равно: N=3, M=4. Следовательно, Ответ: 64

Слайд 25

Задачи из ЕГЭ по Информатики (№10) 3.Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A? 1.Рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А: АА*** А*А** А**А* А***А Здесь звёздочка обозначает любой символ из набора { C , G , T }, то есть один из трёх символов. Итак, равно 3 3 = 27 Всего 4 шаблона, они дают 4 · 27 = 108 комбинаций 2. Теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три: *АА** *А*А* *А**А они дают 3 · 27 = 81 комбинацию 3.Два шаблона, где первая по счёту буква А стоит на третьей позиции: **АА* **А*А они дают 2 · 27 = 54 комбинации 4.Один шаблон, где сочетание АА стоит в конце ***АА они дают 27 комбинаций 5.Всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций!

Слайд 26

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