Файл: Решение. Разобьем множество всех возможных выборок, удовлетворяющих заданному условию, на два непересекающихся подмножества.docx

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.12.2023

Просмотров: 17

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Задание 1. Сколькими способами из колоды в 36 карт можно выбрать неупорядоченный набор из 4-х карт так, чтобы в этом наборе было бы в точности 2 карты красной масти, 2 туза?

Решение.

Разобьем множество всех возможных выборок, удовлетворяющих заданному условию, на два непересекающихся подмножества.

Среди четырех выбранных карт

2 туза черной масти и 2 карты красной масти

2 туза красной масти и 2 карты черной масти

Количество способов выбрать:

  • 2 туза черной масти – 1;

  • 2 карты красной масти (не тузы красной масти) – = 120.

  • 2 туза красной масти – 1;

  • 2 карты черной масти (не тузы черной масти) – = 120.

Число выборок заданной структуры равно:

1* = 1*120 = 120.

1* = 1*120 = 120.

Общее число способов выбора 4-х карт, удовлетворяющих условию задачи, составляет:

120+120 = 240.

Задание 2. Дано множество А = {0, 3, 8, 9}.

Для каждого пункта, указанного ниже, нужно найти количество объектов, а также получить сами соответствующие объекты.

  1. Сколькими способами из множества А можно выбрать 2 различные цифры?

  2. Сколько различных трехзначных чисел можно записать из цифр, входящих в множество А (цифры в записи числа могут повторяться)?

  3. Сколько различных трехзначных чётных (нечётных) чисел можно записать из цифр, входящих в множество А (цифры в записи числа могут повторяться)?

  4. Сколько различных трехзначных чисел можно записать из цифр, входящих в множество А (все цифры в записи числа различны)?

  5. Сколько различных трехзначных чётных (нечётных) чисел можно записать из цифр, входящих в множество А (все цифры в записи числа различны)?


Решение.

Дано множество А = {0, 3, 8, 9}.

  1. Сколькими способами из множества А можно выбрать 2 различные цифры?

.

Получим сами сочетания:

{{0,9}, {0,8}, {0,3}, {3,9}, {3,8}, {8,9}}.

  1. Сколько различных трехзначных чисел можно записать из цифр, входящих в множество А (цифры в записи числа могут повторяться)?

3*4*4=48.

Получим эти числа в виде векторов (кортежей):

(A\{0}) A×A = {3, 8, 9} × {0, 3, 8, 9} × {0, 3, 8, 9} =

= {(3,0,0), (3,0,3), (3,0,8), (3,0,9), (3,3,0), (3,3,3), (3,3,8), (3,3,9), (3,8,0), (3,8,3), (3,8,8), (3,8,9), (3,9,0), (3,9,3), (3,9,8), (3,9,9), (8,0,0), (8,0,3), (8,0,8), (8,0,9), (8,3,0), (8,3,3), (8,3,8), (8,3,9), (8,8,0), (8,8,3), (8,8,8), (8,8,9), (8,9,0), (8,9,3), (8,9,8), (8,9,9), (9,0,0), (9,0,3), (9,0,8), (9,0,9), (9,3,0), (9,3,3), (9,3,8), (9,3,9), (9,8,0), (9,8,3), (9,8,8), (9,8,9), (9,9,0), (9,9,3), (9,9,8), (9,9,9)}.

Полученных кортежей, соответствующих заданным трехзначным числам, действительно 48.

  1. Сколько различных трехзначных нечетных чисел можно записать из цифр, входящих в множество А (цифры в записи числа могут повторяться)?

Здесь последняя цифра выбирается из подмножества {3,9} множества A. Имеем:

3*4*2= 24.

Получим соответствующие числа.

(A\{0}) ×A× {3, 9} = {3, 8, 9} × {0, 3, 8, 9} × {3, 9} =

