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

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


 

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

63467. Струйная печать 370 KB
  Лишние капли отклоняющая система направляет в систему сбора и рециркуляции чернил чтобы затем использовать их вновь иначе расход красителя сделал бы себестоимость печати дорогой. Так в коммерческих системах печати капли генерируются...
63469. Принципи постмодернізму в художній літературі рубежу ХХ – ХХІ століть 32.98 KB
  Мета: Ознайомити студентів зі зрушеннями у філософських концепціях способі мислення сучасної людини що відбулися на межі ХХ ХХІ століть та знайшли специфічне відображення у текстах художньої літератури. Завдання: Розкрити особливості й сутність сучасної ситуації постмодернізму.
63470. Спецификация JavaBeans 158 KB
  Для того, чтобы класс Java можно было назвать компонентом JavaBeans, он должен удовлетворять перечисленным ниже требованиям: Способность к инициализации нового экземпляра. Компоненты JavaBeans нельзя создавать на основе интерфейсов и абстрактных классов.
63471. Сериализация объектов 96 KB
  Сериализация объектов Java позволяет вам взять любой объект, который реализует интерфейс Serializable, и включить его в последовательность байт, которые могут быть полностью восстановлены для восстановления исходного объекта.
63472. Настройка страницы свойств 102.5 KB
  При создании кода компонента JavaBeans следует помнить о том, что этот компонент помимо пассивных имеет и активных пользователей, которые могут применять для него визуальные инструменты разработки.
63473. Java DataBase Connectivity. Основы языка SQL 162 KB
  Чтобы получить доступ в БД, поставляемой некоторым поставщиком, вы обращаетесь через разработанный поставщиком движок, в котором используется своя реализация SQL. Несовместимость, главным образом, связана с встроенным SQL и хранимыми процедурами (stored procedure).
63474. Java DataBase Connectivity. Уровни изолированности транзакций 84 KB
  Есть несколько способов разрешения конфликтов между одновременно выполняющимися транзакциями. Пользователь может задать уровень изолированности, то есть уровень внимания, которое СУБД должна уделить при разрешении возможных конфликтов.
63475. Информационные системы 93.5 KB
  Пример: Система Элементы системы Главная цель системы Фирма Люди оборудование материалы здания Производство товаров Информационная система Компьютеры компьютерные сети люди информационное и программное обеспечение Производство профессиональной информации Информационная система...