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

Решение.

Для решения этой задачи нам необходимо разобрать каждую из трёх предложенных кодовых цепочек и проверить, сколько вариантов расшифровки для них существует. Мы будем пользоваться таблицей кодов:
А: $01$
В: $011$
Д: $100$
О: $111$
Р: $010$
У: $001$

1) Разберём первую цепочку: $11101001$
Попробуем первый вариант: первые три цифры $111$ — это буква О. Остаётся $01001$. Далее можно взять $010$ (Р) и $01$ (А). Получаем слово ОРА.
Попробуем второй вариант: первые три цифры $111$ — это О. Но оставшуюся часть $01001$ можно расшифровать иначе: $01$ (А) и $001$ (У). Получаем слово ОАУ.
Так как расшифровок больше одной, эта цепочка нам не подходит.

2) Разберём вторую цепочку: $010111011$
Попробуем первый вариант: первые три цифры $010$ — это буква Р. Далее $111$ — это О. И последние три цифры $011$ — это В. Получаем слово РОВ.
Проверим, есть ли другие варианты. Если начать с буквы А ($01$), то следующая часть будет $0111011$. Здесь может быть В ($011$), тогда останется $1011$, но кода $10$ или $101$ в таблице нет. Если после А ($01$) взять О ($111$), останется $011$ (В). Получаем АОВ.
Уже найдено два варианта (РОВ и АОВ), значит, эта цепочка тоже имеет несколько расшифровок.

Примечание: Внимательно перепроверим вторую цепочку. Если мы берем Р ($010$), то остается $111$ (О) и $011$ (В). Если мы берем А ($01$), остается $011$ (В) и $1011$ (нет кода) ИЛИ $01$ (А) и $111$ (О) и $011$ (В). Таким образом, цепочка $010111011$ расшифровывается как РОВ или АОВ.

3) Разберём третью цепочку: $01001010$
Попробуем расшифровать:
Первые цифры $010$ — это Р. Остаётся $01010$.
Далее можно взять $01$ (А), остаётся $010$ (Р). Получаем РАР.
Или после первой Р ($010$) взять $010$ (Р), остаётся $10$ (кода нет).
Если начать с А ($01$), останется $001010$. Далее $001$ (У) и $010$ (Р). Получаем АУР.
Здесь тоже несколько вариантов.

Важное уточнение: Перепроверим анализ цепочек. В условии сказано, что только ОДНА цепочка имеет ОДНУ расшифровку.
Посмотрим на вторую цепочку $010111011$ ещё раз.
Если начать с А ($01$), то следующая цифра $0$. Кода, начинающегося на $011$, кроме В, нет. Если мы взяли А ($01$), то следующая буква должна начинаться с $0$. Это может быть Р ($010$), У ($001$) или А ($01$).
Если А($01$) + Р($010$), остается $11011$ — кода нет.
Если А($01$) + А($01$), остается $111011$. Это О($111$) + В($011$). Получаем ААОВ.
Если Р($010$) + В($011$), остается $1011$ — кода нет.
Единственный верный и однозначный разбор второй цепочки: $010$ (Р), $111$ (О), $011$ (В) — РОВ.
Проверим "ААОВ": $01$ + $01$ + $111$ + $011$ = $0101111011$. В нашей цепочке на одну единицу меньше! Значит, ААОВ не подходит.
Проверим "АОВ": $01$ + $111$ + $011$ = $01111011$. Тоже не совпадает.
Следовательно, цепочка $010111011$ расшифровывается только как РОВ.

Ответ: РОВ

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