Тур 1 Вариант 1 Задача 4 "Детали"

Задача 4

Детали обозначаются трехзначными символьными конструкциями. Есть два способа записи в памяти отдельной конструкции. Один из способов – записывать в память код каждого символа независимо, используя для него минимально возможное количество бит. Второй способ – записывать в память уникальный код каждой конструкции, опять же используя для этого минимально возможное количество бит.

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

В ответе укажите целое число.

Решение:

Мощность алфавита – это количество символов в этом алфавите. Если алфавит имеет мощность К, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно  Q=K^N.

С помощью М бит можно закодировать 2^М различных вариантов (чисел).

1)    Посчитаем количество бит, необходимых для кодирования  детали первым и вторым способом, при К=2, используется набор из двух разных символов При первом способе каждый символ кодируется 1 битом. 2¹=2.  3·1=3, т.е. вся конструкция кодируется 3 битами. При втором способе, количество деталей, которые можно закодировать 2³ = 8. Для кодирования необходимо 3 бита. В первом случае требуется столько же бит информации для записи обозначения одной детали, сколько и во втором случае.

2)  Продолжим:

К=	Способ 1	Способ 2	Разница
3 4	3·2=6	33 = 27 < 25 43 = 26	6 − 5 = 1 6 − 6 = 0
5	3·3=9	53 = 125 < 27	9 − 7 = 2

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

Ответ: 5.