вернуться
Информатика

Вопрос 5

По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение №1

Давайте сначала разберём условие задачи. У нас имеются сообщения, в которых бывают только 4 буквы: П, О, С, Т. При этом сами сообщения закодированы с помощью двоичного кода, то есть вместо букв передаются последовательности ноликов и единичек.

Известно, что Т кодируется 111, О — 0, П — 100. Например, ПОП было бы закодировано так: 1000100 (полужирным выделено вхождение буквы П). А, например, вот такая последовательность 1110100 декодировалась бы однозначно в слово ТОП.

Нам надо придумать наименьший возможный код для буквы С, при котором декодирование было бы однозначным. Что означает слово "однозначность" в данном контексте?

К примеру, давайте обозначим букву С за 1. Наименьший возможный? Да, потому что меньше 1 символа не бывает. Но есть ли однозначность? 

  1. Рассмотрим слово 111. С одной стороны, это — буква Т. С другой стороны, если С — это 1, то 111 можно декодировать, как ССС. То есть, одно и то же слово, записанное в двоичном коде, можно декодировать двумя способами, при этом непонятно, какой из них верный. Значит, если сделать кодом буквы С цифру 1, то такое кодирование не будет однозначным.
  2. Значит, нельзя кодировать букву С кодами, состоящими из одной цифры (0 — уже занято О, 1 — не подходит). Попробуем двумя. Вариантов — четыре: 00, 10, 11, 01. При этом сходу очевидно, что вариант С=00 не подходит, так как в этом случае слово 00 может восприниматься либо как буква С, либо как две буквы О. Поэтому остаётся три варианта: 10, 11, 01.
  3. Попробуем закодировать букву С кодом 10. С какой потенциально буквой у С есть общая часть? С П (С=10, П=100, есть общая часть 10). Давайте тогда и рассмотрим тогда слово 100, связанное с буквой П. 
    С одной стороны, 100 может быть декодировано просто буквой П (ведь П и есть 100).
    С другой стороны, 100 можно декодировать буквами СО (С=10, О=0). 
    Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 10.
  4. Закодируем букву С кодом 11. В этом случае буква С очень похожа на букву Т (С=11, Т=111). Рассмотрим последовательность 111111.
    С одной стороны, 111111 можно декодировать, как ТТ.
    С другой стороны, 111111 декодируется, как ССС.
    Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 11.
  5. Закодируем букву С кодом 01. В этом случае буква С очень похожа на перевёрнутый код буквы П (П=100, С=01). Рассмотрим последовательность 0100.
    С одной стороны, 0100 можно представить, как СОО.
    С другой стороны, 0100 декодируется, как ОП.
    Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 01.
  6. Таким образом, все двузначные коды не подошли. Значит, надо брать трёхзначные.
  7. Варианты у нас следующие: 000, 001, 010, 100, 011, 101, 110, 111. При этом 111 и 100 уже заняты буквами Т и П соответственно. Вариант 000 очевидно не подходит по соображениям обозначенным в п.2 (равен трём буквам О). 
  8. Остаётся: 001, 010, 011, 101, 110. Заметьте — мы сразу упорядочили коды по возрастанию, как это требуется в условии задачи (если вдруг подойдут несколько кодов — нужно выбрать наименьший).
  9. Начнём с 001. Он очевидным образом похож на букву П (П=100, С=001). Возьмём последовательность 00100.
    С одной стороны, 0010можно декодировать, как СОО.
    С другой стороны, 00100 представим, как ООП.
    Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 001.
  10. Рассмотрим код 010.  Он похож на букву П (П=100, С=010). Возьмём последовательность 0100.
    С одной стороны, 0100 можно декодировать, как СО.
    С другой стороны, 0100 представим, как ОП.
    Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 010.
  11. Рассмотрим код 011.  В нём уже две единицы, значит, если и есть неоднозначность, то она обязана быть с буквой Т (111). Возьмём последовательность 011100.
    С одной стороны, 011100 можно декодировать, как СП.
    С другой стороны, 011100 представим, как ОТОО.
    Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 011.
  12. Рассмотрим код 101. Он похож на несколько кодов, но если начать перебирать возможные несостыковки, то мы их не найдём. На основе этого делаем вывод, что этот код и будет являться ответом.

Ответ: код буквы С, которых сохраняет однозначость кодирования/декодирования, — 101.