34664

Основы комбинаторики

Реферат

Информатика, кибернетика и программирование

При выборе m элементов из n различных элементов принято говорить что они образуют соединение из n элементов по m. Перестановка Соединение каждое из которых содержит n различных элементов взятых в определенном порядке называются перестановками из n элементов n=m. Сочетание Соединения отличающиеся друг от друга каждое из которых содержит m элементов взятых из n элементов называется сочетанием из n элементов по m n m. Размещение с повторением Размещение из n элементов в каждое из которых входит m элементов причем один и тот же...

Русский

2013-09-08

56 KB

6 чел.

исциплина «Основы алгоритмизации и программирование»  Основы комбинаторики

Основы комбинаторики.

[1] КОМБИНАТОРИКА

[2] Перестановка

[3] Сочетание

[4] Размещение с повторением

[5] Размещение

[6] Перестановка с повторением

КОМБИНАТОРИКА

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

При выборе m элементов из n различных элементов принято говорить, что они образуют соединение из n элементов по m.

Перестановка

Соединение, каждое из которых содержит n различных элементов, взятых в определенном порядке, называются перестановками из n элементов (n=m).

Пример: a, b, c  abc, acb, bac, bca, cab, cba  Количество перестановок: n!

const n=3;

var

 p,r:array[0..n] of integer;

 i,j,k,d,l: integer;

Begin

 for i:=0 to n do p[i]:=i;

 while p[0]=0 do

 begin

   for i:=1 to n do write(p[i]:3);

   writeln;

   l:=l+1;

    j:=N;

   while p[j-1]>p[j] do j:=j-1;

   k:=N;

   while p[j-1]>p[k] do k:=k-1;

   d:=p[j-1];

   p[j-1]:=p[k];

   p[k]:=d;

   for i:=j to n do r[i]:=p[N-(i-j)];

   for i:=j to n do p[i]:=r[i];

 end;

 writeln(l);

End.

Сочетание

 Соединения, отличающиеся друг от друга, каждое из которых содержит m элементов, взятых из n элементов, называется сочетанием из n элементов по m (n>m).

Пример: a, b, c  ab, ac, bc  Количество сочетаний  n! / (m! (n-m)!)

var

 b:array[1..100] of integer;

 i,j,n,m,k : integer;

Begin

 read(n,m);

 for i:=1 to m do b[i]:=i;

 repeat

   for i:=1 to m do write(b[i]:3);

    writeln;

   j:=m;

   while (j>0) and (b[j]>=n-m+j) do j:=j-1;

   if j<>0 then

   begin

     b[j]:=b[j]+1;

     for k:=j+1 to m do b[k]:=b[k-1]+1;

   end;

 until j=0;

End.

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

Размещение из n элементов, в каждое из которых входит m элементов, причем один и тот же элемент может повторяться в каждом размещении любое число раз, но не более чем m, называются размещениями из n  элементов по m  с повторением.

Пример: a, b, c        aaa, aab, aba, abb, baa, bab, bba, bbb    Количество размещений nm 

var

 a:array[0..100] of integer;

 i,n,m : integer;

Begin

 read(n,m);

 for i:=0 to m do a[i]:=0;

 while a[m]=0 do

 begin

    i:=0;

   a[0]:=a[0]+1;

   while (a[i]=n) and (a[m]=0) do

   begin

     a[i]:=0;

     a[i+1]:=a[i+1]+1;

     i:=i+1;

   end;

   for i:=m-1 downto 0 do write(a[i]:2);

   writeln;

 end;

End.

Размещение

Соединения, отличающиеся друг от друга составом элементов или их порядком, каждое из которых содержит m (m<n) элементов, взятых из n различных элементов, размещением из n элементов по m.

Пример:  a, b, c  ab, ba, ac, ca, bc, cb  Количество размещений  n! / (n-m)!

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

Перестановка из n  предметов, в каждую из которых входят n1 одинаковых предметов, называют перестановками из n элементов с повторениями.

