Комбинаторные задачи в информатике

В науке и практике часто встречаются задачи,  решая которые приходится составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций. Такие задачи получили название комбинаторных задач, а раздел математики, в котором рассматриваются подобные задачи,называется комбинаторикой.

Термин "комбинаторика" ввел в математический обиход Готфрид Вильгельм Лейбниц (1.07.1646 - 14.11.1716) - всемирно известный немецкий учёный.

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

В знаменитой басне Крылова «Квартет» «проказница Мартышка, Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент: они исследовали влияние взаимного расположения музыкантов на качество исполнения. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты. Зададимся вопросом: сколько существует способов, чтобы рассадить, например в один ряд, четырёх музыкантов?

«Особая примета» комбинаторных задач — вопрос, который всегда можно сформулировать так, чтобы он начинался словами: «Сколькими способами...».

Презентация содержит 20 слайдов.

КОМБИНАТОРНЫЕ ЗАДАЧИ

Что такое комбинаторика?

В науке и практике часто встречаются задачи, решая которые приходится составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций . Такие задачи получили название комбинаторных задач, а раздел математики, в котором рассматриваются подобные задачи,называется комбинаторикой.

« Комбинаторика»( лат. «combinare», соединять, сочетать)

Что такое комбинаторика?

Термин "комбинаторика"

ввел в математический обиход

Готфрид Вильгельм Лейбниц (1.07.1646 - 14.11.1716) - всемирно известный немецкий учёный

Что такое комбинаторика?

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках,

о построении магических

и латинских квадратов.

ОСОБАЯ ПРИМЕТА !

В знаменитой басне Крылова

«Квартет» «проказница Мартышка,

Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент: они исследовали влияние взаимного расположения музыкантов на качество исполнения. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты. Зададимся вопросом:

сколько существует способов, чтобы рассадить, например в один ряд, четырёх музыкантов?

ОСОБАЯ ПРИМЕТА !

Воспетый Маяковским «молоткастый, серпастый» советский паспорт имел серию и номер, состоящие в общей сложности из трёх частей:

• некоторое число, записанное римскими цифрами;
• две русские буквы;
• шесть арабских цифр.

Например, ГХ-РГ № 062993. Разумеется, все паспорта должны иметь разные номера.

Сколько может быть различных паспортов?

ОСОБАЯ ПРИМЕТА !

Нас приглашают сыграть в Лотто-Миллион. Суть игры в том, что нужно из 49 номеров угадать 6, которые выпадут во время тиража. Для участия в игре следует приобрести специальную карточку и вычеркнуть в ней 6 любых квадратов, пронумерованных числами от 1 до 49. Чтобы выиграть наверняка можно было бы запастись таким количеством карточек, какое необходимо для вычёркивания 6 номеров всеми возможными способами

Сколько этих способов?

ОСОБАЯ ПРИМЕТА !

Общее у всех трёх задач то, что их решением занимается отдельная область математики, называемая комбинаторикой.

«Особая примета» комбинаторных задач — вопрос, который всегда можно сформулировать так, чтобы он начинался словами: «Сколькими способами...».

Размещения без повторений

Имеется n различных элементов. Сколько из них можно составить к расстановок?

При этом две расстановки считаются различными, если они отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

Такие расстановки называют размещения без повторений, а их число обозначают (читается «а из n по к»; А-первая буква французского слова Arrangement , что означает приведение в порядок).

Справедлива формула:

= n ( n-1)(n-2) …. (n-k+1)

ЗАДАЧА

В первой группе класса «А» первенства по футболу участвуют 17 команд. Разыгрываются медали: золотые, серебряные, бронзовые. Сколькими способами они могут быть распределены?

Решение

А =17*16*15=4080

Перестановки

При составлении размещений без повторений из n элементов по к мы получили расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все n элементов, то они могут отличаться друг то друга лишь порядком входящих в них элементов. Такие расстановки называют перестановками из n элементов , или, короче, n - перестановками. Обозначается Р (Р-первая буква французского слова Permutation - «перестановка»).

= = n(n-1 )… 2*1=n !

=

ЗАДАЧА

Семь девушек стоят в круге. Сколькими различными способами они могут встать в круг?

Решение

Р =7!=7*6*5*4*3*2*1=5040

Перестановки с повторениями

До сих пор мы переставляли предметы, которые были попарно различны. Если же некоторые переставляемые предметы одинаковы, то получается меньше перестановок- некоторые перестановки совпадут друг с другом.

Р = N !

ЗАДАЧА

Сколько перестановок можно сделать из букв слова «Миссисипи»?

Решение

Р(4,3,1,1)=9!:(4!*3!*1!*1!)=2520

Сочетания

Всякая неупорядоченная выборка объема к из множества, состоящего из n различных объектов, полученная в схеме выбора без возвращений, называется сочетанием из n элементов по к.

Таким образом, сочетания различаются составом входящих в них объектов, но непорядком этих объектов. Из определения выбора без возвращений следует, что к удовлетворяет неравенствам 0 к n .

Обозначают С (читается: «це из n по к »; С-первая буква французского слова Combinasion - «сочетания»). Вычисляют по формуле

ЗАДАЧА

В полуфинале по шахматам участвуют 20 человек, а в финал выходят только трое. Сосчитать число различных исходов полуфинала.

Решение

Задачи по программированию

Сколькими способами можно набрать n рублей, если существуют монеты 1, 2, 5, 10 и 50 рублей.

var n,i,j,k,l,m,s:byte;

begin

readln(n);

for i:=0 to n do

for j:=0 to n div 2 do

for k:=0 to n div 5 do

for l:=0 to n div 10 do

for m:=0 to n div 50 do

if i+j*2+k*5+l*10+m*50=n then begin

writeln('1*',i,'+2*',j,'+5*',k,'+10*',l,'+50*',m,'=',n);

s:=s+1; end;

writeln(' Комбинаций ',s);

readln ;

end .

Задачи по программированию

Сколько можно составить слов из 4 букв, при этом алфавит состоит из 20 букв

const n=20;

a:array[1..n] of string=(' а ',' б ',' в ',' г ',' д ',' е ',' ж ',' з ',' и ',' к ',

' л ',' м ',' н ',' о ',' п ',' р ',' с ',' т ',' у ',' ф ');

var i,j,k,l:integer; s:real;

begin

for i:=1 to n-3 do

for j:=i+1 to n-2 do

for k:=j+1 to n-1 do

for l:=k+1 to n do begin

writeln(a[i]:2,a[j]:2,a[k]:2,a[l]:2);

s:=s+1;

end;

writeln(s*s*s*s:20:0);

readln ;

end .

ВЫВОД

Знания основ комбинаторики и умение их применять в программировании позволяет решить множество задач из математики, информатики и просто задач из повседневной жизни, с которыми мы сталкиваемся.

Спасибо за внимание!