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

Задания

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

№ п/п	№ задания	Ответ
1	81788	16

Ключ