Разбор задачи A16 (демо ЕГЭ 2004)
a | b | c | d | e |
---|---|---|---|---|
000 | 110 | 01 | 001 | 10 |
Определите, какой набор букв закодирован двоичной строкой 1100000100110
- baade
- badde
- bacde
- bacdb
1 способ
Построим графы для быстрого поиска в двоичной строке букв:
На графе розовым цветом выделены коды искомых букв.
Анализ строки 1100000100110 происходит так:
1) берем первый символ. Он равен "1", поэтому смотрим граф с вершиной, равной "1":
Видно, что в этом графе есть коды: 10 и 110.
2) берем второй символ. Он равен "1", поэтому идем по правой ветке: 1→11. кодом "11" ничего не закодировано.
3)берем третий символ. Он равен "0", спускаемся по ветке: 1→11→110. Получаем код "110". им закодирован символ "b".
После того как нашли символ, анализ снова начинаем с вершины графа.
4) берем следующий четвертый символ. Он равен "0", поэтому смотрим граф с вершиной, равной "0":
Видно, что в этом графе есть коды: 01, 000 и 001.
5) берем пятый символ. Он равен "0", поэтому идем по левой ветке: 0→00. кодом "00" ничего не закодировано.
6) берем шестой символ. Он равен "0", поэтому идем по левой ветке: 0→00→000. Получаем код "000". им закодирован символ "a".
и т.д. для остальных символов закодированной строки.
В таблице ниже описан анализ всей строки:
Двоичная строка | 110 000 01 001 10 | ||||
---|---|---|---|---|---|
Путь в графе до кода буквы | 1→11→110 | 0→00→000 | 0→01 | 0→00→001 | 1→10 |
Двоичная строка, разбитая на коды букв | 110 | 000 | 01 | 001 | 10 |
Буква | b | a | с | d | e |
Получили: bacde.
2 способ
Используем метод подстановки. Для этого приведенные варианты заменим двоичными кодами:
Строка-эталон | baade | badde | bacde | bacdb | |
---|---|---|---|---|---|
код в строку | 1100000100110 |
110 000 |
110 000 |
110 000 01 001 10 |
110 000 01 001 |
код в столбец | 1 |
1 1 0 |
1 1 0 |
1 1 0 |
1 1 0 |
1 | |||||
0 | |||||
0 |
0 0 0 |
0 0 0 |
0 0 0 |
0 0 0 |
|
0 | |||||
0 | |||||
0 |
|
|
0 1 |
0 1 |
|
1 | |||||
0 |
0 0 1 |
0 0 1 |
|||
0 | |||||
1 | |||||
1 |
1 0 |
|
|||
0 | |||||
Искомый набор букв выделен розовым. Для удобства анализ строк был сделан горизонтально и вертикально.
Из таблицы видно, что код строки совпадает только с кодом набора букв bacde (вариант3).