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