№ 9735 Основная волна 19.06.23 (Уровень: Базовый)

По каналу связи передаются шифрованные сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, З. Для передачи используется неравномерный двоичный код. Для шести букв используются кодовые слова.

Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?

В ответе запишите суммарную длину кодовых слов для букв: А; Б.

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

1. Строим бинарное (двоичное) дерево

В любом прототипе задания №4 построение бинарного дерева - это наш первый шаг.

В большинстве задач нам хватит дерева глубины 3-4.

2. Вчитываемся в условие задачи

По условию Фано, никакой код не может быть началом другого кода.

Например, мы не можем закодировать какую-либо букву как 110, т.к. буква Д имеет код 11. Для удобства советуем сразу зачёркивать те ветки, которые мы не сможем использовать из-за условия Фано.

Переносим данные из условия на наше дерево и зачеркиваем ненужные нам ветки: