По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: А — 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