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

Решение.

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

1) Разберём цепочку $100101000$:
— Попробуем первый вариант: первая буква может быть Д ($100$). Остаётся $101000$. Далее может идти К ($101$) и С ($000$). Получаем слово ДКС.
— Попробуем второй вариант: первая буква может быть Н ($10$). Остаётся $0101000$. Далее может идти А ($01$), снова А ($01$) и С ($000$). Получаем слово НААС.
Так как расшифровок больше одной, эта цепочка нам не подходит.

2) Разберём цепочку $100000101$:
— Попробуем первый вариант: первая буква Д ($100$). Остаётся $000101$. Далее С ($000$) и К ($101$). Получаем слово ДСК.
— Попробуем второй вариант: первая буква Н ($10$). Остаётся $0000101$. Далее С ($000$), но затем остаётся $0101$, что можно расшифровать как АА ($01$ и $01$). Получаем слово НСАА.
Эта цепочка также имеет несколько вариантов расшифровки.

3) Разберём цепочку $0110001$:
— Попробуем начать с А ($01$). Остаётся $10001$.
— После А может идти только Д ($100$), так как кода $10$ (Н) быть не может (если взять Н, останется $001$, а кода $001$ или $0$ не существует).
— После Д ($100$) остаётся $01$, что соответствует букве А.
— Таким образом, получаем слово АДА.
Проверим, возможны ли другие варианты в начале: цепочка не может начинаться с С, Д, К, Н или О, так как их коды не совпадают с началом $011...$. Единственный возможный старт — это буква А. Последовательно проверяя каждый шаг, мы убеждаемся, что иного пути расшифровки, кроме А-Д-А, не существует.

Единственная цепочка, имеющая только одну расшифровку — третья, и она соответствует слову АДА.

Ответ: АДА

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