Задание 4 ЕГЭ: суммарная длина кодов букв

Условие Фано: суммарная длина кодов букв. Тема номера — условие фано. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 11, Д – 10, Е – 01, З – 000. Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв? В ответе укажите суммарную длину кодов букв Б, В, Г и Ж.

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

Решение

Слова здесь нет, поэтому минимизируем просто сумму длин кодов неизвестных букв. По дереву известных кодов свободны ветки 001, а букв 4 — значит, какие-то ветки придётся делить. Выгоднее делить короткую ветку: деление ветки длины d на две добавляет d + 2 знака.

Оптимальный вариант: Б – 00100, В – 00101, Г – 00110, Ж – 00111. Сумма: 5 + 5 + 5 + 5 = 20.

Проверка перебором всех кодов длиной до 6 знаков:

from itertools import product

known = {"А": "11", "Д": "10", "Е": "01", "З": "000"}
unknown = "БВГЖ"
codes = ["".join(p) for n in range(1, 7) for p in product("01", repeat=n)]

def fano(c, used):   # c не начало другого кода и другой код не начало c
    return all(not a.startswith(c) and not c.startswith(a) for a in used)

best = None

def search(i, used, total):
    global best
    if best is not None and total >= best:   # уже не лучше найденного
        return
    if i == len(unknown):
        best = total
        return
    for c in codes:
        if fano(c, used):
            search(i + 1, used + [c], total + len(c) * 1)

search(0, list(known.values()), 0)
print(best)

Решить такую задачу — новый вариант с проверкой