Разбор задачи A13 (демо ЕГЭ 2006)
В | К | А | Р | Д |
---|---|---|---|---|
000 | 11 | 01 | 001 | 10 |
Из четырех полученных сообщений в этой кодировке, только одно прошло без ошибки и может быть корректно декодировано. Найдите его:
- 110100000100110011
- 111010000010010011
- 110100001001100111
- 110110000100110010
Построим графы для быстрого поиска в двоичной строке букв:
На графе розовым цветом выделены коды иcпользуемых букв.
Начнем с варианта 1:
Анализ строки 110100000100110011 происходит так:
1) берем первый символ. Он равен "1", поэтому смотрим граф с вершиной, равной "1":
Видно, что в этом графе есть коды: 10 и 11.
2) берем второй символ. Он равен "1", поэтому идем по правой ветке: 1→11. кодом "11" закодирована буква К.
После того как нашли символ, анализ снова начинаем с вершины графа.
3) берем следующий третий символ. Он равен "0", поэтому смотрим граф с вершиной, равной "0":
Видно, что в этом графе есть коды: 01, 000 и 001.
5)берем четвертый символ. Он равен "1", поэтому идем по правой ветке: 0→01. кодом "01" закодирована буква A.и т.д. для остальных символов закодированной строки.
В таблицах ниже описан полный анализ всех строк:
Вариант1
Двоичная строка | 11 01 000 001 001 10 01 1 | |||||||
---|---|---|---|---|---|---|---|---|
Путь в графе до кода буквы | 1→11 | 0→01 | 0→00→000 | 0→00→001 | 0→00→001 | 1→10 | 0→01 | 1 |
Двоичная строка, разбитая на коды букв | 11 | 01 | 000 | 001 | 001 | 10 | 01 | 1 |
Буква | К | А | В | Р | Р | Д | А | - |
Вариант2
Двоичная строка | 11 10 10 000 01 001 001 1 | |||||||
---|---|---|---|---|---|---|---|---|
Путь в графе до кода буквы | 1→11 | 1→10 | 1→10 | 0→00→000 | 0→01 | 0→00→001 | 0→00→001 | 1 |
Двоичная строка, разбитая на коды букв | 11 | 10 | 10 | 000 | 01 | 001 | 001 | 1 |
Буква | К | Д | Д | В | А | Р | Р | - |
Вариант3
Двоичная строка | 11 01 000 01 001 10 01 11 | |||||||
---|---|---|---|---|---|---|---|---|
Путь в графе до кода буквы | 1→11 | 0→01 | 0→00→000 | 0→01 | 0→00→001 | 1→10 | 0→01 | 1→11 |
Двоичная строка, разбитая на коды букв | 11 | 01 | 000 | 01 | 001 | 10 | 01 | 11 |
Буква | К | А | В | А | Р | Д | А | К |
Вариант4
Двоичная строка | 11 01 10 000 10 01 10 01 0 | ||||||||
---|---|---|---|---|---|---|---|---|---|
Путь в графе до кода буквы | 1→11 | 0→01 | 1→10 | 0→00→000 | 1→10 | 0→01 | 1→10 | 0→01 | 0 |
Двоичная строка, разбитая на коды букв | 11 | 01 | 10 | 000 | 10 | 01 | 10 | 01 | 0 |
Буква | К | А | Д | В | Д | А | Д | А | - |
Сообщения вариантов 1, 2, 4 оканчиваются кодом, которым не закодирована ни одна буква:
вариант 1 - "1",
вариант 2 - "0",
вариант 4 - "1".
Сообщение варианта 3 может быть корректно декодировано.
Получили: 110100001001100111.