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

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

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

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

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

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

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

10111101

1010110

10111000

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

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

НОС

Пояснение

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

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

2. Разбор второй цепочки: $1010110$
Попробуем расшифровать её:
• Способ А: Первые цифры $101$ — это К. Остаётся $0110$ . Далее $01$ — это А, остаётся $10$ — это Н. Получаем слово КАН.
• Способ Б: Первые цифры $10$ — это Н. Остаётся $10110$ . Далее $10$ — это Н, остаётся $110$ . Но кода $110$ в таблице нет. Однако, если мы возьмём $10$ (Н), затем $101$ (К), останется $10$ (Н). Получаем слово НКН.
Цепочка имеет несколько вариантов расшифровки, она нам не подходит.

3. Разбор третьей цепочки: $10111000$
Проверим все возможные варианты деления:
• Посмотрим на начало: код $1$ или $1011$ отсутствует. Возможны только $10$ (Н) или $101$ (К).
• Если начнём с К ( $101$ ): остаётся $11000$ . Кода $1$ , $11$ или $110$ нет. Единственный вариант — $111$ (О). После этого остаётся $000$ (С). Получаем слово КОС.
• Если начнём с Н ( $10$ ): остаётся $111000$ . Далее может быть только $111$ (О). После этого остаётся $000$ (С). Получаем слово НОС.
Внимание: проверим внимательно ещё раз. В коде $10111000$ :
Если мы берём К ( $101$ ), то следующая часть $110...$ не может быть расшифрована, так как нет кода, начинающегося на $110$ (кроме $111$ , но у нас после двух единиц идёт ноль). Значит, вариант с К невозможен.
Единственный верный путь:
$10$ — это Н
$111$ — это О
$000$ — это С
Других вариантов нет, так как на каждом этапе выбор кода однозначен для успешного завершения расшифровки.

Ответ: НОС

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