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

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


 

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

55641. Рівняння 64.5 KB
  Мета уроку: формування понять піраміда основа вершина бічні ребра висота піраміди вмінь учнів знаходити елементи піраміди. Спільну вершину трикутних граней називають вершиною піраміди протилежну...
55642. Квадратні рівняння. Розв’язування неповних квадратних рівнянь 119 KB
  Мета: Повторити вивчений матеріал про лінійні рівняння з однією змінною рівняння першого степеня його корені та способи розвязування; Вивести: означення квадратного рівняння та навчитися їх перетворювати до зведених квадратних рівнянь...
55643. Алгебраїчні рівняння та нерівності вищих порядків, які зводяться до квадратних 2.48 MB
  Основні методи розвязання рівнянь Розкладання лівої частини рівняння на множники А Спосіб групування 1 Розвязання 2 Відповідь: Б Застосування схеми Горнера 1 Розвязання Дільниками вільного члена є числа Серед них знаходимо корені рівняння...
55644. Рівняння. Розв’язування задач за допомогою рівнянь 286.5 KB
  Мета уроку: узагальнити та закріпити навички розвязування рівнянь і задач за допомогою рівнянь; розвивати навички усної лічби вміння аналізувати умову задачі й вибирати ту величину для позначення її змінною...
55645. РОЗВ’ЯЗУВАННЯ ДІОФАНТОВИХ РІВНЯННЬ 531.5 KB
  Ознайомити учнів з діофантовими рівняннями та різними способами їх розвязування можна на факультативних заняттях чи на засіданнях математичного гуртка. Кожен спосіб супроводжується теоретичним обґрунтуванням прикладами розвязаних задач та задачами для самостійного розвязування.
55646. Рівняння та їх властивості 117.5 KB
  Мета: навчальна: повторити основні відомості про рівняння; ознайомити учнів з основними властивостями рівнянь; формувати вміння застосовувати властивості при розвязуванні рівнянь...
55647. З Різдвом Христовим 289 KB
  У хату заходить господиня з діточками. Господиня Ой славен славен Святий вечір. Господиня Неси синку Дідуха на покуть. Господиня Несу кутю на покутю на зелене жито щоб бджоли сіли щоб ми дочекалися сіяти й орати щоб ми були багаті на бджоли й вівці на гроші й червінці.
55648. Святкування Різдва в Україні 49.5 KB
  Щось колядники не йдуть. До хати входять колядники співають Добрий вечір тобі пане господарю Радуйся Ой радуйся земле Син Божий народився. Застеляйте столи та все килимами Та кладіть калачі з ярої пшениці Бо прийдуть до тебе три празники в гості...
55649. Різдво Христове як прояв Божого милосердя 37.5 KB
  Мета: Виховати в учнів почуття радості Світлого Різдва Христового; формувати потребу приносити радість. Розвивати духовно моральне мислення учнів. Вмховувати духовно багату високоморальну особистість.