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

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


 

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

70494. Малая группа как социально-психологическое образование 38 KB
  Именно в малых группах происходит формирование личности проявляются ее качества поэтому личность нельзя изучать вне группы. Через малые группы осуществляются связи личности с обществом: группа трансформирует воздействие общества на личность личность воздействует на общество сильнее...
70495. Шунты 83 KB
  Шунты применяются для расширения пределов измерения амперметров при этом большую часть измеряемого тока пропускают через шунт а меньшую – через измерительный механизм ИМ прибора. Шунты на малые токи выполняются в виде катушек или спиралей из манганинового провода шунты на большие...
70496. Приборы электростатической системы 61 KB
  Приборы электростатической системы бывают двух разновидностей: с изменяющейся площадью пластин; с изменяющимся расстоянием между пластинами рис. Приборы с изменяющимся расстоянием между пластинами состоят из двух неподвижных пластин одна из которых при измерениях заряжается...
70497. Приборы ферродинамической системы 90.5 KB
  Схемы включения определяются видами измеряемых величин и аналогичны включению амперметра вольтметра и ваттметра электродинамической системы. Приборы ферродинамической системы используют для измерений в цепях переменного тока в качестве ваттметров частотомеров фазометров...
70498. Приборы электродинамической системы 80.5 KB
  На оси прибора жестко закреплены подвижная катушка указательная стрелка с балансными грузиками магнитоиндукционный или воздушный успокоитель и концы двух противодействующих токопроводящих пружин. Перемещение подвижной части прибора происходит в результате взаимодействия магнитных...
70499. Приборы электромагнитной системы 176.5 KB
  Катушки амперметров наматывают медным проводом диаметром 0,6 мм и более. Приборы для измерения силы тока до 5 А имеют обмотку из 40 - 50 витков медного провода диаметром до 1 мм. При токе около 250 А катушку выполняют из медной шины. Катушки вольтметров наматывают медным изолированным проводом...
70500. Приборы магнитоэлектрической системы 143.5 KB
  Приборы магнитоэлектрической системы бывают двух разновидностей: с подвижной рамкой рис. Измерительный механизм приборов магнитоэлектрической системы с подвижной рамкой рис. 2 а состоит из: 1 ─ неподвижного цилиндрического сердечника установленного строго по центру...
70501. Класс точности. Нормирование погрешностей 40 KB
  Класс точности применяется для средств измерений используемых в технических измерениях когда нет необходимости или возможности выделить отдельно систематические и случайные погрешности оценить вклад влияющих величин с помощью дополнительных погрешностей.