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

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

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

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

А	Д	К	Н	О	С
01	100	101	10	111	000

Некоторые шифровки можно расшифровать несколькими способами. Например, 00010101 может означать не только СКА, но и СНК.

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

1010110

100000101

00011110001

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

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

СОДА

Пояснение

Решение.

Для решения этой задачи нам необходимо разобрать каждую из трёх предложенных цепочек и проверить, сколько вариантов расшифровки для них существует. Мы будем использовать таблицу кодов:
А — $01$
Д — $100$
К — $101$
Н — $10$
О — $111$
С — $000$

1. Разбор первой цепочки: $1010110$
Попробуем расшифровать её разными способами:
Способ А: $10$ (Н) + $10$ (Н) + $1$ (нет кода) — не подходит.
Способ Б: $101$ (К) + $01$ (А) + $10$ (Н). Получается слово КАН.
Способ В: $10$ (Н) + $101$ (К) + $10$ (Н). Получается слово НКН.
Так как у первой цепочки уже нашлось как минимум два варианта расшифровки (КАН и НКН), она нам не подходит.

2. Разбор второй цепочки: $100000101$
Попробуем расшифровать её:
Способ А: $100$ (Д) + $000$ (С) + $101$ (К). Получается слово ДСК.
Способ Б: $10$ (Н) + $00$ (нет кода) — не подходит.
Способ В: $100$ (Д) + $00$ (нет кода) — не подходит.
Казалось бы, здесь один вариант, но проверим внимательно: код $100$ — это Д, а код $10$ — это Н. Если мы возьмём $10$ (Н), то останется $00000101$ . Далее $000$ (С), остаётся $00101$ . Кода $00$ нет.
Однако, если мы возьмём $100$ (Д), затем $000$ (С), затем $101$ (К), мы получаем ДСК.
Проверим ещё раз: может ли цепочка начинаться иначе? Если $10$ (Н), то дальше $000$ (С), остаётся $0101$ , что есть $01$ (А) + $01$ (А). Получается слово НСАА.
У второй цепочки тоже несколько вариантов расшифровки (ДСК и НСАА), она не подходит.

3. Разбор третьей цепочки: $00011110001$
Попробуем расшифровать её по шагам:
- Первые цифры $000$ . Это может быть только буква С. (Кода $00$ или $0$ не существует).
- Далее идут цифры $111$ . Это может быть только буква О. (Кодов $1$ или $11$ не существует).
- Далее идут цифры $100$ . Это может быть буква Д. Если мы попробуем взять $10$ (Н), то останется $001$ , а кода $00$ не существует. Значит, здесь только Д.
- В конце остаются цифры $01$ . Это буква А.
Таким образом, цепочка расшифровывается единственным способом: $000$ (С) + $111$ (О) + $100$ (Д) + $01$ (А).
Получается слово СОДА.

Ответ: СОДА

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