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

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

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

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

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

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

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

10111101

00011110

100111101

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

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

СОН

Пояснение

Решение.

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

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

2. Разбор цепочки $00011110$ :
Попробуем расшифровать: первая буква может быть только $С$ ( $000$ ), так как других кодов на нули нет. Остаётся $11110$ .
Далее может идти $О$ ( $111$ ), тогда остаётся $10$ , что соответствует букве $Н$ . Получаем слово: СОН.
Проверим, есть ли другие варианты. Если после $С$ мы не возьмём $О$ , то других кодов, начинающихся на $111$ , в таблице нет. Если попробовать взять после $С$ код $Н$ ( $10$ ), то останется $1110$ , но кода $1110$ или кода, начинающегося на $1110$ , не существует. Таким образом, для этой цепочки возможен только один вариант расшифровки.

3. Разбор цепочки $100111101$ :
Попробуем первый вариант: первая буква $Д$ ( $100$ ). Остаётся $111101$ . Далее $О$ ( $111$ ), затем $Н$ ( $10$ ), в конце остаётся лишняя единица (или $101$ как $К$ ). Один из вариантов: $Д$ ( $100$ ) + $О$ ( $111$ ) + $К$ ( $101$ ) = ДОК.
Попробуем другой вариант: первая буква $Н$ ( $10$ ). Остаётся $0111101$ . Далее $А$ ( $01$ ), затем $О$ ( $111$ ), затем $Н$ ( $10$ ), и снова лишняя единица. Однако можно выделить: $Н$ ( $10$ ) + $А$ ( $01$ ) + $О$ ( $111$ ) + $К$ ( $101$ ) = НАОК.
Поскольку здесь также возможны разные варианты (например, начало с $Д$ или с $Н$ ), эта цепочка нам не подходит.

Единственная цепочка, которая расшифровывается однозначно — это $00011110$ , что соответствует слову СОН.

Ответ: СОН

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