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

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


 

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

25822. Острый и хронический ринит. Связь заболевания носа и среднего уха 14.78 KB
  Связь заболевания носа и среднего уха. Рини́т насморк синдром воспаления слизистой оболочки носа. Острый ринит возникает как следствие воздействия на слизистую оболочку полости носа вирусной или бактериальной инфекции. Поражение распространяется на обе половины носа.
25823. Полипы носа 14.67 KB
  Полипы носа. Назальные полипы обычно делят на антрохоанальные полипы и этмоидальные полипы. Несмотря на их удаление во время хирургического вмешательства назальные полипы возникают повторно примерно в 70 случаев. Она может быть проведена под общей или местной анестезией полипы удаляют при помощи эндоскопической хирургии.
25824. Заболевания полости рта. Дефекты губ и нёба 16.78 KB
  Дефекты губ и нёба. Аномалии твёрдого нёба: слишком высокое и узкое готическое плоское и низкое расщелины твёрдого нёба. Расще́лина нёба разрыв расщелина в средней части нёба возникающая вследствие не заращения двух половин нёба в период эмбрионального развития. Может быть поражена лишь часть нёба например только мягкое нёбо или язычок нёба или же расщелина может проходить по всей длине сочетаясь с билатеральными расщелинами в передней части верхней челюсти; нередко такие дети рождаются с расщелиной губы.
25825. Дефекты языка 13.97 KB
  Дефекты языка. К аномалиям развития языка относится прежде всего полное его отсутствие или аглоссия; недоразвитие языка микроглоссия или ненормально большой язык макроглоссия. Сравнительно частым дефектом развития является врождённое укорочение уздечки языка. При этом дефекте движения языка могут быть затруднены т.
25826. Дефекты челюстей и зубов. Прикусы: нормальный и патологический. Аномалии прикуса 15.92 KB
  Дефекты челюстей и зубов. Неправильное звукопроизношение особенно у детей вызывается различными дефектами строения челюстей которые ведут к аномалиям прикуса: прогнатией когда верхняя челюсть сильно выдается вперед; прогенией когда нижняя челюсть выступает вперед; открытым передним прикусом когда между верхними и нижними зубами при их смыкании остается промежуток; боковым прикусом когда при смыкании боковых зубов остаётся промежуток. Диастема аномалия положения зубов; чрезмерно широкий промежуток между резцами верхней...
25827. Нервно-мышечные нарушения полости рта 14.1 KB
  Одной из причин поражения лицевого нерва является воспаление среднего уха т. Из других причин необходимо отметить его травматические поражения и простудное воздействие. Паралич лицевого нерва бывает как правило односторонним что приводим к асимметричной деформации лица: на стороне поражения не закрывается глаз не поднимается бровь угол рта и щека опущены книзу отведение губ и оскаливание зубов невозможны весь рот перетянут на противоположную сторону. губы на стороне поражения не смыкаются и воздух свободно выходит через...
25828. Аудит расчетов с подотчетными лицами 45.5 KB
  Не все организации расплачиваются по безналичному расчету перечисляя деньги со своего счета на счет продавца. Для этого деньги выдаются из кассы сотрудникам под отчет. Если при покупке были израсходованы не все деньги то остаток сотрудник должен вернуть в кассу. Если же сотрудник переплатил добавил свои деньги то сумма переплаты организация должна ему компенсировать.
25829. Аудит расчетов с покупателями и заказчиками 29 KB
  Основная цель аудита установить правильность ведения учета расчетов с покупателями и заказчиками за реализованную отгруженную продукцию выполненные работы оказанные услуги. В ходе аудита расчетов с покупателями и заказчиками должны быть решены следующие задачи: проверка правильности оформления первичных документов по реализации продукции выполнению работ оказанию услуг с целью подтверждения обоснованности возникновения дебиторской задолженности; подтверждение своевременности погашения и правильности отражения на счетах...
25830. Аудит расчетов с поставщиками и подрядчиками 43 KB
  Цели и задачи аудита расчетов с поставщиками и подрядчиками Основная цель проверки установить правильность ведения расчетов с поставщиками и подрядчиками за полученные товарноматериальные ценности принятые выполненные работы и оказанные услуги. В ходе аудита расчетов с поставщиками и подрядчиками должны быть решены следующие задачи: проверка правильности оформления первичных документов по прибытию товарноматериальных ценностей и получению услуг с целью подтверждения обоснованности возникновения кредиторской задолженности; ...