Найдите код минимальной длины для буквы Г.
Условие
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: А — 0, Б — 1111, В — 1010. Найдите код минимальной длины для буквы Г. Если таких кодов несколько, укажите код с минимальным числовым значением. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Ответ
100
Решение по шагам
Как рассуждать
Решение. Заметим, что кодовые слова 0 и 1 выбрать нельзя. Заметим, что нельзя выбирать кодовые слова начинающиеся на 0 по условию Фано. Также нельзя использовать кодовые слова 10 и 11, так как они являются началом кодовых слов Б — 1111 и В — 1010 соответственно. Далее идут свободные кодовые слова длиною 3 — 100 и
Осталось ещё 3 шага — откроются после входа:
- Шаг 2
- Шаг 3
- Шаг 4
){kind=link}
Бесплатно · займёт минуту