infoegehelp.ru

Успешно сдать ЕГЭ по информатике
  • Главная
  • Контакты
  • Карта сайта
  • Помощь сайту
Важно
  • Демо варианты ЕГЭ
  • Учим числа: 2 в степени
  • Биты, байты, килобайты
Решение задач
  • Задачи вне основных разделов информатики
Разделы информатики
  • 2011-12-18-14-33-54Системы счисления
  • 2011-12-18-16-45-20Алгебра логики
  • 2011-12-18-16-55-26Программирование
  • 2011-12-18-16-53-40Кодирование информации
  • 2011-12-18-16-56-19Компьютерные сети и Интернет
  • -excelЭлектронные таблицы (Excel)
  • 2011-12-18-16-57-50Базы данных
  • 2011-12-18-16-58-50Графы
  • 2011-12-18-17-00-15Файловая система
  • Устройство компьютера
  • ПО компьютера

Разбор задачи A13 (демо ЕГЭ 2005)

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв ‑ из двух бит, для некоторых - из трех). Эти  коды представлены в таблице:
ABCDE
000 01 100 10 011

Определить, какой набор букв закодирован двоичной строкой  0110100011000

  1. EBCEA
  2. BDDEA
  3. BDCEA
  4. EBAEA
Решение:

1 способ

Построим графы для быстрого поиска в двоичной строке букв:

Задача A13 ЕГЭ по информатике 2005 кодирование набора букв

На графе розовым цветом выделены коды искомых букв.

На рисунке видно, что декодирование цепочки символов будет неоднозначным, т.к. идет дублирование (повторение) части кода другого символа. Например, в коде буквы E (011) дублируется код буквы B (01), а в коде буквы C (100) дублируется код буквы D (10).

При раскодировании последовательности будем стараться использовать буквы, код которых длиннее, чтобы быстрее рассмотреть всю последовательность. Например, если встретится последовательность 011, то сначала ее раскодируем как E. И если идущий дальше код раскодироваь нельзя, то вернемся обратно и выберем вместо E букву B. Также поступим с буквами C и D.

Анализ строки 0110100011000 происходит так:

1) берем первый символ. Он равен "0", поэтому смотрим граф с вершиной, равной "0":

Задача A13 ЕГЭ по информатике 2005 граф с вершиной 0

Видно, что в этом графе есть коды: 01, 000, 011.

2) берем второй символ. Он равен "1", поэтому идем по правой ветке: 0→01 (на рисунке розовая стрелка). Получаем код "01". Им закодирован символ "B".

Если взять следующий 3-й символ (он равен "1"), то пойдем по ветке 0→01→011 (на рисунке синие стрелки). Получится код "011". Им закодирована буква E.

Задача A13 ЕГЭ по информатике 2005 найдена буква E

Выберем букву E.

Далее анализ снова начинаем с вершины графа

3)берем четвертый символ. Он равен "0", поэтому смотрим граф с вершиной, равной "0".

Задача A13 ЕГЭ по информатике 2005 граф с вершиной 0

Видно, что в этом графе есть коды: 01, 000, 011.

4)берем пятый символ. Он равен "1", поэтому идем по правой ветке: 0→01 (на рисунке розовая стрелка). Получаем код "01". Им закодирован символ "B".

Задача A13 ЕГЭ по информатике 2005 найдена буква 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 способ

Используем метод подстановки. Для этого приведенные варианты заменим двоичными кодами:


Строка-эталонEBCEABDDEA BDCEA EBAEA
код в строку 0110100011000 011 01 100 01 10 10 011 01 10 100 011 000 011 01 000 011
код в столбец  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).

Перейти к другим задачам.

 

Rambler's Top100

© Латыпова В.А., 2012-2020. Все права защищены.
Копирование материалов сайта только с разрешения администрации сайта