Комбинаторика. Формирование комбинаторных групп из N по К (К - от 1 до N)

Комбинаторика. Орын ауыстыру (перестановка), орналастыру (размещение)

Орын ауыстыру

 

Мысал 1. 10 адам кезекте анша діспен труы ммкін?

 

Бл сеспті талылай отырып, 10 адамды кезекті 10 орнында орналастыру ажет екені тсінікті болып отыр, яни 10 элементтен 10 бойынша орналастыру ажет - . Ол мынаан те:

= 10 9 8 ... 3 2 1 = 10!

n элементтен n бойынша орналастыру n элементтен алмастыру деп аталады. Осылайша, n элементтен екі трлі алмастыру бір-бірінен элементтер санымен емес, элементтерді орналасу ретімен ерекшеленеді. Анытама. M = {a1, a2, ..., an} аыры жиыны бар болсын. М жиыныны n элементінен тратын рбір реттелген жиын осы жиынны алмастыруы деп аталады

Анытамаа сйкес n элементтен алуан трлі алмастырулар саны тмендегіге те:

мытпаыздар, 0! = 1.

Берілген есепті шешу шін санны факториалын есептейтін процедурасы бар программаны ру жет.

Program mіsal6;

uses WіnCrt;

var

n, f : longіnt;

{----------------------------------------------------------------------------------------}

Procedure Factorіal(n : іnteger; var f : longіnt);

var

і : іnteger;

begіn

f := 1;

іf n = 0 then f := 1

else for і := 1 to n do f := f*і

end;

{----------------------------------------------------------------------------------------}

begіn

wrіte('Жиынны элементтер санын енгізііз '); readln(n);

Factorіal(n, f);

wrіteln('Он адам кезекте ', f, ' діспен труы ммкін')

end.

 

Мысал 7. 2, 3, 4, 5, 9 цифрларынан анша жп бес табалы сан руа

болады?

 

Шешімні математикалы алгоритмі

Жп сандар жп цифрмен аяталады. Берілген мысалда жп сандар екеу.

Айталы, жп санны бірі барлы жадайда е соы орында орналассын, онда барлы алынатын сандар жп болады. Мндай сандар нешеу болады? Оны саны алан 4 цифрдан алынатын алмастырулар санына, яни 4!-а те. Біра берілген сандарды ішінде таы бір жп сан бар. Айталы, енді осы екінші жп сан да е соы орында орналассын. Онда таы да жп сандар шыады жне оны саны 4!-а те.

Нтижеде бес табалы жп сандар саны 2*4! болады.

 

Программаны ру иына сопайды. Сондытан да оны з бетінше рыыздар.

Тапсырма 3

0, 1, 2, 3, 5 цифрларымен 5-ке блінетін анша бес табалы сан руа болады?

 

 

Орналастыру

Алдымен математикадаы, оны ішінде жиындар теориясындаы кейбір ымдарды еске тсірейік.

Біріншіден, жиын дегеніміз не? Жиын ымы математикада негіз алаушы жне аныталмаан болып табылады.

Жиын дегеніміз андай да бір орта белгісі бойынша біріккен объектілер жиынтыы

Осылайша, сыныптаы орындытар мен стелдер жиыны жнінде, натурал сандар жиыны, бтін, рационал жне наты сандар жиыны туралы айтуа болады.

Жиына кіретін объектілерді элементтер деп атаймыз.

5 саны натурал сандар жиыныны элементі болады. стел сыныптаы стелдер жиыныны элементі болады. детте жиындар A, B, C, D, ..., X, Y, Z латынны бас ріптерімен белгіленеді, ал оларды элементтері a, b, c, d, ..., x, y, z кіші ріптермен белгіленеді.

а А жиыныны элементі дегенді а А жиынына тиісті дейді.

детте жиын элементтері фигуралы жаша ішінде жазылады:

Бізге элементтері крсетілген А жиыны жне B = {a1, a2, a3, a4} жиыны берілсін.

Байаанымыздай, В жиыныны рбір элементі А жиыныны да элементі болады. Бл жадайда В жиынын А жиыныны ішкі жиыны деп айтады.

Анытама..Егер В элементіні рбір элементі А жиыныны да элементі болса, онда В А-ны ішкі жиыны деп аталады.

Кп жадайда бізге жиын элементтерін ана емес, сонымен атар оларды жиындаы орналасу ретін де білу ажет болады.

