РЕШУ ЕГЭ — информатика

Задания

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: А  — 0, Б  — 1111, В  — 1010. Найдите код минимальной длины для буквы Г. Если таких кодов несколько, укажите код с минимальным числовым значением.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Решение. Заметим, что кодовые слова 0 и 1 выбрать нельзя. Заметим, что нельзя выбирать кодовые слова начинающиеся на 0 по условию Фано. Также нельзя использовать кодовые слова 10 и 11, так как они являются началом кодовых слов Б  — 1111 и В  — 1010 соответственно. Далее идут свободные кодовые слова длиною 3  — 100 и 110. 101 не подходит, так как является началом кодового слова 1010 (В), 111 не подходит, так как является началом кодового слова 1111 (Б). Минимальное числовое значение у кодового слова 100.

Ответ: 100.

Приведём решение Евгения Джобса (построение двоичного дерева).

Заметим несколько свободных префиксов: 100, 1011, 110 и 1110. Выбираем префикс с минимальным числовым значением.

Приведём решение Евгения Джобса на языке Python.

codes = ['0', '1010', '1111']

# длина префиксов от 1 до 4

for i in range(1, 5):

# все префиксы, как двоичные числа

for x in range(2**i):

pfx = bin(x)[2:].zfill(i)

# если префикс не является началом сущ.кода

# и сущ.коды не являются началом префикса

if all(c[:i] != pfx and pfx[:len(c)] != c

for c in codes):

print(pfx)

break

№ п/п	№ задания	Ответ
1	55800	100

Ключ