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

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


 

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

16323. Определение удельного вращения и неизвестной концентрации сахарного раствора при помощи сахариметра СУ-3 244 KB
  Лабораторная работа Определение удельного вращения и неизвестной концентрации сахарного раствора при помощи сахариметра СУ3 Описание лабораторной установки Сахариметр СУ3 используемый в данной работе применяется для измерения угла вращения плоскости
16324. ОПРЕДЕЛЕНИЕ ПОКАЗАТЕЛЯ ПРЕЛОМЛЕНИЯ И СРЕДНЕЙ ДИСПЕРСИИ ЖИДКОСТИ С ПОМОЩЬЮ РЕФРАКТОМЕТРА ИРФ-22 373.5 KB
  ОПРЕДЕЛЕНИЕ ПОКАЗАТЕЛЯ ПРЕЛОМЛЕНИЯ И СРЕДНЕЙ ДИСПЕРСИИ ЖИДКОСТИ С ПОМОЩЬЮ РЕФРАКТОМЕТРА ИРФ22 Методические указания содержат подробное описание одной лабораторной работы общего физического практикума по оптике. Целью работы является определение показателей пре...
16325. ИЗУЧЕНИЕ ВНЕШЕНЕГО ФОТОЭФФЕКТА 174.5 KB
  ИЗУЧЕНИЕ ВНЕШЕНЕГО ФОТОЭФФЕКТА Теоретическая часть Описание явления. Свет падающий на вещество передает этому веществу энергию в результате чего могут возникать разнообразные эффекты. Среди этих явлений важное место занимает внешний фотоэлектрический эффект ...
16326. ОПРЕДЕЛЕНИЕ ПОКАЗАТЕЛЯ ПРЕЛОМЛЕНИЯ СТЕКЛА ПРИ ПОМОЩИ МИКРОСКОПА 137.5 KB
  ОПРЕДЕЛЕНИЕ ПОКАЗАТЕЛЯ ПРЕЛОМЛЕНИЯ СТЕКЛА ПРИ ПОМОЩИ МИКРОСКОПА Теоретическая часть В основе определения показателя преломления стекла в данной работе используется один из фундаментальных законов геометрической оптики: закон преломления света. Согласно ...
16327. ИЗУЧЕНИЕ МИКРООБЪЕКТОВ ПРИ ПОМОЩИ МИКРОСКОПА 259.5 KB
  Лабораторная работа ИЗУЧЕНИЕ МИКРООБЪЕКТОВ ПРИ ПОМОЩИ МИКРОСКОПА Теоретические основы эксперимента Принцип действия микроскопа основан на формировании увеличенного изображения исследуемого объекта за счет увеличения угла зрения линзами. На рис.1 показан ход ...
16328. Поляризация света. Лабораторный практикум по общей физике 648.5 KB
  Поляризация света Лабораторный практикум по общей физике Оптика Содержание Часть I Теоретические основы эксперимента Электромагнитная природа света. Уравнения Максвелла Поперечность световой волны и поляризация света Поляризация при отражении
16329. Программирование алгоритмов линейной структуры 131.5 KB
  Лабораторная работа № 1 Программирование алгоритмов линейной структуры Цель: приобретение навыков программирования алгоритмов линейной структуры с помощью подпрограммыфункции вычисляющей значение арифметических выражений. Индивидуальные варианты лаборатор
16330. Программирование алгоритмов разветвляющейся структуры 293 KB
  Лабораторная работа № 2 Программирование алгоритмов разветвляющейся структуры Цель: приобретение навыков программирования алгоритмов разветвляющейся структуры с помощью пользовательской подпрограммыпроцедуры где на определенном этапе производится выбор очеред...
16331. Программирование алгоритмов ветвлений со многими вариантами 54.5 KB
  Лабораторная работа № 3 Программирование алгоритмов ветвлений со многими вариантами Цель: приобретение навыков программирования алгоритмов ветвлений со многими вариантами с помощью пользовательской подпрограммыфункции позволяющей выбрать необходимый вариант из...