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

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


 

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

84044. Нормативное обеспечение создания электронного правительства в РФ с 2008 г. по настоящее время 40.25 KB
  № 8ФЗ Об обеспечении доступа к информации о деятельности государственных органов и органов местного самоуправления далее – Федеральный закон № 8ФЗ. Действие Федерального закона № 8ФЗ распространяется на отношения связанные с обеспечением доступа пользователей информацией к информации о деятельности государственных органов и органов местного самоуправления. Федеральный закон № 8ФЗ определяет принципы и способы обеспечения доступа к информации о деятельности государственных органов и органов местного самоуправления закрепляет права...
84045. Федеральный закон от 27 июля 2010 г. № 210-ФЗ «Об организации предоставления государственных и муниципальных услуг»: новации в документообороте при предоставлении государственных (муниципальных) услуг 38.91 KB
  № 210ФЗ Об организации предоставления государственных и муниципальных услуг: новации в документообороте при предоставлении государственных муниципальных услуг. N 210ФЗ Об организации предоставления государственных и муниципальных услуг направлен на регулирование вопросов предоставления государственных и муниципальных услуг в том числе вопросов предоставления таких услуг в электронном виде. Закона также устанавливает требования к процедурам предоставления государственных муниципальных услуг в электронном виде; Закон регламентирует...
84046. Документационное обеспечение управления как наука и учебная дисциплина 36.63 KB
  Документационное обеспечение управления ДОУ – это деятельность направленная на организацию документирования в организации и управления технологическим циклом движения документов. Поэтому термин ДОУ подчеркивает информационносоставляющую в современной организации делопроизводства. Документационное обеспечение управления – это деятельность аппарата управления охватывающая вопросы документирования и организации работы с документами в процессе осуществления им управленческих функций. Деятельность каждой организации осуществляется в...
84047. История развития делопроизводства в России 44.78 KB
  В этих условиях единая система делопроизводства не была востребована самой системой управления. Рассмотренный период можно охарактеризовать как период постепенного складывания традиций русской системы делопроизводства накопления опыта документирования обработки и хранения документов обеспечения их сохранности. Система государственного делопроизводства начинает складываться только в середине 15 века с развитием Московского княжества в государство.
84048. Документооборот: понятие, функции, составные части. Объем документооборота, способы его учета 40.09 KB
  Документооборот организации – это движение документов в организации с момента их создания или получения до завершения исполнения или отправления. Характеристикой документооборота является его объем под которым понимается количество документов поступивших в организацию и созданных ею за определенный период. Кроме этого регистрация позволяет осуществлять контроль исполнения документов а также вести их поиск. Наряду с организацией документооборота в понятие организация работы с документами входит хранение документов и их использование в...
84049. Виды документов ИОГВ Пермского края их роль в документационном обеспечении управления 34.29 KB
  Деятельность губернатора Пермского края руководителя администрации губернатора Пермского края председателя Правительства Пермского края заместителей председателя Правительства Пермского края руководителя аппарата Правительства Пермского края обеспечивается комплексом документов составляющим организационнораспорядительную документацию. Губернатор Пермского края издает указы и распоряжения во исполнение Конституции Российской Федерации федеральных законов нормативных актов Президента Российской Федерации постановлений Правительства...
84050. Способы документирования. Способы записи и воспроизводства информации документа 35.53 KB
  Способы записи и воспроизводства информации документа. Документирование – запись информации на различных носителях по установленным правилам. Носитель документированной информации – материальный объект используемый для закрепления и хранения на нем речевой звуковой или изобразительной информации в том числе в преобразованном виде. Запись информации это способ фиксирования информации на материальном носителе.
84051. Нормативные правовые акты РФ, федеральных органов исполнительной власти РФ, регламентирующие порядок делопроизводства и документооборота в органах государственной власти 36.97 KB
  Нормативную базу делопроизводства составляют: законодательные акты Российской Федерации в сфере документации и информации; указы и распоряжения Президента Российской Федерации постановления Правительства Российской Федерации в сфере делопроизводства; законодательные акты субъектов Российской Федерации и правовые акты принимаемые органами исполнительной власти субъектов Российской Федерации учитываются при организации делопроизводства органами представительной и исполнительной власти субъектов Федерации а также организациями...
84052. Структура и функции Управления документационного обеспечения аппарата Правительства Пермского края 33.28 KB
  Управление документационного обеспечения является структурным подразделением аппарата Правительства Пермского края и выполняет следующие функции: организует и регулирует документационное обеспечение; участвует в автоматизации документирования проектов законов постановлений протоколов и стенограмм заседаний других документов Правительства Пермского края; обеспечивает организационнотехническую подготовку и проведение заседаний; организует архивное хранение документов Правительства Пермского края и подготавливает их к передаче на...