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

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

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

1. Анализируем первую цепочку: $0100100101$
Попробуем первый вариант расшифровки:
- Первые цифры $010$ — это буква Р.
- Далее идёт $010$ — это снова буква Р.
- Далее $010$ — буква Р.
- В конце остаётся $1$, для которого нет кода. Значит, этот путь неверный.
Попробуем другой вариант:
- Первые цифры $01$ — это буква А.
- Далее идёт $001$ — это буква У.
- Далее $001$ — буква У.
- В конце $01$ — буква А. Получилось слово АУУА.
Ещё один вариант:
- Первые цифры $010$ — это буква Р.
- Далее $01$ — буква А.
- Далее $001$ — буква У.
- В конце $01$ — буква А. Получилось слово РАУА.
Так как мы нашли два способа расшифровки (АУУА и РАУА), эта цепочка нам не подходит.

2. Анализируем вторую цепочку: $011011111100$
Попробуем расшифровать её:
- Первые цифры могут быть только $011$ (буква В), так как если взять $01$ (буква А), то следующая цифра будет $1$, а кодов, начинающихся на $10$, кроме Д ($100$), у нас нет, но здесь идёт $101$.
- После $011$ (В) идёт $011$ (В).
- Далее идёт $111$ (О).
- Далее идёт $111$ (О).
- В конце остаётся $00$, для которого нет кода. Значит, этот путь тупиковый.
Попробуем иначе:
- Первые цифры $011$ (В).
- Далее идёт $01$ (А).
- Далее идёт $111$ (О).
- Далее идёт $111$ (О).
- В конце остаётся $100$ (Д). Получилось слово ВАООД.
Проверим, есть ли другие варианты. Если начать с $011$ (В), а затем взять $011$ (В), мы уже видели, что расшифровка не получается. Если начать с $011$ (В), затем $01$ (А), затем $111$ (О), затем $111$ (О), то остаётся только $100$ (Д). Других комбинаций для этой последовательности единиц и нулей нет. Слово ВВОД получается, если взять: $011$ (В), $011$ (В), $111$ (О), $100$ (Д). Проверим: $011 + 011 + 111 + 100 = 011011111100$. Это слово ВВОД. Оно расшифровывается единственным образом.

3. Анализируем третью цепочку: $0100110001$
- Вариант 1: $010$ (Р), $011$ (В), $000$ (нет кода).
- Вариант 2: $01$ (А), $001$ (У), $100$ (Д), $01$ (А). Получилось АУДА.
- Вариант 3: $010$ (Р), $01$ (А), $100$ (Д), $01$ (А). Получилось РАДА.
Так как есть два варианта (АУДА и РАДА), цепочка не подходит.

Таким образом, только вторая цепочка имеет единственную расшифровку — ВВОД.

Ответ: ВВОД

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