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

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


 

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

15265. ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ОБЛАСТЕЙ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ СИСТЕМЫ НА ПЛОСКОСТИ ДВУХ ПАРАМЕТРОВ. МЕТОДИЧКА 84.95 KB
  ЛАБОРАТОРНАЯ РАБОТА № 8 ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ОБЛАСТЕЙ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ СИСТЕМЫ НА ПЛОСКОСТИ ДВУХ ПАРАМЕТРОВ Цель работы. Ознакомление с экспериментальными методами построения областей устойчивости линейных динамических систем и изучение влияния на...
15266. ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ОБЛАСТЕЙ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ СИСТЕМЫ НА ПЛОСКОСТИ ДВУХ ПАРАМЕТРОВ 69.47 KB
  Лабораторная работа №8 ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ОБЛАСТЕЙ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ СИСТЕМЫ НА ПЛОСКОСТИ ДВУХ ПАРАМЕТРОВ Вариант №1 1. Цель работы. Ознакомление с экспериментальными методами построения областей устойчивости линейных динамических систем и изуче...
15267. ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ЧАСТОТНЫХ ХАРАКТЕРИСТИК ТИПОВЫХ ДИНАМИЧЕСКИХ ЗВЕНЬЕВ 1.98 MB
  ЛАБОРАТОРНАЯ РАБОТА № 9 ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ЧАСТОТНЫХ ХАРАКТЕРИСТИК ТИПОВЫХ ДИНАМИЧЕСКИХ ЗВЕНЬЕВ Цель работы. Изучение частотных характеристик типовых динамических звеньев и способов их построения. Методические рекомендации. До начала работы студенты д
15268. Экспериментальное построение частотных характеристик типовых динамических звеньев 160.34 KB
  Лабораторная работа №9 Экспериментальное построение частотных характеристик типовых динамических звеньев Вариант 1 Цель работы. Изучение частотных характеристик типовых динамических звеньев и способов их построения. Исследуемые звенья: 1. Апериодическ...
15269. ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЭЛЕКТРОМЕХАНИЧЕСКОГО ОБЪЕКТА УПРАВЛЕНИЯ 2.5 MB
  ЛАБОРАТОРНАЯ РАБОТА № 10 ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЭЛЕКТРОМЕХАНИЧЕСКОГО ОБЪЕКТА УПРАВЛЕНИЯ Цель работы. Изучение математических моделей и исследование характеристик электромеханического объекта управления построенного на основе электродвигателя пос...
15270. Построение математической модели электромеханического объекта управления 332 KB
  Лабораторная работа №10 Построение математической модели электромеханического объекта управления по курсу Теория управления вариант 1 Цель работы: изучение математических моделей и исследование характеристик электромеханического объекта управления пост...
15271. Исследование механических характеристик АД с короткозамкнутым ротором 317.01 KB
  2 ОТЧЁТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №1 Тема: Исследование механических характеристик АД с короткозамкнутым ротором Цель работы: с помощью приложений ActiveASMA и DynAMA исследовать механические характеристики АД с короткозамкнутым ротором; исследовать зависимости...
15272. Исследование механических характеристик ДПТ с независимым возбуждением в двигательном режиме 904.83 KB
  ОТЧЁТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №2 Тема: Исследование механических характеристик ДПТ с независимым возбуждением в двигательном режиме Цель работы: с помощью приложений ActiveASMA и DynAMA исследовать механические характеристики ДПТ с независимым возбуждением получить иск...