БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра программного обеспечения информационных технологий
Факультет ФКСиС Специальность ПОИТ
Индивидуальная практическая работа №1
по дисциплине «Дискретная математика»
тема: «Элементы комбинаторики»
Вариант 4
Выполнил студент: Бордон Е.С. группа 991051 Зачетная книжка № 99105004
Минск 2020
Задание 1.
Сколькими способами из колоды в 36 карт можно выбрать неупорядоченный набор из 4-х карт так, чтобы в этом наборе было бы в точности:
4 |
3 дамы, 2 крестовые карты |
|
|
Так как в колоде есть только 1 крестовая дама, существует только одно подмножество для решения задачи
•1 крестовая дама – 1;
•2 дамы – С32=3;
•1 крестовая карта (не дама) – 8;
Общее число способов выбора 4-х карт, удовлетворяющих условию задачи равно: 1 * 3 * 8 = 24;
Ответ: 24.
Задание 2.
Дано множество А (см. таблицу ниже).
Для каждого пункта, указанного ниже, нужно найти количество объектов, а также получить сами соответствующие объекты.
1)Сколькими способами из множества А можно выбрать 2 различные цифры?
2)Сколько различных трехзначных чисел можно записать из цифр, входящих
вмножество А (цифры в записи числа могут повторяться)?
3)Сколько различных трехзначных чётных (нечётных) чисел можно записать из цифр, входящих в множество А (цифры в записи числа могут повторяться)?
4)Сколько различных трехзначных чисел можно записать из цифр, входящих
вмножество А (все цифры в записи числа различны)?
5)Сколько различных трехзначных чётных (нечётных) чисел можно записать из цифр, входящих в множество А (все цифры в записи числа различны)?
4 |
{0,2,3,6} |
|
|
1. Сколькими способами из множества А можно выбрать 2 различные цифры?
2 |
= |
4! |
= 6. |
|
|||
|
|||
4 |
|
2!(4−2)! |
|
|
|
|
{{0,2}, {0,3}, {0,6}, {2,3}, {2,6}, {3,6}}
2. Сколько различных трехзначных чисел можно записать из цифр, входящих в множество А (цифры в записи числа могут повторяться)?
3 * 4 * 4 = 48;
(A\ {0}) x A x A = {2,3,6} x {0,2,3,6} x {0,2,3,6} =
{(2,0,0), (2,0,2), (2,0,3), (2,0,6), (2,2,0), (2,2,2), (2,2,3), (2,2,6), (2,3,0), (2,3,2), (2,3,3), (2,3,6), (2,6,0), (2,6,2), (2,6,3), (2,6,6), (3,0,0), (3,0,2), (3,0,3), (3,0,6), (3,2,0), (3,2,2), (3,2,3), (3,2,6), (3,3,0), (3,3,2), (3,3,3), (3,3,6), (3,6,0), (3,6,2), (3,6,3), (3,6,6), (6,0,0), (6,0,2), (6,0,3), (6,0,6), (6,2,0), (6,2,2), (6,2,3), (6,2,6),
(6,3,0), (6,3,2), (6,3,3), (6,3,6), (6,6,0), (6,6,2), (6,6,3), (6,6,6)}.
3. Сколько различных трехзначных чётных (нечётных) чисел можно записать из цифр, входящих в множество А (цифры в записи числа могут повторяться)?
Нечетные:
Последняя цифра выбирается из подмножества {1} множества А.
3 * 4 * 1 = 12;
(A\{0}) x A x {1} = {2,3,6} x {0,2,3,6} x {1} = {(2,0,1), (2,2,1), (2,3,1), (2,6,1), (3,0,1), (3,2,1), (3,3,1), (3,6,1), (6,0,1), (6,2,1), (6,3,1), (6,6,1)}.
Четные:
Последняя цифра выбирается из подмножества {0,2,6} множества А.
3 * 4 * 3 = 36;
(A\{0}) x A x {0,2,6} = {2,3,6} x {0,2,3,6} x {0,2,6} ={ (2,0,0), (2,0,2), (2,0,6), (2,2,0), (2,2,2), (2,2,6), (2,3,0), (2,3,2), (2,3,6), (2,6,0), (2,6,2), (2,6,6), (3,0,0), (3,0,2), (3,0,6), (3,2,0), (3,2,2), (3,2,6), (3,3,0), (3,3,2), (3,3,6), (3,6,0), (3,6,2), (3,6,6), (6,0,0), (6,0,2), (6,0,6), (6,2,0), (6,2,2), (6,2,6), (6,3,0), (6,3,2), (6,3,6), (6,6,0), (6,6,2), (6,6,6) }
4.Сколько различных трехзначных чисел можно записать из цифр, входящих
вмножество А (все цифры в записи числа различны)?
3* 3 * 2 = 18;
{2} x ({0} x {3, 6} {3} x {0, 6} {6} x {0, 3})
{3} x ({0} x {2, 6} {2} x {0, 6} {6} x {0, 2})
{6} x ({0} x {2, 3} {2} x {0, 3} {3} x {0, 2}) =
={(2,0,3), (2,0,6), (2,3,0), (2,3,6), (2,6,0), (2,6,3)}{(3,0,2), (3,0,6), (3,2,0), (3,2,6), (3,6,0), (3,6,2)}{(6,0,2), (6,0,3), (6,2,0), (6,2,3), (6,3,0), (6,3,2)} =
={ (2,0,3), (2,0,6), (2,3,0), (2,3,6), (2,6,0), (2,6,3), (3,0,2), (3,0,6), (3,2,0), (3,2,6), (3,6,0), (3,6,2), (6,0,2), (6,0,3), (6,2,0), (6,2,3), (6,3,0), (6,3,2) }.
5. Сколько различных трехзначных чётных (нечётных) чисел можно записать из цифр, входящих в множество А (все цифры в записи числа различны)?
Нечетные:
1 * 2 * 2 = 4;
{2} x {0,6} x {3} {6} x {0,2} x {3} = {(2,0,3), (2,6,3), (6,0,3), (6,2,3)}
Четные:
Если последняя цифра 2 или 6: 2 * 2 * 1 = 4 Если последняя цифра 0: 3 * 2 * 1 = 6 Общее количество возможных чисел: 4+4+6=14
{2} x {3,6} x {0} {2} x {0,3} x {6}
{3} x {2,6} x {0} {3} x {0,6} x {2} {3} x {0,2} x {6}
{6} x {2,3} x {0} {6} x {0,3} x {2} =
= { (2,3,0), (2,6,0), (2,0,6), (2,3,6), (3,2,0), (3,6,0), (3,0,2), (3,6,2), (3,0,6), (3,2,6), (6,2,0), (6,3,0), (6,0,2), (6,3,2) }
Задание 3.
Написать программу для получения из заданных элементов (см. таблицу ниже) всех сочетаний заданной длины k с повторениями элементов.
№ |
Набор элементов |
|
|
4 |
aaa b cc dd |
|
|
Программа написана на языке pascal в программной среде Lazarus.
В программе реализована генерация сочетаний задаваемой длинны K из элементов a,b,c,d также задаваемой длины. Реализовано сохранение в текстовый файл результатов работы программы.
Рис 1. Схема работы программы
Процедура генерации всех возможных комбинаций, удаления лишних и внесения результатов в ListBox:
procedure TForm1.Difficult(Sender: TObject); // Сортировка и вывод var
sl :TStringList; |
|
procedure Gen(S0,S1 : string); |
|
var |
|
i,j: integer; |
|
s: string; |
|
c:char; |
|
begin |
|
if length(S1) > 1 then |
// Генерация всех возможных перестановок |
for i:=1 to length(S1) do |
|
Gen(S0+S1[i],copy(S1,1,i-1) + copy(S1,i+1,length(S1))) // S0 увеличивается на 1, S1 |
|
уменьшается |
|
else |
|
begin |
|
s:= copy(S0+S1,1,k_count); |
// Обрезаем результат до длины K |
for i:=1 to k_count-1 do |
// Сортируем по алфавиту элементы |
for j:=i+1 to k_count do if ord(s[i])>ord(s[j]) then begin
c:=s[i];
s[i]:=s[j];
s[j]:=c;
end; //Добавляем в Stringlist sL.Add(s);
end;
end;
begin
sL:= TStringList.Create; sL.Sorted:= True;
sL.Duplicates:= dupIgnore; // Удаление всех дубликатов Gen('',n_s_count);
ListBox1.Items.Assign(sL);
sL.Free;
Label17.Caption:= 'Число сочетаний: ' + IntToStr(Form1.ListBox1.Items.Count); end;
Результаты работы программы:
