Тапсырма 7. Шахмат татасыны 32 ара рістерінде 12 а жне 12 ара шашкаларды анша діспен орналастыруа болады?

Осымша сабатар шін

 

Мысал 14. 210 саныны барлыы анша блгіші бар? 30030 санында ше? N бтін санында ше?

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

p1, ..., pm – q саныны р трлі арапайым блгіштері болсын. Егер болса, мндаы - андай да бір натурал сандар, онда q саныны барлы блгіштер саны (1 мен q-ды оса) a1, a2, ..., am дреже крсеткіштеріні айталанбалы терулер санына те. Ал ол з кезегінде туындысына те.

Программаны ру алгоритмі тмендегідей болуы ммкін:

  1. 2-ге блінетін арапайым блгіштер саны аныталады.
  2. Бл блгіштер саны 1-ге арттырылып, s айнымалысына меншіктеледі.
  3. Та арапайым блгіштер саны аныталады.
  4. рбір арапайым блгіш шін оларды саны орнатылады да 1-ге арттырылады жне s-ке кбейтіледі.
  5. Нтижеде барлы блгіштер саны экрана шыарылады.

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 уроках в начальной школе преподают предметы: математику, письмо, чтение, рисование, музыку, физкультуру и труд. Вывести на экран всевозможные варианты расписания предметов на день.