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

#55438Задание №2ФИПИ

Кодирование и декодирование

Валя шифрует русские слова, записывая вместо каждой буквы её код. Коды букв даны в таблице.

А	В	Д	О	Р	У
01	011	100	111	010	001

Некоторые кодовые цепочки можно расшифровать несколькими способами. Например, 00101001 может означать не только УРА, но и УАУ.

Даны три кодовые цепочки:

11101001

010111011

01001010

Найдите среди них ту, которая имеет только одну расшифровку, и запишите в ответе расшифрованное слово.

Правильный ответ

РОВ

Пояснение

Решение.

Для решения этой задачи нам необходимо разобрать каждую из трёх предложенных кодовых цепочек и проверить, сколько вариантов расшифровки для них существует. Мы будем пользоваться таблицей кодов:
А: $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$ расшифровывается только как РОВ.

Ответ: РОВ

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