Teacher & coder

Задача № 163

По каналу связи передаются сообщения, содержащие только буквы: Е, М, А, Т, К, И, Л. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: И — 00, Т — 010, К — 0110, Е — 10.

Для оставшихся букв А, Л и М кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования слова МАТЕМАТИКА?

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

Можно скопировать и вставить все ответы сразу
ЕГКР 27 апреля 2024 года (Московский пробник)
Прокрути, чтобы прочитать решение задачи
Ты уверен, что хочешь это сделать?
Удачного чтения!

Решение

Код из видео

# подключаем стандартные библиотеки
from itertools import product

# коды из условия задачи
codes = '00 010 0110 10'.split()
# все коды, длина которых от 1 до 4 символов
all_codes = [''.join(x) for i in range(1, 5) for x in product('01', repeat=i)]

# выводм коды из условия задачи
print(codes)

# перебираем все коды
for code1 in all_codes:
    # для каждого проверяем уже имеющиеся коды
    for code2 in codes:
        # если какой-то код является начлом другого, то прерываем цикл
        if code1.startswith(code2) or code2.startswith(code1):
            break
    # если цикл не прерван, то сохраняем код себе
    else:
        codes.append(code1)

# выводим все коды: из условия + свободные
print(codes)

Артём Зинкин

Лучше не гуглить и подумать самостоятельно. Тест можно пройти несколько раз :)
Чтобы поделиться задачей с коллегами или друзьями, отправьте им ссылку :)
Забыл сказать, что у этой задачи есть подробное решение. Посмотрите его :)
Попробуйте решить эту задачу сами и посмотрите наши разборы похожих задач :)
Кстати, на ЕГЭ тоже нельзя копировать :)
Этим материалом удобно поделиться по прямой ссылке :)