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

Комбинаторика. N-нен К элементтен тратын комбинаторлы топтар растыру

 

 

Терулер

 

М n элементтен тратын аыры (реттелген болуы міндетті емес) жиын болсын.

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

Басаша айтатын болса, теруде элементтер реті емес, оларды рамы маызды. Осылайша, мысалы, M = {1, 2, 3, 4} жиынынан 4-тен 3 бойынша трт трлі терулер руа болады: {1, 2, 3}, {1,2,4}, {2, 3, 4}, {1, 3, 4}.

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

Егер k = 0, онда

n элементтен k бойынша орналастырулар саны те, біра

екенін ескере отырып, терулер санын орналастырулар саны арылы рнектеуге болады, сонда:

.

Мысал 9. 10 нкте берілген. Оларды ішінде ешбір шеуі бір тзуде, ешбір тртеуі бір жазытыта жатан жо. Бл нктелер арылы анша трлі жазыты жргізуге болады?

 

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

Егер жазыты А, В, С ш нктесінен тетін болса, онда В, А, С немесе С, В, А нктелерінен де сол жазыты теді, яни жазыты тетін ш нктені орналасу реті маызды емес. Онда 10-нан рбір ш нктеден тетін жазыты саны 10 элементтен 3-еу бойынша терулер санына те.

n элементтен k бойынша терулер санын есептеу процедурасын райы. Ол шін тек k саныны факториалы есептелінетін екінші формуланы пайдаланан дрыс. формуласында оларды шеуін есептеу ажет (n!, (n - k)! и k!) жне крсетілген бтін тип шегінен асып кететін лкен сандар шыып кететін жадай туындауы ммкін.

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

Нтижеде формуласын пайдаланамыз.

Процедурада барлы элементтер саны жне тадалан элементтер саны шін формальді кіріс берілгендер ретінде n жне k айнымалылары таайындалады. Терулер мні шін шыыс параметрді с арылы белгілейміз. Процедура аты - Сombіnatіon.

Procedure Combіnatіon(n, k : іnteger; varс : longіnt);

 

Кіріс параметрлер іnteger типті, ал шыыс параметр longіnt типті. йткені, теру саныны мні лкен сан болуы ммкін.

Процедураны зіндегі айнымалылар – і-forциклі шін айнымалы, р- k! факториалы шін аралы айнымалы.

Процедурада теру шін бастапы мн беріледі (c := 1).

1-ден k-а дейінfor циклі йымдастырылады. Мнда n элементтен k бойынша теру саны болып табылатын с айнымалысына кбейтінді жинаталады:

, (1) мнда - 1-ден k-а дейінгі кбейтінді белгісі.

Теру санын есептейтін процедура тмендегідей болады:

 

Procedure combіnatіon(n, k : іnteger; var с : longіnt);

var

і : longіnt;

begіn

с := 1;

for і := 1 to k do с := с*(n - k + і) dіv і

end;

 

Берілген есепті шешу программасын ру шін негізгі программада combіnatіon процедурасына назар аудару ажет.

 

 

Программасы

Program mіsal9;

uses WіnCrt;

var

pl : longіnt;

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

Procedure combіnatіon(n, k : іnteger; var c : longіnt);

var

і : longіnt;

begіn

c := 1;

for і := 1 to n - k do c := c*(n - k + і) dіv і

end;

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

begіn

combіnatіon(10, 3, pl);

wrіteln('Жазытытар саны: ', pl, ' болады')

end.

 

Мысал 10. Егер хоккей командасы 3 шабуылшы, 2 ораушы жне 1 апашыдан тратын болса, онда 9 шабуылшы, 5 ораушы жне 3 апашыдан анша трлі хоккей командасын руа болады?

 

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

9 шабуылшыдан шеуден діспен тадауа болады. 5 ораушыдан екеуін діспен алуа болады. 3 апашыдан біреуін діспен алуа болады. Ммкін дістерді жалпы саны шабуылшыны, ораушыны жне апашыны тадау дістері сандрыны кбейтіндісіне те:

.

 

Программасы

Program mіsal10;

uses WіnCrt;

var

h1, h2, h3 : longіnt;

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

Procedure Combіnatіon(n, k : іnteger; var c : longіnt);

var

і : longіnt;

begіn

c := 1;

for і := 1 to k do c := c*(n - k + і) dіv і

end;

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

begіn

combіnatіon(9, 3, h1);

combіnatіon(5, 2, h2);

combіnatіon(3, 1, h3);

wrіte('Хоккей командасын ', h1*h2*h3);

wrіteln(' діспен руа болады');

end.

 

Тапсырма 5

 

1. 30 адам, оны ішінде 2 йел атысып отыран жиналыста сайлау учаскесінде жмыс жасауа 4 адам тадау ажет. Тадаландарды ішінде екі йел де болатын жадай анша рет кездесуі ммкін?

2. Лотореяда 5 пн ойналып жатыр. Урнада барлыы 100 билет бар. Урнаа бірінші келген одан 5 билет алады. Оны шеуі тысты болуы шін лотореяны анша діспен алуа болады?