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 элементов с повторениями.

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


 

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

68048. Регіональний конкурс «Найкращий відгук на сучасну дитячу прозу» 36.5 KB
  Матеріал до підготовки: мікрофон музика книжкові виставки: Книги які знають усе Сучасна дитяча проза формуляри читачів 4 та 5 класів. Щоб дізнаємося які книги подобаються нашим конкурсантам ми заглянемо у їхні формуляри. Запитання для читачів: Яка книга залишила у твоїй памяті...
68049. Виховний захід: «Інформація» 173 KB
  Після того як перший учасник закінчив розповідь він займає місце в аудиторії слухачів. Визначте хто яке місце зайняв якщо відомо що Галя зайняла друге місце Наталя хоч і не стала переможцем але в призери попала а Віра програла Ані. Аня Віра Галя Наталя 1 місце 2 місце 3 місце...
68050. Конкурс кмітливих та винахідливих «Мій розпорядок дня» 36 KB
  - Heute haben wir Wiederholungsstunde zum Thema «Unser Tageslauf». - Sagt, an welchem Thema haben wir gearbeitet? - Woruber haben wir zu diesem Thema gesprochen? - An welchem grammatischen Stoff haben wir in dieserZeit gearbeitet (Perfekt)?
68051. Конкурс юних філологів (сценарій виховного заходу для учнів 8 класу) 54.5 KB
  Наша мова найважливіша частина не лишень нашої поведінки а й нашої особистості нашої душі розуму Сьогодні тут зібралися справжні українці шанувальники мови знавці рідного слова. Сьогодні я пропоную вам демонструючи свої знання з мови ще й зібрати з нашого незвичайного фруктового дерева...
68052. “Птахи - наші вірні друзі.” Зустрічаємо птахів 77.5 KB
  Розширити та поглибити знання учнів про світ птахів вчити дітей вдумливо дбайливо ставитися до навколишнього середовища замислюватися над наслідками своїх дій. Виховувати любов до природи бажання оберігати птахів інтерес до усної народної творчості.
68053. Конспект виховної години на тему: «Безсердечна людина» 29 KB
  Дякуємо за гарну інсценізацію хто скаже як можна назвати головного героя одним словом А що означає безсердечна людина Назвіть вчинки які може зробити безсердечна людина. Діти а зараз давайте дамо характеристику слову безсердечна яка це людина запис на дошці зла погана чорна...
68054. Утворення трицифрових чисел. Читання чисел, записаних у нумераційній таблиці. Додавання чисел різних розрядів. Задача на спільну роботу 74.5 KB
  Мета: розвивати вміння розв’язувати задачі на спільну роботу; розвивати логічне мислення; розвивати соціальну компетентність школярів; закріплювати знання натурального ряду чисел у межах 1000 і розрядний склад трицифрових чисел; виховувати інтереси до знань і бажання пізнавати таємниці математики...