Минимальная длина двоичного кода
По каналу связи передаются сообщения, содержащие только буквы из набора А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Н — 1111, З — 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если оно закодировано минимально возможным количеством двоичных знаков?
Условие как в банке ФИПИ — открыть и сверить
| По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков? | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Подсчитайте, сколько раз каждая буква встречается в слове КАЗАЧКА.
2Наводящая — какие числа считатьуровень 2 из 3
Чтобы общая длина была минимальной, более часто встречающимся буквам назначают более короткие кодовые слова, сохраняя условие Фано.
3Прямая — фактически решениеуровень 3 из 3
В слове буква К встречается 2 раза, А — 3 раза, З и Ч — по 1 разу. Минимальная суммарная длина кодирования равна $2 \cdot 1 + 3 \cdot 2 + 1 \cdot 3 + 1 \cdot 3 = 14$.