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

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


 

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

60243. У світі пірамід 75 KB
  Перше чудо світу єгипетські піраміди. Але навіть тепер піраміди справляють таке могутнє враження що нам важко висловити почуття які охоплюють нас коли ми споглядаємо ці камяні геометричні споруди над Нілом.
60244. ДАНИНА ПОДВИГУ 302.5 KB
  Сьогодні визначається знаменна дата 70-а річниця боїв за Дніпро і визволення столиці України Києва від гітлерівських загарбників. Серед видатних перемог Великої Вітчизняної війни операція по визволенню Києва...
60245. Виховний захід: Поле чудес 187 KB
  І завданням кожного з нас є турбота про світ природи що нас оточує та охорона тварин рослин та природних ресурсів. Виходячи з цього і враховуючи притаманні державі геополітичні географічні демографічні соціально-економічні та екологічні особливості цілями...
60247. Классный час по профориентации «Дорога в Завтра» 54.5 KB
  Повышение мотивационно-ценностной готовности к зрелому выбору: сформированность у ученика самооценки адекватной личным способностям и возможностям получить желаемое образование наличие ценностных ориентаций и индивидуально...
60248. Літературні розумники 52.5 KB
  Різдвяна пісня у прозі 8. Вогонь Прометея VІ Темна конячка поняття у скринці Теорія літератури Канцона пісня про кохання Сирвента пісня про політику суспільне життя Пастореле пісня про зустріч лицаря і пастушки Рубаї чотиривірш де римується...
60249. СИЛЬНІ ДУХОМ 1.14 MB
  Мета: виховувати позитивне ставлення до людей з обмеженими можливостями; ознайомити з організаціями, які піклуються про інвалідів; розкрити проблеми людей–інвалідів та засоби їх вирішення...
60250. Путешествие в страну сказок 52 KB
  Мальвина Под музыку входит Мальвина Дюймовочка Айболит Буратино и Мальвина все вместе Здравствуйте ребята Дюймовочка вы хотите вместе с нами путешествовать по стране Сказок Дети Да Айболит но нам нужен транспорт чтобы попасть в эту страну.
60251. Твори своє щастя 81.5 KB
  Мета: ознайомити учнів з поняттям щастя формувати уміння розрізняти його серед інших почуттів; розвивати бачення прекрасного; збагачувати словниковий запас дітей; виховувати любов і повагу до матері сімї рідного краю викликати бажання робити добро...