={(3,0,3), (3,0,9), (3,3,3), (3,3,9), (3,8,3), (3,8,9), (3,9,3), (3,9,9), (8,0,3), (8,0,9), (8,3,3), (8,3,9), (8,8,3), (8,8,9), (8,9,3), (8,9,9), (9,0,3), (9,0,9), (9,3,3), (9,3,9), (9,8,3), (9,8,9), (9,9,3), (9,9,9).

Сколько различных трехзначных четных чисел можно записать из цифр, входящих в множество А (цифры в записи числа могут повторяться)?

Здесь последняя цифра выбирается из подмножества {0, 2} множества A. Имеем:

3*4*2=24.

Получим соответствующие числа.

(A\{0}) ×A× {3, 9} = {3, 8, 9} × {0, 3, 8, 9} × {0, 8} =

={(3,0,0), (3,0,8), (3,3,0), (3,3,8), (3,8,0), (3,8,8), (3,9,0), (3,9,8), (8,0,0), (8,0,8), (8,3,0), (8,3,8), (8,8,0), (8,8,8), (8,9,0), (8,9,8), (9,0,0), (9,0,8), (9,3,0), (9,3,8), (9,8,0), (9,8,8), (9,9,0), (9,9,8).

  1. Сколько различных трехзначных чисел можно записать из цифр, входящих в множество А (все цифры в числе различны)?

Первая цифра числа выбирается из множества A\{0} (3 варианта). После выбора первой цифры один из элементов множества A\{0} уже использован и не может быть повторно выбран, но зато элемент 0 возвращается в рассмотрение – его можно использовать в качестве второй цифры. Таким образом, для выбора второй цифры также есть 3 возможности. К моменту выбора третьей цифры, две цифры из имеющихся четырёх уже выбраны. Поэтому остается 2 возможности выбрать третью цифру. Имеем:

3*3*2=18.

Получим эти 18 чисел в виде кортежей.

{3} × ({0}×{8, 9} ∪ {8}×{0, 9} ∪ {9}×{0, 8}) ∪

∪{8} × ({0}×{3, 9} ∪ {3}×{0, 9} ∪ {9}×{0, 3}) ∪



∪ {9} × ({0}×{3, 8} ∪ {3}×{0, 8} ∪ {8}×{0, 3}) =

= {3}×{0}×{8, 9} ∪ {3}×{8}×{0, 9} ∪ {3}×{9}×{0, 8} ∪

∪ {8}×{0}×{3, 9} ∪ {8}×{3}×{0,9} ∪ {8}×{9}×{0, 3} ∪

∪ {9}×{0}×{3, 8} ∪ {9}×{3}×{0, 8} ∪ {9}×{8}×{0, 3} =

= {(3,0,8), (3,0,9), (3,8,0), (3,8,9), (3,9,0), (3,9,8)} ∪

∪ {(8,0,3), (8,0,9), (8,3,0), (8,3,9), (8,9,0), (8,9,3)} ∪

∪ {(9,0,3), (9,0,8), (9,3,0), (9,3,8), (9,8,0), (9,8,3)} =

= {(3,0,8), (3,0,9), (3,8,0), (3,8,9), (3,9,0), (3,9,8), (8,0,3), (8,0,9), (8,3,0), (8,3,9), (8,9,0), (8,9,3), (9,0,3), (9,0,8), (9,3,0), (9,3,8), (9,8,0), (9,8,3)}.

  1. Сколько различных трехзначных нечётных чисел можно записать из цифр, входящих в множество А (все цифры в числе различны)?

Последнюю цифру можно выбрать двумя способами из множества {3, 9}. Для выбора первой цифры остается множество {8} и один (не выбранный) элемент множества {3, 9} (т.е. всего две возможности). К моменту выбора третьей цифры остается два невыбранных элемента множества А, т.е. тоже две возможности. Имеем:

2*2*2=8.

Формируем выражение, позволяющее получить искомые числа, в виде кортежей:

Числа вида 3_9: {3} × {0, 8} × {9}

Числа вида 8_3 и 8_9: {8} × ({0} × {3, 9} ∪ {3} × {9} ∪ {9} × {3})

Числа вида 9_3: {9} × {0, 8} × {3}

{3} × {0, 8} × {9}∪{{8} × ({0} × {3, 9} ∪ {3} × {9} ∪ {9} × {3}) ∪{{9} × {0, 8} × {3} =

= {(3, 0, 9), (3, 8, 9), (8, 0, 3), (8, 0, 9), (8, 3, 9), (8, 9, 3), (9, 0, 3), (9, 8, 3)}.

Сколько различных трехзначных чётных чисел можно записать из цифр, входящих в множество А (все цифры в числе различны)?

Последнюю цифру можно выбрать двумя способами – из множества {0,8}. Разобьем множество всех чисел, удовлетворяющих заданным условиям, на два непересекающихся подмножества: в первое подмножество входят все числа, заканчивающиеся на 8 (вида __8),

а во второе – все числа, заканчивающиеся на 0 (вида __ 0).

Для чисел из первого подмножества первую цифру можно выбрать двумя способами (из множества {3, 9}), тогда вторую – тоже двумя способами (0 и одна из оставшихся цифр: 3 или 9). Таким образом, количество чисел в первом подмножестве равно 2*2*1 = 4.

Для чисел из второго подмножества первую цифру можно выбрать тремя способами (из множества {3, 8, 9}), а вторую – двумя способами (из двух элементов множества {3, 8, 9}, которые остались после выбора первой цифры). Таким образом, количество чисел во втором подмножестве равно 3*2*1 = 6.

По правилу суммы получаем общее количество возможных чисел: 4 + 6 = 10, и сами числа:

({3} × {0, 9} ∪ {9} ×{0, 3}) × {8} ∪ ({3} × {8, 9} ∪ {8} × {3, 9} ∪ {9} × ×{3, 8}) × {0} =

= {(3, 0, 8), (3, 9, 8), (9, 0, 8), (9, 3, 8), (3, 8, 0), (3, 9, 0), (8, 3, 0), (8, 9, 0), (9, 3, 0), (9, 8, 0)}.

Задание 3. Написать программу для получения из заданных элементов


всех сочетаний заданной длины k с повторениями элементов.

Листинг кода:

#include

using namespace std;
bool next_comb(int index[], const int& n, const int& m)

{

int j = m - 1;

while (index[j] == n && j >= 0)

j--;

if (j < 0)

return false;

if (index[j] >= n)

j--;

index[j]++;

if (j == m - 1)

return true;

for (int k = j + 1; k < m; k++)

index[k] = index[j];

return true;

}
int main()

{

setlocale(LC_ALL, "rus");

string char_set[] = { "aa", "bb", "cc", "dd"};

int N = sizeof(char_set) / sizeof(char_set[0]);

for (int i = 0; i < N; ++i)

std::cout << char_set[i] << " ";

std::cout << std::endl;

int n;

cin >> n;

int k = N > n ? N : n;

int* index = new int[k];

for (int i = 0; i < k; i++)

index[i] = 1;

do

{

for (int i = 0; i < n; ++i)

std::cout << char_set[index[i] - 1] << " ";

std::cout << std::endl;

} while (next_comb(index, N, n));

delete[] index;

//std::cin.get();
}

Пример работы программы: