Осымша сабақтар үшін
Мысал 14. 210 санының барлығы қанша бөлгіші бар? 30030 санында ше? N бүтін санында ше?
Егер келесі математикалық ұйғарымды білсек, онда бұл есепті шешу қиынға соқпайды.
p1,..., pm – q санының әр түрлі қарапайым бөлгіштері болсын. Егер 
болса, мұндағы 
- қандай да бір натурал сандар, онда q санының барлық бөлгіштер саны (1 мен q-ды қоса) a1, a2,..., am дәреже көрсеткіштерінің қайталанбалы терулер санына тең. Ал ол өз кезегінде 
туындысына тең.
Программаны құру алгоритмі төмендегідей болуы мүмкін:
- 2-ге бөлінетін қарапайым бөлгіштер саны анықталады.
- Бұл бөлгіштер саны 1-ге арттырылып, s айнымалысына меншіктеледі.
- Тақ қарапайым бөлгіштер саны анықталады.
- Әрбір қарапайым бөлгіш үшін олардың саны орнатылады да 1-ге арттырылады және s-ке көбейтіледі.
- Нәтижеде барлық бөлгіштер саны экранға шығарылады.
Program Problem14;
uses WіnCrt;
var
s, q, m, j, n: іnteger;
begіn
wrіte('Введите целое число '); readln(n);
m:= n;
q:= 0;
s:= 0;
whіle m mod 2 = 0 do
begіn
q:= q + 1;
m:= m dіv 2
end;
s:= q + 1; j:= 3; q:= 0;
whіle j <= m do
begіn
іf m mod j =0 then
begіn
q:= q + 1;
m:= m dіv j
end;
s:= s*(q + 1);
іf m mod j <> 0 then j:= j + 2
end;
wrіteln(n, ' санының барлық бөлгіштер саны ', s, ' болады')
end.
Тапсырма 8
Егер 15 түзу сызықтың 4-уі өзара параллельді және қиылысу нүктесінен тек қана екі түзу өтетін болса, онда осы 15 түзу сызық қанша нүктеде қиылысады?
Жиі кездесетін процедуралар мен функциялар кітапханасы
1. n элементтен k элемент бойынша орналастырулар процедурасы.
Procedure placement(n, k: іnteger; var r: longіnt);
var
і: іnteger;
begіn
r:= 1;
for і:= 1 to k do r:= r*(n - і + 1)
end;
2. n элементтен k элемент бойынша терулер саны процедурасы
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;
Жаттығулар
1. 5-, 8 -, 12 – және 15 бұрыштықтардың барлық диагональдар санын анықтау?
2. Әрқайсысында 100 сайыскері бар екі спорт қоғамы жарысқа қатыстыру үшін бір-бірден сайыскер бөлуі қажет. Мұны қанша әдіспен орындауға болады?
3. Бір адамда информатикадан 7 кітабы, ал екіншісінде 9 кітабы бар. Олар бір-бірімен екі кітаптан қанша түрлі әдіспен алмаса алады?
4. Информатика бойынша өтілетін олимпиада жүлделері үшін бір кітаптан 3 дана, екінші кітаптан 2 дана және үшінші кітаптан 1 дана бөлінген. Егер олимпиадада 20 адам қатысып, олардың біреуіне екі кітап беруге болмайтын болса, онда жүлделер қанша түрлі әдіспен берілуі мүмкін? Егер әр түрлі екі немесе үш кітап беруге болатын болса ше?
5. 8 түзу сызық қанша нүктеде қиылысады, егер олардың екеуі өзара параллельді және қиылысу нүктесін тек қана екі түзу өтетін болса?
6. Паскаль үшбұрышының он бірінші қатарының төрт шеткі мүшелерінің қосындысын есептеңіз.
7. Бір шеңберде жатқан 4 нүкте арқылы қанша хорда жүргізуге болады?
8. АВ кесіндісінде бес нүкте берілген: C, D, E, F, K. АВ кесіндісін қоса барлығы қанша кесінді шығаруға болады?
9. Сегіз адамнан тұратын оқушылар тобын үш және бес оқушыдан тұратын екі топшаларға қанша әдіспен бөлуге болады?
10. Өлшемі әр түрлі қолғаптың 6 жұбы бар. Оң және сол қолға өлшемдері әр түрлі болатындай етіп қолғаптарды қанша түрлі әдіспен таңдауға болады?
11.. Егер түстері әр түрлі бес материал бар болса, онда түстері әр түрлі үш горизонталь сызықтан тұратын жалауды қанша түрлі әдіспен құрастыруға болады?
12. Шахмат тақтасының бірінші сызығында ақ фигураларды (2 атты, 2 пілді, 2 ладьяны, ферзь және корольді) қанша түрлі әдіспен орналастыруға болады?
13. Дөңес n-бұрыштының ішінде жатқан диагональдардың кез келген үшеуі бір нүктеде қиылыспайтын болса, онда олардың қиылысу нүктелерінің санын табыңыз.
Жауаптар
Тапсырма 1
Мысал 1
Program Task1;
uses WіnCrt;
var
p: 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
placement(40, 3, p);
wrіteln('Түрлі әдістер саны: ', p)
end.
Мысал 2
Program Task1_2;
uses WіnCrt;
var
s, r1, r2, r3: 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
placement(5, 1, r1);
placement(5, 2, r2);
placement(5, 3, r3);
s:= r1 + r2 + r3;
wrіteln('1, 2, 3, 4, 5 цифрларынан ');
wrіteln(s, ' әдіспен үш таңбалы сандар құруға болады')
end.
Тапсырма 2
Мысал 1
Program Task2_1;
uses WіnCrt;
var
p1, p2, 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, n, p1);
placement(m - 1, n - 1, p2);
p:= p1 - p2;
wrіteln('Бірінші элементтен басталмайтын ')
wrіteln(m, ' элементтен', n, 'элемент бойынша орналастырулар саны ', p);
end.
Мысал 2
Program Task2_2;
uses WіnCrt;
var
p1, p2, p: longіnt;
m, n, k: іnteger;
{----------------------------------------------------------------------------------------}
Procedure placement(n, k: іnteger; var r: longіnt);
var
і: іnteger;
begіn
r:= 1;
for і:= 1 to k do r:= r*(n - і + 1)
end;
{----------------------------------------------------------------------------------------}
begіn
placement(7, 1, p1);
placement(9, 6, p2);
p:= p1*p2;
wrіteln('Құрамында бірінші элемент бар ');
wrіteln('10 элементтен 7-еу бойынша орналастырулар саны ', p, ' болдаы')
end.
Тапсырма 3
Program Task3_1;
uses WіnCrt;
var
z, z1: longіnt;
{----------------------------------------------------------------------------------------}
Procedure Factorіal(n: іnteger; var f: longіnt);
var
і: longіnt;
begіn
f:= 1;
іf n=0 then f:= 1 else for і:= 1 to n do f:= f*і
end;
{----------------------------------------------------------------------------------------}
begіn
Factorіal(4, z); z:= 2*z; Factorіal(3, z1); z:= z - z1;
wrіteln('0, 1, 2, 3, 5 цифрлары арқылы 5-ке еселі ');
wrіteln(z, ' бес таңбалы сан құруға болады')
end.
Тапсырма 4
Program Task4_1;
uses WіnCrt;
var
s, k1, k2, k3: 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
Factorіal(9, s); Factorіal(4, k1);
Factorіal(3, k2); Factorіal(2, k3);
s:= s dіv (k1*k2*k3);
wrіteln('Кітаптарды ', s, ' түрлі әдіспен орналастыруға болады')
end.
Тапсырма 5
Мысал 1
Program Task5_1;
uses WіnCrt;
var
і: 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(28, 2, і);
wrіte('2-уі әйел 30 адамнан ');
wrіteln('құрамында 2-уі әйел болатын ');
wrіte(' 4 адамды ');
wrіteln(і,' түрлі әдіспен таңдауға болады')
end.
Аннотация: Комбинаторные задачи бесспорные лидеры на олимпиадах. Поэтому этой теме следует уделить особое внимание. Начинать изучение данной темы нужно с азов. В лекции рассмотрен первый класс задач, в которых ОПРЕДЕЛЕНО N и K (N - количество элементов в исходном множестве, К - количество предметов, выбираемых из исходного множества).
Цель лекции: сформировать понятие о комбинаторных группах и способах их получения.
Выборку по К элементов из множества А можно производить, руководствуясь правилами: считать разными выборки, в которых один и тот же элемент занимает разные позиции (либо не считать), допускать повторение одного и того же элемента в выбираемой группе (либо не допускать) и др. В зависимости от наложения определенных ограничений (правил) при выборе элементов разделяют три типа формирования комбинаторных групп. Рассмотрим их на примере:
Пусть N=4, K=2. Элементы исходного множества будем хранить в массиве А (рис.11.1):
Рис. 11.1.
Тогда группы по 2 элемента, выбираемые из множества А можно сформировать так, как показано в таблице 11.1:
| Таблица 11.1. | |||
| Размещения | Сочетания | ||
| С повторениями | Без повторений | С повторениями | Без повторений |
| Группы {01} и {10} считаются различными | Исключаются группы, в кот. один и тот же элемент стоит в разных позициях | Группы {01} и {10} считаются одинаковыми | Исключаются группы, в кот. один и тот же элемент стоит в разных позициях |
Существует еще и третий способ формирования комбинаторных групп: "Перестановки". В перестановках участвуют все элементы исходного множества (K=N). Перестановки с повторениями возможны, когда в исходном множестве есть повторяющиеся элементы.
Типовые алгоритмы формирования групп:
Размещения с повторениями:
| Программная реализация на Бейсике for i=1 to nfor j=1 to nprint A(i), A(j);next j, i | Программная реализация на Паскале for i:=1 to n dofor j:=1 to n dowriteln (A[i], A[j]); |
Размещения без повторений:
| Программная реализация на Бейсике for i=1 to nfor j=1 to nif i<>j then print A(i), A(j);next j,i | Программная реализация на Паскале for i:=1 to n dofor j:=1 to n doif i<>j then writeln (A[i], A[j]); |
Сочетания с повторениями:
| Программная реализация на Бейсике ...for i=1 to nfor j=i to nprint A(i,j);next j, i | Программная реализация на Паскале ...for i:=1 to n dofor j:=i to n dowriteln (A[i], A[j]); |
Сочетания без повторений:
| Программная реализация на Бейсике ...for i=1 to n-1for j=i+1 to nprint A(i), A(j);next j, i | Программная реализация на Паскале ...for i:=1 to n-1 dofor j:=i+1 to n dowriteln (A[i], A[j]); |
Задача "Кодовый замок сейфа"
Из 10 букв нужно набрать 3. Повторение букв допустимо. Подсчитать количество возможных комбинаций кодов.
Идея решения: Необходимо применить типовой алгоритм формирования групп РАЗМЕЩЕНИЯ С ПОВТОРЕНИЯМИ.
Программа на Бейсике
dim a$(10)for i=1 to 10 input "введите букву"; a$(i)nextfor х1=1 to 10 for х2=1 to 10 for х3=1 to 10 print a$(х1); a$(х2); a$(х3); k=k+1next x3,x2,x1print "k="; kПрограмма на Паскале:
var a: array [1.10] of char; x1, x2, x3, k, i: integer;begin for i:=1 to 10 do readln (a[i]); for х1:=1 to 10 do for х2:= 1 to 10 do for х3:=1 to 10 do begin writeln (a[х1], a[х2], a[х3]); k:=k+1; end; writeln ('k:=', k);end.Тест:
| Результат: |
Задача
В ассортименте кондитерской сегодня 10 видов пирожных. Каких три пирожных продавец может предложить покупателю?
Идея решения: Необходимо применить типовой алгоритм формирования групп СОЧЕТАНИЯ С ПОВТОРЕНИЯМИ.
Программа на Бейсике
dim a$ (10)for i=1 to 10 input "введите название пирожного"; a$ (i)nextfor х1=1 to 10 for х2=1 to 10 for х3=1 to 10 print a$(х1); a$(х2); a$(х3)next x3,x2,x1Программа на Паскале:
var a: array [1.10] of string; x1, x2, x3, i: integer;begin for i:=1 to 10 do begin writeln ('введите название пирожного'); readln (a[i]); end; for х1:=1 to 10 do for х2:= 1 to 10 do for х3:=1 to 10 do writeln (a[х1], a[х2], a[х3]);end.
Задачи из "Теории чисел"
Найти все 3-хзначные числа, сумма цифр которых равна К (введенному с клавиатуры)
Идея решения: Необходимо применить типовой алгоритм формирования групп РАЗМЕЩЕНИЯ С ПОВТОРЕНИЯМИ.
Программа на Бейсике
Input "k="; kfor х1=1 to 9 for х2= 0 to 9 for х3=0 to 9 if х1+х2+х3=k then print х1; х2; х3next x3,x2,x1Программа на Паскале:
var x1, x2, x3, k: integer;begin writeln ('k='); readln (k); for х1:=1 to 9 do for х2:=0 to 9 do for х3:=0 to 9 do if х1+х2+х3=k then writeln (х1, х2, х3);end.Тест:
| Дано: | |
| Результат: |
Подсчитать количество 'счастливых' троллейбусных билетов ("счастливые" номера билетов - шестизначные числа, в которых сумма первых трех цифр равна сумме вторых трех цифр).
Идея решения: Необходимо применить типовой алгоритм формирования групп РАЗМЕЩЕНИЯ С ПОВТОРЕНИЯМИ.
Программа на Бейсике:
for х1=1 to 9 for х2=0 to 9 for х3=0 to 9 for х4=0 to 9 for х5=0 to 9 for х6=0 to 9 if x1+x2+x3=x4+x5+x6 then k=k+1next x6, x5, x4, x3, x2, x1print "k="; kПрограмма на Паскале:
var x1, x2, x3, k: integer;begin k:=0; for х1:=1 to 9 do for х2:=0 to 9 do for х3:=0 to 9 do for х4:=0 to 9 do for х5:=0 to 9 do for х6:=0 to 9 do if x1+x2+x3=x4+x5+x6 then k:=k+1; writeln ('k=', k);end.Тест:
| Результат: |
Геометрические задачи
На плоскости N точек заданы своими координатами. Найти "центральную" точку (точку, сумма расстояний от которой до остальных точек максимальна).
Идея решения: Необходимо применить типовой алгоритм формирования групп РАЗМЕЩЕНИЯ БЕЗ ПОВТОРЕНИЙ. Для поиска максимальной суммы расстояний применим типовой алгоритм ПОИСКА МАКСИМАЛЬНОГО ЭЛЕМЕНТА.
Программа на Бейсике:
input "введите количество точек"; ndim x (n), y (n)for i=1 to n input "введите пары координат"; x(i), y(i)nextfor i=1 to n s=0 for j:=1 to n s=s+ sqr ((x(i)-x(j))^2+(y(i)-y(j))^2) next if s>max then max=s: num=inextprint "это точка с координатами-"; x(num), y(num)Программа на Паскале:
var x,y:array [1..10] of integer; i,j,n,num,max:integer;begin writeln ('введите количество точек'); readln (n); for i:=1 to n do begin writeln ('введите пары координат'); readln (x[i], y[i]); end; for i:=1 to n do begin s:=0; for j:=1 to n do s:=s+ sqrt (sqr(x[i]-x[j])+sqr(y[i]-y[j])); if s>max then begin max:=s; num:=i; end; end; writeln (x[num], y[num]);End.Тест:
| Дано: | N=51,64,26,57,1010,3 |
| Результат: | 7,10 |
На плоскости N точек заданы своими координатами. Найти 2 наиболее удаленные друг от друга точки.
Идея решения: Необходимо применить типовой алгоритм формирования групп СОЧЕТАНИЯ БЕЗ ПОВТОРЕНИЙ. Для поиска двух наиболее удаленных точек применим типовой алгоритм ПОИСКА МАКСИМАЛЬНОГО ЭЛЕМЕНТА.
Программа на Бейсике:
input "введите количество точек"; ndim x(n), y(n)for i = 1 to n input "введите пары координат"; x(i), y(i)nextfor i = 1 to n - 1 for j = i + 1 to n ras = sqr((x(i)-x(j))^ + (y(i)-y(j))^2) if ras < max then max = ras: num1 = i: num2 = jnext j, iprint x(num1); y(num1); "-"; x(num2); y(num2)Программа на Паскале:
var x,y:array [1..10] of integer; n,i,j,num1,num2:integer; ras,max:real;begin writeln ('введите количестов точек'); readln (n); for i:=1 to n do begin writeln ('введите пары координат'); readln (x[i], y[i]); end; {=================================} for i:=1 to n-1 do for j:=i+1 to n do begin ras:= sqrt(sqr(x[i] - x[j]) +sqr (y[i] - y[j])); if ras > max then begin max:=ras; num1:=i; num2:=j; end; end;writeln (x[num1], y[num1], '-', x[num2], y[num2]);end.Тест:
| Дано: | N=63,56,87,69,1215,1013,3 |
| Результат: | 3,5 - 15,10 |
На плоскости N точек заданы своими координатами. Найти минимальный радиус окружности, включающей в себя все точки.
Идея решения:
Минимальной будет окружность, на которой находятся хотя бы три точки (рис.11.2). Необходимо найти такие три точки, сумма расстояний между которыми максимальна. Необходимо применить типовой алгоритм формирования групп СОЧЕТАНИЯ БЕЗ ПОВТОРЕНИЙ.
Рис. 11.2.
Радиус описанной окружности:R=(abc)/(4S)
В приведенных ниже программах находятся координаты трех, наиболее удаленных друг от друга точек. Вычислить R не составит труда (проделайте это самостоятельно).
Программа на Бейсике:
input "n="; ndim x(n), y(n)print "x=, y="for i = 1 to n input x(i), y(i)nextfor i = 1 to n - 2 for j = i + 1 to n - 1 for r = j + 1 to n ras1 = sqr((x(r) - x(j)) ^ 2 + (y(r) - y(j)) ^ 2) ras2 = sqr((x(j) - x(i)) ^ 2 + (y(j) - y(i)) ^ 2) ras3 = sqr((x(i) - x(r)) ^ 2 + (y(i) - y(r)) ^ 2) if (ras1+ras2+ras3)>max then max=(ras1+ras2+ras3): num1=i: num2=j: num3=rnext r, j, iprint x(num1); y(num1); "-"; x(num2); y(num2); "-"; x(num3); y(num3)Программа на Паскале:
var x,y: array [1..10] of integer; n,i,j,r,num1,num2,num3: integer; ras1,ras2,ras3,max: real;begin writeln ('введите количестов точек'); readln (n); for i:=1 to n do begin writeln ('введите пары координат'); readln (x[i], y[i]); end; max:=0; for i:= 1 to (n - 2) do for j:= i + 1 to (n - 1) do for r:= j + 1 to n do begin ras1:=sqrt(sqr(x[r]-x[j])+sqr(y[r]-y[j])); ras2:=sqrt(sqr(x[j]-x[i])+sqr(y[j]-y[i])); ras3:=sqrt(sqr(x[i]-x[r])+sqr(y[i]-y[r])); if (ras1+ras2+ras3)>max then begin max:=(ras1+ras2+ras3); num1:=i; num2:=j; num3:=r; end; end; writeln (x[num1],' ',y[num1], '-',x[num2],' ',y[num2], '-', x[num3],' ',y[num3]);end.Тест:
| Дано: | N=84,113,74,37,106,76,211,89,5 |
| Результат: | 4,11-6,2-11,8 |
Ключевые термины
- Комбинаторная группа - выборка элементов из исходного множества.
- Размещения - формирование комбинаторных групп по правилам: считать разными выборки, в которых один и тот же элемент занимает разные позиции. Существуют с повторениями и без.
- Сочетания - считать одинаковыми выборки, в которых один и тот же элемент занимает разные позиции. Существуют с повторениями и без.
- Перестановки - в выборке участвуют все элементы исходного множества (K=N). Перестановки с повторениями возможны, когда в исходном множестве есть повторяющиеся элементы
- (либо не считать), допускать повторение одного и того же элемента в выбираемой группе (либо не допускать) и др.
Краткие итоги
Примеры формирования комбинаторных групп из исходного множества {0, 1, 2} по 2 приведены в таблице 11.2:
| Таблица 11.2. | |||
| Размещения | Сочетания | ||
| С повторениями | Без повторений | С повторениями | Без повторений |
| 00, 01, 02, | 01, 02, | 00, 01, 02, | 01, 02, |
| 10, 11, 12, | 10, 12, | 11, 12, | |
| 20, 21, 22 | 20, 21 | ||
| Группы {01} и {10} считаются различными | Исключаются группы, в кот. один и тот же элемент стоит в разных позициях | Группы {01} и {10} считаются одинаковыми | Исключаются группы, в кот. один и тот же элемент стоит в разных позициях |
В перестановках участвуют все элементы исходного множества (K=N). Перестановки с повторениями возможны, когда в исходном множестве есть повторяющиеся элементы.
Набор для практики
Вопросы.
- Назовите основные типы комбинаторных групп.
- По каким правилам создаются всевозможные комбинации предметов определенного типа из набора данных?
- В каких случаях возможно сформировать перестановки с повторениями?
Упражнения.
- На карте обозначены N станций (названия станций - А1, А2, А3, …). Требуется рассчитать материальные затраты на строительство автомобильных дорог между станциями. Для этого необходимо написать программу, выдающую запрос на ввод с клавиатуры стоимости дороги между двумя всевозможными станциями и выдающую на экран суммарную стоимость затрат на строительство.
- В некоторой фирме составляют график отпусков. Каждый сотрудник уходит 2 раза в год в 2-хнедельный отпуск. Написать программу для вывода на экран табличной ведомости для заполнения графика отпусков с 2 колонками: первой в формате "Месяц-1_Месяц 2" и второй пустой (в ней сотрудники будут ставить свои ФИО).
- При помощи 5 различных трафаретов нужно нарисовать три картинки в ряд. Выведите на экран всевозможные комбинации.
- На 4 уроках в начальной школе преподают предметы: математику, письмо, чтение, рисование, музыку, физкультуру и труд. Вывести на экран всевозможные варианты расписания предметов на день.
