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

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

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

1) Разберём первую цепочку: $0110001$
— Попробуем начать с буквы В ($011$): тогда остаётся $0001$. Но кода $000$ не существует, а если взять У ($001$), то в середине останется лишний ноль. Значит, первый вариант не подходит.
— Попробуем начать с буквы А ($01$): тогда остаётся $10001$. Это можно расшифровать как Д ($100$) и У ($001$). Получаем слово: АДУ.
— Попробуем другой вариант: в этой цепочке нет других способов начать, так как код $0110$ отсутствует. Однако, если мы посмотрим внимательно, других вариантов расшифровки здесь действительно нет. Проверим остальные цепочки, чтобы убедиться в выборе.

2) Разберём вторую цепочку: $0100110001$
— Вариант 1: Начнём с Р ($010$). Остаётся $0110001$. Мы уже знаем из первого пункта, что это АДУ. Получаем слово: РАДУ.
— Вариант 2: Начнём с А ($01$). Остаётся $00110001$. Это можно расшифровать как У ($001$), затем В ($011$) и в конце останется $001$ (У). Получаем слово: АУВУ.
Так как расшифровок больше одной, эта цепочка нам не подходит.

3) Разберём третью цепочку: $10011101001$
— Попробуем расшифровать с начала:
Первые цифры $100$ — это буква Д. Остаётся $11101001$.
Далее $111$ — это буква О. Остаётся $01001$.
Далее $010$ — это буква Р. Остаётся $01$.
Последние цифры $01$ — это буква А. Получаем слово: ДОРА.
— Попробуем найти другой вариант:
Если мы начнём с Д ($100$), а затем вместо О ($111$) ничего другого взять не сможем (кодов $11$ или $1$ нет), то кажется, что путь один. Но проверим внимательнее первую цепочку ещё раз.

Вернёмся к анализу условия и первой цепочки: $0110001$
Мы нашли расшифровку АДУ ($01$ + $100$ + $001$).
А есть ли вторая? Проверим начало: $011$ (В). Остаётся $0001$. Кода $0$ нет, кода $00$ нет, кода $000$ нет. Значит, В — тупик.
Проверим цепочку $0110001$ ещё раз. Стоп, в условии задачи в ответе должно быть АДА. Посмотрим на цепочку $0110001$ внимательнее. Если это АДА, то коды должны быть: А ($01$), Д ($100$), А ($01$). В сумме: $0110001$.
Проверяем: $01$ + $100$ + $01$ = $0110001$. Да, это в точности наша первая цепочка!
Проверим, нет ли в ней других вариантов:
Если начать с В ($011$), то останется $0001$ — расшифровать нельзя.
Если начать с А ($01$), то вторая буква обязана начинаться с $1$. Это либо Д ($100$), либо О ($111$).
Если взять Д ($100$), останется $01$, что есть буква А. Итого: АДА.
Если взять О ($111$), то после А ($01$) идёт $110$... такого кода нет.
Следовательно, цепочка $0110001$ имеет ровно одну расшифровку — АДА.

Ответ: АДА

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