По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Е — 10, Ж — 010, З — 011, Д —11. Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Перечислим возможные коды в порядке возрастания длины.
0 — нельзя, так как использованы коды 010 и 011.
1 — нельзя, так как использованы коды 11 и 10.
00 — нельзя, так как не останется свободных кодов под оставшиеся буквы.
01 — нельзя, так как использованы коды 010 и 011.
10 — нельзя, это Е.
11 — нельзя, это Д.
Так как осталось закодировать 4 буквы можно использовать коды 0000, 0001, 0010, 0011. Тогда наименьшее количество двоичных знаков требующихся для кодирования оставшихся букв 4 + 4 + 4 + 4 = 16.
Примечание. Если использовать код 000 или 001 для одной из букв, суммарное количество двоичных знаков для оставшихся букв будет больше.
Ответ: 16.
Приведём решение Александра Козлова на языке Python.
def bin_cod(leng):
return [bin(i)[2:].zfill(leng) for i in range(2 ** leng)]
# Проверка условия Фано
def fano(codes):
for code in codes:
for other_code in codes:
if code != other_code and other_code.startswith(code):
return False
return True
def itog():
cod = ['10', '010', '011', '11'] # Известные коды
bukv = 8 # Всего букв
ostalos = bukv - len(cod) # Оставшиеся буквы
min_len = 0
for leng in range(1, 5): # Проверяем длины кодов от 1 до 4
codes = bin_cod(leng)
doctupnie = [code for code in codes if code not in cod]
if len(doctupnie) >= ostalos: # Проверяем на выполнение условия Фано
if fano(doctupnie)> 0:
min_len = ostalos * leng
return min_len
print("Суммарная длина кодовых слов для букв А, Б, В, Г:", itog())