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

Комбинаторика. 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 билет алады. Оның үшеуі ұтысты болуы үшін лотореяны қанша әдіспен алуға болады?