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

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


 

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

49353. Методы локализации неисправностей на аппаратуре СВ и РМ 1.09 MB
  Краткое описание тракта прохождения сигнала Алгоритм поиска неисправности: на структурном уровне на функциональном уровне на принципиальном уровне Заключение Список использованной литературы Задание на курсовое проектирование Неисправность обнаружена на АРМ РМ10 и имеет внешние проявления: яркая засветка экрана ЭЛТ БИО. Эти аналоговые сигналы поступают на блоки БИО и БИВ где обеспечивается отклонение луча...
49354. ЦИФРОВЫЕ СИСТЕМЫ ПЕРЕДАЧИ НЕПРЕРЫВНЫХ СООБЩЕНИЙ 777.15 KB
  Вид модуляции сигнала во второй ступени ЧМ. С учётом заданного вида модуляции сигнала определить его параметры характеризующие форму и требуемое значение полосы пропускания приёмного устройства. По полученному значению вероятности ошибки по формулам потенциальной помехоустойчивости найти минимальное значение отношения мощностей сигнала и помехи необходимое для обеспечения допустимого уровня искажения кода за счёт действия помех. Рассчитать требуемое значение полосы приёмника при использовании сложного сигнала.
49355. Методы логического и физического кодирования 292.4 KB
  В процессе выполнения задания необходимо выполнить логическое и физическое кодирование исходного сообщения в соответствии с заданными методами кодирования провести сравнительный анализ рассматриваемых методов кодирования выбрать и обосновать наилучший метод для передачи исходного сообщения. ЭТАПЫ РАБОТЫ Формирование сообщения В качестве исходного сообщения подлежащего передаче используются фамилия и инициалы студента выполняющего задание. Для цифрового представления сообщения необходимо использовать SCIIкоды. Определить длину сообщения.
49356. Методы локализации неисправностей в аппаратуре СВ и РМ 196.92 KB
  Задано внешнее проявление неисправности: отсутствует развертка на экране БИО по координате Х. Эти аналоговые сигналы поступают на блок БИО где обеспечивают отклонение луча ЭЛТ из центра в необходимое место экрана а ИПТ обеспечивает подсвет отклоненного луча.3 Блок индикатора основной Блок индикатора основной БИО предназначен для: стабилизации вторичной информации о воздушной обстановке; отображение результатов целераспределения состояния боевой готовности и этапов ведения боевых действий подчиненными огневыми средствами;...
49357. Составление алгоритма и программы вычисления функции с использованием нестандартных функций 44.54 KB
  Основной задачей выполнения курсовой работы по технологической информатике является закрепление теоретических знаний,полученных в процессе самостоятельной работы, а также на лекциях, практических , лабораторных занятия, развитие практических навыков программирования , работы за терминалами или персональными компьютерами.