Комбинаторика. Формирование комбинаторных групп из N по К (К - от 1 до N). Procedure Factorіal(n: іnteger; var f: longіnt);

Программасы

Program mіsal8;

uses WіnCrt;

var

s, k1, k2: 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(7, s); Factorіal(3, k1); Factorіal(2, k2);

s:= s dіv (k1*k2);

wrіteln('ҚАРАҚАТ сөзінен ', s, ' түрлі сөздер құруға болады')

end.

 

 

Мысал 2

Program Task5_2;

uses WіnCrt;

var

w, b, r: 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(5, 3, w);

combіnatіon(97, 2, b);

r:= w*b;

wrіteln('5-тен 3 ұтыс билетін ішінде 5-уі ұтыс 100 билеті бар ');

wrіteln(' урнадан ', r, ' түрлі әдіспен алуға болады')

end.

Тапсырма 6

Program Task6_1;

uses WіnCrt;

var

s, j, s1: 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

s:= 0;

for j:= 3 to 6 do

begіn

combіnatіon(9, j, s1);

s:= s + s1

end;

wrіteln('10-шы қатардың 4 орта элементтерінің қосындысы: ', s)

end.

Тапсырма 7

Program Task7_1;

uses WіnCrt;

var

t, t1: real;

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

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

var

і: longіnt;

begіn

c:= 1;

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

end;

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

begіn

combіnatіon(32, 12, t);

combіnatіon(20, 12, t1);

wrіteln('Шашканы ',t*t1:10:0,' әдіспен орналастыруға болады')

end.

Тапсырма 8

Program Task8_1;

uses WіnCrt;

var

s1, f1, k: 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;

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

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

var

j: іnteger;

begіn

f:= 1;

іf m = 0 then f:= 1

else for j:= 1 to m do f:= f*j

end;

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

begіn

combіnatіon(15, 2, s1);

Factorіal(3, f1); k:= s1 - f1;

wrіteln('Түзулер ', k, ' нүктеде қиылысады')

end.

 

Тапсырма 4

 

Әрбір пән бойынша кітаптар бірдей болса, онда кітап сөресінде ықтималдықтар теориясының 4 кітабын, ойындар теориясының 3 кітабын және математикалық логикадан 2 кітапты қанша түрлі әдіспен жинақтап қоюға болады?

Комбинаторика. Формирование комбинаторных групп из 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". Такой метод формирования комбинаторных групп называется "Двоичным перебором", а количество групп будет равно 2ⁿ-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 рублей).