Для пяти букв латинского алфавита заданы их двоичные коды
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
Какой набор букв закодирован двоичной строкой 1100000100110?
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.
Разобьём код слева направо по данным таблицы и переведём его в буквы:
110 000 01 001 10 — b a c d e.
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
Какой набор букв закодирован двоичной строкой 1000110110110? Все буквы в последовательности — разные.
Мы видим, что условия Фано и обратное условие Фано не выполняются, значит, код можно раскодировать неоднозначно.
Будем пробовать разные варианты, отбрасывая те, в которых получаются повторяющиеся буквы:
1) 100 011 01 10 110
Первая буква определяется однозначно, её код 100: a.
Пусть вторая буква — с, тогда следующая буква — d, потом — e и b.
Такой вариант удовлетворет условию, значит, окончательно получили ответ: acdeb.
Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Какая последовательность из 6 букв закодирована двоичной строкой 011111000101100?
Мы видим, что условия Фано и обратное условие Фано не выполняются, значит, код можно раскодировать неоднозначно.
Будем пробовать различные варианты:
1) 011 11 100 0101100
Первая буква определяется однозначно, её код 011: D.
Вторая буква также определится однозначно — E.
Пусть третья буква B, тогда следующая начинается с кода 010, но таких букв в таблице нет, значит, предположение не верно.
2) 011 11 10 00 101 100
Третья буква — С, потом — A. Мы хотим получить ещё две буквы, чтобы в сумме их было 6, тогда следующая буква — F, и последняя — B.
Окончательно получили ответ: DECAFB.
Примечание. DECACEA не подходит, так как 7 букв.
так же подходит decacea
011 11 10 00 10 11 00
В задании спрашивается о последовательности из шести букв.
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к каждому представлению дописывается сумма его элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01100010100100100110.
Из примера видно, что 2 знака кодируются 10 двоичными разрядами (битами), на каждую цифру отводится 5 бит. В условии сказано, что каждая цифра записывается кодом длиной 4 знака, значит, пятую цифру можно отбросить.
Разобьём двоичную запись на группы по 5 знаков: 01100 01010 01001 00110. Отбрасываем последнюю цифру в каждой пятёрке и переводим в десятичную запись:
0110 0101 0100 0011 — 6 5 4 3.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 10; Б — 11; В — 000; Г — 001; Д — 010. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Второй вариант ответа не подходит, поскольку код буквы А является началом кода буквы В. Третий вариант не подходит, поскольку код буквы В является началом кода буквы Г. Четвёртый вариант ответа подходит.
infoegehelp.ru
Разбор задачи A13 (демо ЕГЭ 2005)
Определить, какой набор букв закодирован двоичной строкой 0110100011000
Построим графы для быстрого поиска в двоичной строке букв:
На графе розовым цветом выделены коды искомых букв.
На рисунке видно, что декодирование цепочки символов будет неоднозначным, т.к. идет дублирование (повторение) части кода другого символа. Например, в коде буквы E ( 01 1) дублируется код буквы B ( 01 ), а в коде буквы C ( 10 0) дублируется код буквы 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.
Далее анализ снова начинаем с вершины графа
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 |
Используем метод подстановки. Для этого приведенные варианты заменим двоичными кодами:
Для 5 букв латинского алфавита заданы их двоичные коды
Задание входит в ЕГЭ по информатике для 11 класса под номером 5 (Кодирование и декодирование информации).
Рассмотрим, как решаются подобные задания на примере.
Попробуем декодировать строку, чтобы получить исходный набор букв. Для этого будем каждый раз брать первые 2 или 3 символа и искать такую последовательность в таблице кодов. Первая буква равна 11 или 110, в таблице есть только последовательность 110, которая обозначает букву «b». Оставшаяся строка равна:
Следующая буква равна 00 или 000, в таблице есть только последовательность 000, которая обозначает букву «a». Оставшаяся строка равна:
Следующая буква равна 01 или 010, в таблице есть только последовательность 01, которая обозначает букву «c». Оставшаяся строка равна:
Следующая буква равна 00 или 001, в таблице есть только последовательность 001, которая обозначает букву «d». Оставшаяся строка равна:
Оставшаяся строка равна 10, это буква «e». Таким образом, получился набор букв bacde, это ответ номер 3.
Поделитесь статьей с одноклассниками «Для 5 букв латинского алфавита заданы их двоичные коды – как решать».
Есть другой способ решения?
Предложите другой способ решения задачи «Для 5 букв латинского алфавита заданы их двоичные коды». Возможно, он окажется более понятным для кого-нибудь:
вот мои 20 символов и ответ: 2
a1 b1 c1 d1 e1 f1 g1 h1 i1 j1 k1 l1 m1 n1 o1 p1 q1 r1 s1 t1 u1 v1 w1 x1 y1 z2 a2 b2 c2 d2 e2 f2 g2 h2 i2 j2 k2 l2 m2 n2 o2 p2 q2 r2 s2 t2 u2 v2 w2 x2 y2 z3 a3 b3 c3 d3 e3 f3 g3 h3 i3 j3 k3 l3 m3 n3 o3 p3 q3 r3 s3 t3 u3 v3 w3 x3 y3 z4 a4 b4 c4 d4 e4 f4 g4 h4 i4 j4 k4 l4 m4 n4 o4 p4 q4 r4 s4 t4 u4 v4 w4 x4 y4 z5 a5 b5 c5 d5 e5 f5 g5 h5 i5 j5 k5 l5 m5 n5 o5 p5 q5 r5 s5 t5 u5 v5 w5 x5 y5 z6 a6 b6 c6 d6 e6 f6 g6 h6 i6 j6 k6 l6 m6 n6 o6 p6 q6 r6 s6 t6 u6 v6 w6 x6 y6 z7 a7 b7 c7 d7 e7 f7 g7 h7 i7 j7 k7 l7 m7 n7 o7 p7 q7 r7 s7 t7 u7 v7 w7 x7 y7 z8 a8 b8 c8 d8 e8 f8 g8 h8 i8 j8 k8 l8 m8 n8 o8 p8 q8 r8 s8 t8 u8 v8 w8 x8 y8 z9 a9 b9 c9 d9 e9 f9 g9 h9 i9 j9 k9 l9 m9 n9 o9 p9 q9 r9 s9 t9 u9 v9 w9 x9 y9
1b 1c 1d 1e 1f 1g 1h 1i 1j 1k 1l 1m 1n 1o 1p 1q 1r 1s 1t 1u 1v 1w 1x 1y 1z 1a 2b 2c 2d 2e 2f 2g 2h 2i 2j 2k 2l 2m 2n 2o 2p 2q 2r 2s 2t 2u 2v 2w 2x 2y 2z 2a 3b 3c 3d 3e 3f 3g 3h 3i 3j 3k 3l 3m 3n 3o 3p 3q 3r 3s 3t 3u 3v 3w 3x 3y 3z 3a 4b 4c 4d 4e 4f 4g 4h 4i 4j 4k 4l 4m 4n 4o 4p 4q 4r 4s 4t 4u 4v 4w 4x 4y 4z 4a 5b 5c 5d 5e 5f 5g 5h 5i 5j 5k 5l 5m 5n 5o 5p 5q 5r 5s 5t 5u 5v 5w 5x 5y 5z 5a 6b 6c 6d 6e 6f 6g 6h 6i 6j 6k 6l 6m 6n 6o 6p 6q 6r 6s 6t 6u 6v 6w 6x 6y 6z 6a 7b 7c 7d 7e 7f 7g 7h 7i 7j 7k 7l 7m 7n 7o 7p 7q 7r 7s 7t 7u 7v 7w 7x 7y 7z 7a 8b 8c 8d 8e 8f 8g 8h 8i 8j 8k 8l 8m 8n 8o 8p 8q 8r 8s 8t 8u 8v 8w 8x 8y 8z 8a 9b 9c 9d 9e 9f 9g 9h 9i 9j 9k 9l 9m 9n 9o 9p 9q 9r 9s 9t 9u 9v 9w 9x 9y 9z
