Задание №2 — Теоретические основы информатики

Решение.

Чтобы решить эту задачу, нам нужно разобрать каждую из трёх предложенных цепочек и проверить, сколько вариантов расшифровки для них существует. Мы будем последовательно отделять коды букв слева направо, сверяясь с таблицей.

1. Разбор цепочки $10111101$:
Попробуем первый вариант: первая буква может быть $К$ ($101$). Остаётся $11101$. Далее может идти $О$ ($111$), остаётся $01$, что соответствует букве $А$. Получаем слово: КОА.
Попробуем другой вариант: первая буква может быть $Н$ ($10$). Остаётся $111101$. Далее может идти $О$ ($111$), остаётся $101$, что соответствует букве $К$. Получаем слово: НОК.
Так как расшифровок больше одной, эта цепочка нам не подходит.

2. Разбор цепочки $00011110$:
Попробуем расшифровать: первая буква может быть только $С$ ($000$), так как других кодов на нули нет. Остаётся $11110$.
Далее может идти $О$ ($111$), тогда остаётся $10$, что соответствует букве $Н$. Получаем слово: СОН.
Проверим, есть ли другие варианты. Если после $С$ мы не возьмём $О$, то других кодов, начинающихся на $111$, в таблице нет. Если попробовать взять после $С$ код $Н$ ($10$), то останется $1110$, но кода $1110$ или кода, начинающегося на $1110$, не существует. Таким образом, для этой цепочки возможен только один вариант расшифровки.

3. Разбор цепочки $100111101$:
Попробуем первый вариант: первая буква $Д$ ($100$). Остаётся $111101$. Далее $О$ ($111$), затем $Н$ ($10$), в конце остаётся лишняя единица (или $101$ как $К$). Один из вариантов: $Д$ ($100$) + $О$ ($111$) + $К$ ($101$) = ДОК.
Попробуем другой вариант: первая буква $Н$ ($10$). Остаётся $0111101$. Далее $А$ ($01$), затем $О$ ($111$), затем $Н$ ($10$), и снова лишняя единица. Однако можно выделить: $Н$ ($10$) + $А$ ($01$) + $О$ ($111$) + $К$ ($101$) = НАОК.
Поскольку здесь также возможны разные варианты (например, начало с $Д$ или с $Н$), эта цепочка нам не подходит.

Единственная цепочка, которая расшифровывается однозначно — это $00011110$, что соответствует слову СОН.

Ответ: СОН

Источник: ФИПИ