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