ЕГЭ · ЗАДАНИЕ 4
Кодирование и условие Фано · №27272
Передаются имена переменных A, B, C и знаки +, −, *, /. Известны A = 1100, B = 1011, C = 100. Найдите минимальную суммарную длину кодов четырёх знаков действий.
| Символ | Кодовое слово |
|---|---|
| A | 1100 |
| B | 1011 |
| C | 100 |
| + | ? |
| − | ? |
| * | ? |
| / | ? |
Напоминание: ни одно кодовое слово не должно быть началом другого кодового слова.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 11
1. Разберём свободные ветви
Из-за A = 1100, B = 1011 и C = 100 нельзя брать коды 10 и 11. Под ветвью 1 остаются свободные 111, 1010 и 1101. Ветвь 0 пока свободна полностью.
2. Построим подходящий набор
| Знак | Один из допустимых кодов | Длина |
|---|---|---|
| + | 00 | 2 |
| − | 01 | 2 |
| * | 111 | 3 |
| / | 1010 | 4 |
Проверяем условие Фано среди новых и известных кодов. Всё допустимо. Получаем 2 + 2 + 3 + 4 = 11.
3. Исключим меньшую сумму
С однобитовым кодом 0 минимальные длины остальных трёх — 3, 4 и 4: сумма не меньше 12.
Без него все длины не меньше 2. Сумма 10 потребовала бы двух кодов длины 2 и ещё двух длины 3. Но двухбитовые коды могут быть только 00 и 01; после их выбора под ветвью 1 свободен только один трёхбитовый код — 111. Поэтому второму оставшемуся знаку нужно минимум 4 бита. Нижняя граница равна 11 и достигнута.
Частая ошибка: использовать 101 вместе с B = 1011 — короткий код стал бы началом длинного.
Самопроверка. Закройте разбор и повторите расчёт без подсказки.