Для передачи используется двоичный код, удовлетворяющий условию Фано.
Условие
| По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:Буква | Кодовое слово |
|---|---|
| А | 0101 |
| Б | 101 |
| Г | |
| Е | 011 |
| Буква | Кодовое слово |
| И | 00 |
| М | 0100 |
| Р | 11 |
| Т | |
Укажите кратчайшее кодовое слово для буквы Г. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.0 — нельзя, А, Е, И и М начинаются с 0.1 — нельзя, Б и Р начинаются с 1.00 — нельзя из-за И.01 — нельзя из-за А, Е и М.10 — нельзя из-за Б.11 — нельзя из-за Р.000 — нельзя из-за И.001 — нельзя из-за И.010 — нельзя из-за М.011 — нельзя из-за Е.100 — нельзя, поскольку, если закодировать букву Г кодовым словом 100, для буквы Т не будет кодовых слов, удовлетворяющих условию Фано.101 — нельзя из-за Б.110 — нельзя из-за Р.111 — нельзя из-за Р.0000 — нельзя из-за И.0001 — нельзя из-за И.0010 — нельзя из-за И.0011 — нельзя из-за И.0100 — нельзя из-за М.0101 — нельзя из-за А.0110 — нельзя из-за Е.0111 — нельзя из-за Е.1000 — можно использовать.1001 — можно использовать.1010 — нельзя из-за Б.1011 — нельзя из-за Б.1100 — нельзя из-за Р.1101 — нельзя из-за Р.1110 — нельзя из-за Р.1111 — нельзя из-за Р.
Осталось ещё 1 шаг
Таким образом, наименьшее числовое значение у…
Бесплатно · займёт минуту