Элементы комбинаторики 2

Комбинаторика

Решение задач

Задачи

Просмотрите алгоритм решения задач

к тесту «Элементы комбинаторики»

• Бусины
• Буквы и слова
• Пароль

Задача про бусины

Для составления цепочек используются бусины, помеченные буквами: X, Y, Z, V, W

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

• На первом месте - одна из бусин X, Y, Z, не стоящая на втором месте.
• В середине цепочки - одна из бусин V, W, Z, которой нет на последнем месте.
• В конце цепочки стоит одна из бусин W, X, Y, Z.

Сколько цепочек можно создать по этому правилу?

Задача про бусины (решение)

Нужно создать цепочку из 3 бусинок:

1. Сколько вариантов бусинок может быть на 1 месте?

X

Y

Z

3 варианта

Задача про бусины (решение)

2. Сколько вариантов бусинок может быть на 2 месте?

Используются буквы V, W, Z

Нужно учесть 1 условие: 1 и 2 буквы не должны совпадать.

V

W

Z

X

Y

Z

V

W

Z

V

W

W

X

Y

W

X

Y

Задача про бусины (решение)

3. Сколько вариантов бусинок может быть на 3 месте?

Используются буквы W, X, Y, Z.

Нужно учесть 2 условие: на 2 и 3 месте буквы не должны совпадать.

W

X

Y

Z

V

W

Z

X

Y

Z

X

Y

Z

Всего 10 вариантов

W

X

Y

Z

V

W

Z

X

Y

Z

Всего 10 вариантов

W

X

Y

Z

Всего 7 вариантов

V

W

X

Y

Z

Ответ: 10+10+7 = 27 вариантов

Задача про буквы и слова

Некоторый алфавит содержит буквы Г, Д, З.

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

(Пример решения задачи см. Учебник стр. 29 Задача 4)

Перейдем к решению.

Задача: буквы и слова (решение)

Решение

Под «слова» понимаются сочетание букв.

1. Сколько вариантов букв может быть на 1 месте? = 3 варианта

2. Сколько вариантов букв может быть на 2 месте? = 3 варианта

3. Сколько вариантов букв может быть на 3 месте? = 3 варианта

4. Сколько вариантов букв может быть на 4 месте? = 3 варианта

5. Сколько вариантов букв может быть на 5 месте? = 3 варианта

4. Сколько вариантов всего? Используем правило произведения (учебник стр. 28 ). В итоге получится 3*3*3*3*3= 243 слов

Ответ : 243

При решении подобных задач можно пользоваться формулой, определяющей максимально возможное количество комбинаций (слов) фиксированной длины определённого алфавита:

M= N k M = 3 5 = 243

M – максимально возможное количество слов;

N – количество символов в (мощность) алфавите;

k - длина слова (количество символов в слове).

Задача про буквы и слова

Сколько слов длины 4, заканчивающихся согласной буквой, можно составить из букв Л, Е, В?

Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Перейдем к решению.

1. Сколько вариантов букв может быть на 1 месте? = 3 варианта

2. Сколько вариантов букв может быть на 2 месте? = 3 варианта

3. Сколько вариантов букв может быть на 3 месте? = 3 варианта

4. Сколько вариантов букв может быть на 4 месте? = 2 варианта (согласных две – Л и В)

4. Сколько вариантов всего? Используем правило произведения (учебник стр. 28 ). В итоге получится 3*3*3* 2 = 54 слов

Ответ : 54

Задача про пароль

Для регистрации на сайте некоторой страны пользователю необходимо придумать пароль длиной ровно 10 символов.

В пароле можно использовать только прописные буквы английского алфавита, т.е. 26 символов.

Каждый символ в пароле кодируется одинаковым и минимально возможным количеством бит.

Информация о пользователе хранится с помощью минимально возможного целого количества байт.

Для хранения дополнительной информации на одного пользователя отводится 15 байт.

Определите объем памяти в байтах, необходимый для хранения информации о 50 пользователях.

Перейдем к решению (см. Учебник стр. 30 Задача 5)

Задача про пароль (решение)

Подсчитаем информационный объем пароля для одного пользователя:

Решение.

K = 10

N = 26

______

I - ?

Используем две формулы: I = K*i N = 2 i

N = 2 i = 26 Для кодирования 1 символа при алфавите в 26

Тогда информационный вес 1 символа пароля i = 5 бит

Тогда информационный объем пароля для 1 пользователя I = 10 * 5 = 50 бит /8 = 6, 25 байт

По задаче «Информация о пользователе хранится с помощью минимально возможного целого количества байт » .

Поэтому информационный объем пароля округляем с избытком

6, 25 байт  7 байт

На каждого пользователя также хранится дополнительная информация на одного пользователя отводится 15 байт

7+15 = 22 байта

Тогда на всех пользователей информационный объем

I = 22 * 50 = 1100 байт

Ответ: 1100