Егер жиындаы элементтерді орналасу реті ескерілсе, онда орналасу реті р трлі бірдей элементтері бар жиындар біз шін р трлі жиындар болып саналады.

Мысалы: Z = {z1, z2, z3, z4 } и B = {z2, z1, z3, z4} р трлі жиындар болып саналады, йткені оларда жиындарды орналасу реті р трлі.

Элементтерді орналасу реті берілген жиын реттелген деп аталады

арапайым мысалдар арастырайы.

1-мысал. Сыныпта 12 оу пні бар. Бір кнде 5 р трлі саба тіледі. Саба кестесі анша трлі діспен рылуы ммкін.

 

Оу пндерін 1-ден 12-ге дейінгі цифрлармен белгілейік:

1, 2, 3, 4, 5, ..., 10, 11, 12.

Есепті шарты бойынша осы 12 санны ішінен 5 саннан тадау ажет. Осы бес саннан тратын тадау сандармен ана емес, оларды орналасу ретімен де ерекшеленуі тиіс, мысалы, терімні бірі келесідей болуы ммкін: {1, 2, 3, 4, 5}; осы сандарды алмастыруда шыатын {2, 1, 3, 4, 5} терімі де есепті шартын анааттандырады.

Шынында да, бірінші терім келесі пндерден тратын болсын: {алгебра, физика, химия, тарих, дебиет}; онда е болмаанда екі пнді алмастыру барысында алынан терім сабаты жаа кестесін береді: {физика, алгебра, химия, тарих, дебиет}.

Осылайша, 5 саннан тратын терім сандармен ана емес, оларды орналасу ретімен де ерекшеленуі ммкін.

Мндай ішкі жиындар комбинаторикада орналастырулар деп аталады.

Анытама. k бойынша n элементтен тратын орналасу деп берілген жиынны k элементтен тратын барлы реттелген ішкі жиыны аталады

Мысалы, M = {1, 2, 3, 4} жиынынан 4-тен 2-еу бойынша 12 р трлі орналастырулар алуа болады:

{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}

{2, 1} {3, 1} {4, 1} {3, 2} {4, 2} {4, 3}

n элементтен k бойынша алынан орналастырулар санын символымен ерекшелейміз жне = формуласы бойынша анытаймыз.

Яни, = = = = 12.

1-ші мысала оралайы. Онда 12-ден 5-еу бойынша орналастырулар санын табу керек.

Формула бойынша табатын болса: = =

Орналастыру санын баса діспен де табуа болады:

= =

Сонымен,

n элементтен k бойынша орналастыру саны k элементтер саныны кбейтіндісіне те деп айтса болады :

Мысалы,

Осылайша, осы принцип бойынша есептеу процедурасын ра отырып, біз факториалдар есептеуде шыатын лкен сандармен жмыс жасаудан тыламыз жне программа руды ысартамыз.

n элементтен k бойынша орналастыру процедурасы..

 

Procedure pl(n, k : іnteger; var r : longіnt);

var

і : іnteger;

begіn

r := 1;

for і := 1 to k do r := r*(n - k + і)

end;

 

Программасы

Program mіsal1;

uses WіnCrt;

var

n, k, r : longіnt;

{----------------------------------------------------------------------------------------}

{ n элементтен k бойынша орналастыру санын емесптейтін процедура }

Procedure pl(n, k : іnteger; var r : longіnt);

var

і : іnteger;

begіn

r := 1;

for і := 1 to k do r := r*(n - k + і)

end;

{----------------------------------------------------------------------------------------}

begіn

wrіte('Барлы пндер санын енгізііз '); readln(n);

wrіte('Бір кнде тілетін сабатар санын енгізііз '); readln(k);

Pl(n, k, r);

wrіteln('Саба кестесі нсаларыны саны мынаан те: ', r )

end.

 

Мысал 2. 0, 1, 2, ..., 9 цифрлары арылы трт табалы р трлі анша сан жазуа болады?

 

Алдымен 10-нан 4 цифр бойынша анша трлі діспен тадауа болатынын анытауымыз ажет. Яни 10 элементтен 4–еуден орналастырулар санын анытау ажет .

Біра сандарды бл шамасынан 0 цифрімен басталатындарын алып тастауымыз ажет, мысалы, 0123, 0213 жне т.с.с. Бл сандар трт табалыа жатпайды. Мндай сандар 9 цифрдан (0-ден баса) шыатын ш табалы сандар млшеріне, яни 9 элементтен 3-еу бойынша шыатын орналастырулар санына те, .

10 цифрдан растыруа болатын трт табалы сандар млшері айырмасына те.

Программасы

 

Program mіsal2;

uses WіnCrt;

var

n, k, a, a1 : longіnt;

{----------------------------------------------------------------------------------------}

Procedure placement(n, k : іnteger; var r : longіnt);

var

і : іnteger;

begіn

r := 1;

for і := 1 to k do r := r*(n - k + і)

end;

{----------------------------------------------------------------------------------------}

begіn

wrіte('Цифрларды берілген млшерін енгізііз '); readln(n);

wrіte('СВведите ко-во цифр, из скольких составляется число '); readln(k);

placement(n, k , a);

placement(n - 1, k - 1, a1);

wrіteln(' 0, 1, 2, .., 9 цифрлары арылы жазуа болатын трлі ');

wrіteln('трт табалы сандар млшері: ', a - a1)

end.

Тапсырма 1

Орналастыру процедурасын олданып, программа рыыз.

1. 40 адамнан тратын жиналыста з ортасынан трааны, оны орынбасарын жне хатшыны анша трлі діспен тадай алады?

2. 1, 2, 3, 4, 5 цифрларынан сандардаы цифрлар айталанбайтындай етіп анша ш табалы сан растыруа болады?

 

Орналастыру кмегімен шешілетін есептер

 

Мысал 3. Бір адам он ріпті бірінен жне бес цифрдан тратын телефон нмірін мытып кетті. Біра ол бл нмірде 3,5,7,9 цифрларыны бар екенін біледі. ажетті абонентке звондап хабарласу шін анша рет сынама жасап кру ажет?

 

Ізделініп отыран нмірге 5 орына трлі діспен орналастыруа болатын трт цифр енуі ажет , біра бесінші цифр 10 цифрді ішінен кез келгені болуы ммкін (0, 1, 2, ..., 9). Сондытан ріпсіз трлі телефон нмірлер саны болады.

Бл нмірлерді он ріпті райсысымен оса отырып, келесіні аламыз:

 

10 10 .

Орналастыру процедурасын олданып, программаны райы:

 

Program Problem3;

uses WіnCrt;

Var

p : longіnt;

{----------------------------------------------------------------------------------------}

Procedureplacement(n, k : іnteger; var r : longіnt);

Var

і : іnteger;

begіn

r := 1;

for і := 1 tok do r := r*(n - k + і)

End;

{----------------------------------------------------------------------------------------}

begіn

placement(5, 4, p);

p := 10*10*p;

wrіteln('звондап хабарласу шін ', p, ' рет сынама жасау керек')

End.

 

Мысал 4. n элементтен m бойынша анша орналастыру бірінші элементтен басталады?

 

Программа ру бойынша тсініктемелер

 

n элементтен бірінші элементті тадап алып, оны алынатын орналастыруларда бірінші орына ата бекітеміз.

Сонда, ізделініп отыран жиында n-1 элемент алады. Оны ішінен m - 1 элементтен тадап, оны бірінші кезекте тран бірінші элементке осу керек.

Енді n-1 –ден бойынша анша трлі діспен тадауа болатынын анытау ажет. Оны діспен орындауа болады.

Алынатын орналастыруларда бірінші элемент бірінші орына ата бекітіліп ойыландытан, барлы орналастырулар саны -а те болады.

 

Программасы

 

Program Problem4;

uses WіnCrt;

var

p : longіnt;

m, n : іnteger;

{----------------------------------------------------------------------------------------}

Procedure placement(n, k : іnteger; var r : longіnt);

var

і : іnteger;

begіn

r := 1;

for і := 1 to k do r := r*(n - k + і)

end;

{----------------------------------------------------------------------------------------}

begіn

wrіte('барлы элементтер санын енгізііз '); readln(m);

wrіte('Тадалатын элементтер санын енгізііз '); readln(n);

placement(m - 1, n - 1, p);

wrіteln('Бірінші элементтен басталатын ', m, ' элементтен ', n, ' бойынша ,');

wrіteln('орналастырулар саны', p, '-а те')

end.

Мысал 5. 10 элементтен 7 элементтен орналастырулар рылан. Осы орналастыруларды ішінен аншасыны рамында: а) бірінші элемент, б) екінші жне тртінші элементтер болады?

 

Шешуі

 

Біріншіден, бл есепті алдыысынан айырмашылыы андай?

Алдыы есепте бірінші элементке ата талап ойылды – ол алынан орналастыруларда міндетті трде бірінші орында труы ажет.

Бл мысалда бірінші элемент алынатын орналастыруларда бар болуы ажет, біра оны бірінші орында труы міндетті емес, яни ол алынатын орналастыруларда 7 орынны бірін алуы ммкін.

Жиын элементтерін 1-ден 7-ге дейінгі цифрлармен нмірлеп шыайы, сонда берілген элементтер жиыны {1, 2, 3, 4, 5, 6, 7} трінде жазылуы ммкін. Бірінші элементті берілген элементтен аламыз, ал «бос орындарды «х арылы белгілеп шыамыз. Крініп трандай, 7 ішкі жиын шыады.

Осыдан алынатын орналастыруларда діспен орналастыруа болатыны айдан аны.

Екіншіден, 10-нан бірінші элементті «шыарып алан со, онда 9 элемент алды. Осы 9 элементтен барлы алынатын элементтер саны 7-еу болуы шін бірінші элементке 6-уын тадап, осу ажет. Оны діспен орындауа болады.

Нтижеде, орналастырулар санына те дістер санына ие боламыз. Осы есепті б) пунктіндегі есепті шешімін ойластырыыз.

Программаны з бетінше орындаыздар

Тапсырма 2

1. m элементтен n бойынша анша орналастыру бірінші элементтен баса кез келген элементтен басталады?

2. 10 элементтен 7 элемент бойынша орналастырулар рылан. Осы орналастыруларды нешеуіні рамында а) бірінші элемент б) шінші жне бесінші элементтер болмайды?

 

Жаттыулар

1. Та цифрлардан райсысын тек бір рет олданып анша ш табалы сан руа болады?

2. Барлы цифрлардан сандардаы цифрлар айталанбайтындай етіп анша ш табалы сан руа болады?

3. 20 адам атысып отыран жиналыста президиума 2 адам, оны бірі траа, ал екіншісі хатшы болуа тадап отыр. Мны анша трлі діспен орындауа болады?

4. сзіні ріптерінен 4 ріптен тратын анша трлі сз растыруа болады?

5. 0, 1, 2, ..., 9 цифрларыны кмегімен трлі трт табалы анша сан руа болады?

6. 3, 5, 7, 11, 13, 17, 19, 23 сандарынан анша трлі дрыс блшек руа болады?

Комбинаторика. Формирование комбинаторных групп из N по К (К - от 1 до N)

 

Аннотация: В лекции рассмотрен второй класс задач, в которых N ОПРЕДЕЛЕНО, а K НЕ ОПРЕДЕЛЕНО (N - количество предметов в исходном множестве, K - количество предметов, выбираемых из исходного множества).

Цель лекции: научиться создавать комбинаторные группы двоичным перебором.

 

Пусть N=4. Необходимо сформировать различные группы элементов выбираемых из исходного множества. Количество элементов в выборке от 1 до N. Элементы исходного множества будем хранить в массиве А (рис. 12.1):


Рис. 12.1.

Составим таблицу, в которой выбранный элемент отметим "1", невыбранный - "0":

Таблица 12.1.

Итого, сформированы группы: {3}, {2}, {2, 3}, {1}, {1,3}, {1, 2}, {1, 2, 3}.

Для формирования групп потребовалось перебрать все варианты комбинаций "0" и "1". Такой метод формирования комбинаторных групп называется "Двоичным перебором", а количество групп будет равно 2n-1.

Идея решения: для выбора элементов из исходного множества необходимо получить двоичный код (на единицу больше предыдущего). Первый вариант получения нового двоичного кода - перевод счетчика цикла i из десятичной в двоичную систему счисления. Второй вариант получения очередного двоичного кода - ищем в массиве двоичных кодов d последний нулевой элемент , заменяем его на единицу и обнуляем все следующие за ним элементы (этот метод называется лексигрофическим порядком).

Количество возможных комбинаций двоичных кодов 2^n-1 (исключаем двоичный код, состоящий из одних нулей).

Программная реализация на Бейсике:

input "введите количество элементов исх. множества="; nfor i=1 to n input "введите элемент"; a(i)nextfor i=1 to 2^n-1 rem=поиск первого нулевого элемента========= for j=1 to n if d(j)=0 then x=j next rem=формирование двоичного кода=========== for z=x to n d(z)=0 next z d(x)=1 rem=печать элементов==================== for j=1 to n if d(j) <> 0 then print a(j); next j printnext i

Программная реализация на Паскале:

const nn=10;var a,d: array [1..nn] of integer; i,n,x,j,z,st: integer;begin writeln ('количество элементов'); readln (n); for i:= 1 to n do begin writeln ('введите элемент'); readln (a[i]); end; {=формирование двоичного кода===} st:=1; for i:=1 to n do st:=st*2; for i:= 1 to (st-1) do begin for j:= 1 to n do if d[j]= 0 then x:= j; for z:= x to n do d[z]:=0; d[x]:=1; {=печать элементов========} for j:= 1 to n do if d[j]<>0 then write (a[j]); writeln; end;end.

Тест:

Дано: N=3{1,2,3}
Результат: 2,3 1,3 1,2 1,2,3

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

Задачи:

  • "Размен монет": дана купюра достоинством X. Требуется разменять ее монетами по 1, 5, 10, 50 рублей.
  • Даны гири массами M1, M2, M3, M4. Как можно взвесить предмет массой X?
  • Даны N чисел. Выделите из них группы, содержащие от 1 до N элементов, каждая из которых имеет сумму X.

Программная реализация на Бейсике:

input "x="; xinput "количество элементов в исходном множестве"; nfor i = 1 to n input "введите элемент"; a(i)nextfor i = 1 to (2^n - 1) rem==получение следующего двоичного кода== for j = 1 to n if d(j) = 0 then k = j next j for z = k to n d(z) = 0 next z d(k) = 1 rem============================= s = 0 for j = 1 to n if d(j) <> 0 then s = s + a(j) next j rem========вывод результата========== if s = x then for ii = 1 to n if d(ii) <> 0 then print " "; a(ii); next ii end if printnext i

Программная реализация на Паскале:

const nn=10;var a,d: array [1..nn] of integer; ii,i,n,x,j,z,st,k: integer;begin writeln ('введите с чем сравнивать); readln (х); writeln ('введите количество элементов'); readln (n); for i:= 1 to n do begin writeln ('введите элемент'); readln (a[i]); end; {=вычисление количества возможных комбинаций=} st:=1; for i:=1 to n do st:=st*2; {=================================} for i:= 1 to (st-1) do begin {=получение следующего двоичного кода===} for j:= 1 to n do if d[j]= 0 then k:= j; for z:= k to n do d[z]:=0; d[k]:=1; {=============================} s: = 0; for j: = 1 to n do if d[j] <> 0 then s:= s + a[j]; if s = x then {=====вывод результата=========} for ii:= 1 to n do if d[ii] <> 0 then write (a[ii]); writeln; end;end.

Тест:

Дано: x=5n=31,2,3
Результат: 2,3

Ключевые термины

  • Двоичный перебор - метод формирования комбинаторных групп из исходного множества элементов, на которые "указывают" единицы в соответствующем разряде двоичного кода.
  • Лексиграфический порядок - метод получения очередного двоичного кода.

Краткие итоги

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

Двоичный код (поразрядно) хранится в дополнительном массиве, имеющем такую же размерность, что и массив с исходным множеством элементов. В массиве двоичных кодов на каждом шаге получаем новый двоичный код, единицы которого "указывают" на соответствующие разряды массива исходного множества.

Получение очередного двоичного кода в лексиграфическом порядке предполагает такой алгоритм: массив с двоичным кодом обходится справа налево, ищется первый ноль, он заменяется на единицу, а все элементы, стоящие левее - обнуляются.

Набор для практики

Вопросы.

  • В чем заключается метод двоичного перебора при формировании комбинаторных групп?
  • Укажите количество разнообразных n-разрядных двоичных кодов.
  • Каким образом можно получить следующее за текущим двоичное число (алгоритм получения)?
  • Что изменится в алгоритме формирования комбинаторных групп, если состояние исходных объектов можно охарактеризовать не только как "выбран"/"не выбран": выбранный объект также градируется ("выбран в соответствии с условием 1"/" выбран в соответствии с условием 2")?

Упражнения.

  • Ввести с клавиатуры целое число n. Вывести натуральный ряд двоичных чисел до числа, десятичное представление которого не превосходит n.
  • Тур-фирма предлагает разнообразные путевки, хранящиеся в базе данных в виде названий туров и их стоимостей (всего n туров). Сделать выборку из базы данных тех туров, которые подходят покупателю по цене (покупатель рассчитывает приобрести не более трех путевок не менее, чем на m рублей).