Разбор задачи A13 (демо ЕГЭ 2005)
| A | B | C | D | E |
|---|---|---|---|---|
| 000 | 01 | 100 | 10 | 011 |
Определить, какой набор букв закодирован двоичной строкой 0110100011000
- EBCEA
- BDDEA
- BDCEA
- EBAEA
1 способ
Построим графы для быстрого поиска в двоичной строке букв:
На графе розовым цветом выделены коды искомых букв.
На рисунке видно, что декодирование цепочки символов будет неоднозначным, т.к. идет дублирование (повторение) части кода другого символа. Например, в коде буквы E (011) дублируется код буквы B (01), а в коде буквы C (100) дублируется код буквы D (10).
При раскодировании последовательности будем стараться использовать буквы, код которых длиннее, чтобы быстрее рассмотреть всю последовательность. Например, если встретится последовательность 011, то сначала ее раскодируем как E. И если идущий дальше код раскодироваь нельзя, то вернемся обратно и выберем вместо E букву B. Также поступим с буквами C и D.
Анализ строки 0110100011000 происходит так:
1) берем первый символ. Он равен "0", поэтому смотрим граф с вершиной, равной "0":
Видно, что в этом графе есть коды: 01, 000, 011.
2) берем второй символ. Он равен "1", поэтому идем по правой ветке: 0→01 (на рисунке розовая стрелка). Получаем код "01". Им закодирован символ "B".
Если взять следующий 3-й символ (он равен "1"), то пойдем по ветке 0→01→011 (на рисунке синие стрелки). Получится код "011". Им закодирована буква E.
Выберем букву E.
3)берем четвертый символ. Он равен "0", поэтому смотрим граф с вершиной, равной "0".
Видно, что в этом графе есть коды: 01, 000, 011.
4)берем пятый символ. Он равен "1", поэтому идем по правой ветке: 0→01 (на рисунке розовая стрелка). Получаем код "01". Им закодирован символ "B".
Надо проверить, даст ли следующий (шестой) символ букву E. Он равен "0", поэтому пойдем по ветке 0→01→010. Получится код 010. Следовательно, E не получим. Остановимся на букве B.
Далее анализ снова начинаем с вершины графа
5)снова берем шестой символ. Он равен "0", поэтому смотрим граф с вершиной, равной "0".
и т.д.В таблицах ниже описан анализ всей строки:
| Двоичная строка | 011 01 000 110 00 | |||
|---|---|---|---|---|
| Путь в графе до кода буквы | 0→01→011 | 0→01 | 0→00→000 | 1 |
| Двоичная строка, разбитая на коды букв | 011 | 01 | 000 | - |
| Буква | E |
B | A |
- |
Т.к. строку раскодировать не удалось, то возвращаемся к букве E. Берем вместо "E", букву "B":
| Двоичная строка | 01 10 100 011 000 | ||||
|---|---|---|---|---|---|
| Путь в графе до кода буквы | 0→01 | 1→10 | 1→10→100 | 0→01→011 | 0→00→000 |
| Двоичная строка, разбитая на коды букв | 01 | 10 | 100 | 011 |
000 |
| Буква | B |
D | C |
E |
A |
Получили: BDCEA.
2 способ
Используем метод подстановки. Для этого приведенные варианты заменим двоичными кодами:
| Строка-эталон | EBCEA | BDDEA | BDCEA | EBAEA | |
|---|---|---|---|---|---|
| код в строку | 0110100011000 |
011 01 |
01 10 10 |
01 10 100 011 000 |
011 01 000 |
| код в столбец | 0 |
0 1 1 |
0 1 |
0 1 |
0 1 1 |
| 1 | |||||
| 1 |
1 0 |
1 0 |
|||
| 0 |
0 1 |
0 1 |
|||
| 1 |
1 0 |
1 0 0 |
|||
| 0 | 0 0 0 |
||||
| 0 |
0 1 1 |
||||
| 0 |
0 1 1 |
||||
| 1 | 0 1 1 |
||||
| 1 | |||||
| 0 | 0 0 0 |
||||
| 0 | |||||
| 0 |
Искомый набор букв выделен розовым. Для удобства анализ строк был сделан горизонтально и вертикально.
Из таблицы видно, что код строки совпадает только с кодом набора букв BDCEA (вариант3).