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

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

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

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

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

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

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

0100100101

010111100

10011101001

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

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

РОД

Пояснение

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

Выпишем коды букв для удобства:
А: $01$
В: $011$
Д: $100$
О: $111$
Р: $010$
У: $001$

1. Разбор первой цепочки: $0100100101$
Попробуем найти разные варианты расшифровки:
Способ А: $010$ (Р) + $01$ (А) + $001$ (У) + $01$ (А). Получается слово РАУА.
Способ Б: $01$ (А) + $001$ (У) + $01$ (А) + $001$ (У) + $01$ (А). Получается слово АУАУА.
Так как цепочка имеет более одного варианта расшифровки, она нам не подходит.

2. Разбор второй цепочки: $010111100$
Попробуем расшифровать её:
Способ А: $010$ (Р) + $111$ (О) + $100$ (Д). Получается слово РОД.
Проверим, есть ли другие варианты. Если начать с $01$ (А), то останется $0111100$ . Далее можно взять $011$ (В), останется $1100$ . Но кода $11$ или $110$ не существует. Если после $01$ (А) взять $111$ (О), останется $100$ (Д). Получается АОД.
Стоп, проверим внимательнее: $01$ (А) + $011$ (В) + $11$ (нет кода) — не выходит. А если $01$ (А) + $111$ (О) + $100$ (Д)? Да, это второй вариант расшифровки. Значит, цепочка не уникальна.

Внимание: Перепроверим коды. Буква В — это $011$ , буква Р — это $010$ .
Цепочка $010111100$ :
- Вариант 1: $010$ (Р) + $111$ (О) + $100$ (Д) = РОД.
- Вариант 2: $01$ (А) + $011$ (В) + $1100$ (нет кода).
- Вариант 3: $01$ (А) + $111$ (О) + $100$ (Д) — невозможно, так как после первой $01$ идет единица, а не $111$ .
Давайте ещё раз внимательно: $010$ — это Р. После неё идёт $111$ — это О. После неё $100$ — это Д. Итого РОД.
Может ли она начаться с А ( $01$ )? Если да, то следующая цифра $0$ . Кода, начинающегося на $011...$ нет, кроме В, но там третья цифра $1$ . А у нас после $01$ идёт $1$ . Значит, если мы взяли А ( $01$ ), следующая буква должна начинаться с $1$ . Это либо Д ( $100$ ), либо О ( $111$ ).
Если А ( $01$ ) + О ( $111$ ), то остаётся $100$ (Д). Получаем АОД.
Однако, в цепочке $010111100$ после первой А ( $01$ ) идёт цифра $0$ , а не $1$ . Значит, вариант АОД невозможен. Единственный способ начать — это буква Р ( $010$ ). После неё остаётся $111100$ , что однозначно делится на О ( $111$ ) и Д ( $100$ ).

3. Разбор третьей цепочки: $10011101001$
Способ А: $100$ (Д) + $111$ (О) + $010$ (Р) + $01$ (А) — лишняя $1$ в конце? Нет, там $001$ (У). Итого: Д + О + Р + У (ДОРУ).
Способ Б: $100$ (Д) + $111$ (О) + $01$ (А) + $001$ (У) + $01$ (А). Итого: ДОАУА.
Цепочка имеет несколько расшифровок.

Таким образом, только вторая цепочка $010111100$ расшифровывается единственным способом — РОД.

Ответ: РОД

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