Для получения всех перестановок с повторениями можно воспользоваться алгоритмом из пункта Перестановка, заменив в нем знаки > на знаки >=.


 

А также другие работы, которые могут Вас заинтересовать

48238. Л.Д. Малевич. Українська мова професійного спілкування 282.5 KB
  Стилі і норми української літературної мови в професійному спілкуванні Мовне законодавство в Україні Природа і функції мови. Місце української мови серед мов світу. Правовий статус української мови.
48239. УКРАЇНСЬКА МОВА ЗА ПРОФЕСІЙНИМ СПРЯМУВАННЯМ 888.5 KB
  Усне ділове спілкування. Етика ділового спілкування її предмет та завдання. Структура ділового спілкування. Мовленнєвий етикет Правила усного спілкування фахівця зустрічі переговори телефонне спілкування.
48240. ІСТОРІЯ УКРАЇНИ 430.5 KB
  Програма з курсу Історія України Укл. ВСТУПНЕ СЛОВО Пропоновані матеріали підготовлено з урахуванням проекту навчальної програми з курсу Історія України для вищих навчальних закладів освіти і передбачають розвязання таких завдань: а використання останніх досягнень світової і вітчизняної історичної науки в процесі викладання історії України; б постійне підвищення і вдосконалення наукового і виховного рівня викладання; в забезпечення реалізації в ході навчання принципів історизму та обєктивності в оцінці конкретних подій і явищ; г...
48241. УКРАЇНСЬКА КУЛЬТУРА 102.5 KB
  Ульяновський Українська наукова і культурницька еміграція у ЧехоСловаччині між двома світовими війнами Українська культура: розвиток ідеї та історія книги Автори Української культури: Дмитро Антонович Василь Біднов Дмитро Дорошенко Олександр Лотоцький Симон Наріжний Степан Сірополко Володимир Січинський Дмитро Чижевський Андрій Яковлів Українська культура: Лекції за редакцією Дмитра Антоновича Упор. Ця книжка унікальна спроба цілісного дослідження феномена української культури з найдавніших до...
48242. УКРАЇНСЬКА ЛІТЕРАТУРА ХХ СТОЛІТТЯ 1.33 MB
  Франка нова генерацiя прагнула цiлком модерним європейським способом зобразити своєрiднiсть життя українського народу. Психологiзм змалювання внутрiшнього життя особистостi як важливого моменту образу свiту. Поставши на грунтi класичного реалiзму але не сприйнявши лiнiйно мiметичного принципу зображення життя у формах життя неореалiсти визначали свiй концептуальний принцип мiж документальною достовiрнiстю фiлософськоаналiтичним заглибленням у дiйснiсть та лiричною стихiєю; подеколи промовиста деталь реалiстичного письма сюжет....
48243. УКРАЇНСЬКА МОВА 1.04 MB
  Поняття літературної мови. Тенденції розвитку української літературної мови на сучасному етапі. Функції мови. Культура мови.
48244. Текстове оформлення довідково-інформаційних документів 345.5 KB
  СТАТУТ обєднання співвласників багатоквартирного будинку КРИСТАЛ м. Обєднання співвласників багатоквартирного будинку Кристал надалі Обєднання створюється на підставі Закону України Про обєднання співвласників багатоквартирного будинку від 29 листопада 2001 р. як організаційноправова форма обєднання власників житлових і нежитлових приміщень для сумісного управління єдиним комплексом нерухомого майна й забезпечення...
48245. Українська мова за професійним спрямуванням. Класифікація стилів сучасної української мови 145 KB
  Місце української мови серед інших мов світу. Норми літературної мови. Функціональні стилі сучасної української літературної мови. Місце української мови серед інших мов світу Мова це величне надбання людства.
48246. Специфіка ділової української мови (офіційно-ділового стилю) 57.91 KB
  Офіційно-діловий стиль є одним із соціально значущих різновидів літературної мови, оскільки відіграє важливу роль у державно-політичному, громадському й суспільно-виробничому житті країни.