Кодирование буквенных сообщений в двоичный код —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#56305

Для передачи слова АМБИДЕКСТР решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Известно, что у букв А, Р кодовые слова соответственно равны $010$ , $11$ . Коды остальных букв имеют одинаковую длину. Какова минимальная суммарная длина всех кодовых слов у букв передаваемого слова?

Показать ответ и решение

$PIC$

Тогда $3+ 4 +4 + 4+ 4+ 4 + 4+ 4+ 4 +2$ = $37$

Ответ: 37

Ошибка.
Попробуйте повторить позже

Задача 2#40703

По каналу связи передаются сообщения, содержащие только шесть букв: $D, O,S, K,$ $A,L$ . Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: $S$ — $10$ , $O$ — $11$ , $K$ — $01$ , . Какое наименьшее количество двоичных знаков потребуется для кодирования слова $DDOS$ ?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

Нарисуем бинарное дерево. Как видим, после расстановки букв $S,O, K$ остается ровно $1$ свободная ветка, которую мы не можем занять буквой $D$ , так как остались и другие буквы. Следовательно, нам следует спуститься еще на один уровень по дереву. Так как нас волнует только длина буквы $D$ , мы можем сразу «подвесить» букву $D$ на ветку длины $3$ . Тогда ответ равен $3 + 3 + 2 + 2 = 10$

Ответ: 10

Ошибка.
Попробуйте повторить позже

Задача 3#40694

Для кодирования некоторой последовательности, состоящей из букв К, А, Л, Ч, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, А, Л, Н использовали соответственно кодовые слова $00$ , $010$ , $101$ , $1101$ . Найдите кратчайшее возможное кодовое слово для буквы Ч, если таких слов несколько, то в ответе укажите код с наименьшим числовым значением.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

Нарисуем бинарное дерево. Из картинки видно, что есть две свободные ветки минимальной длины $3$ , наименьшее значение имеет ветка $011$ .

Ответ: 011

Ошибка.
Попробуйте повторить позже

Задача 4#33498

По каналу связи передаются сообщения, содержащие только шесть букв: К, А, Л, Ч, Н, И. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Л — $1$ , Н — $01$ . Какое наименьшее количество двоичных знаков потребуется для кодирования слова КАЛАЧИК?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

Разместим все буквы так, чтобы суммарно длина кодового слова была минимальна:

$PIC$

В этом случае длина кодового слова для КАЛАЧИК равна 4 + 4 + 1 + 4 + 4 + 4 + 4 = 25.
Попробуем разместить буквы иначе, вдруг можно получить кодовое слово, длина которого меньше той, что мы нашли:

$PIC$

В этом случае длина кодового слова для КАЛАЧИК равна 3 + 4 + 1 + 4 + 5 + 5 + 3 = 25.
В обоих случаях получилась суммарная длина $25$ , значит, мы нашли ответ.

Ответ: 25

Ошибка.
Попробуйте повторить позже

Задача 5#30058

Марафонец кодирует буквы К, Р, А, Б, Ы неравномерным двоичным кодом, который удовлетворяет обратному условию Фано. Известно, что букве К соответствует код 00, букве Р - 01, а букве А - 11. Укажите кодовое слово для буквы Б, если известно, двоичный код обладает минимально возможной длиной и что у него минимальное численное значение.

Показать ответ и решение

Не забываем, что граф у нас "перевёрнутый"!

$PIC$

Ответ: 010

Ошибка.
Попробуйте повторить позже

Задача 6#30057

По каналу связи передаются сообщения, содержащие только все заглавные буквы русского алфавита. Для передачи используется двоичный код, допускающий однозначное декодирование. Укажите минимальную возможную длину закодированной последовательности ПАРАЛЛЕЛЬ.

Показать ответ и решение

Подвешиваем все буквы на бинарное дерево и не забываем оставить $1$ свободную ветку для остальных букв алфавита.

$PIC$

Складываем длины кодов каждой буквы и получаем ответ: $3+ 2 + 3+ 2+ 2 + 2+ 3+ 2+ 4 = 23$

Ответ: 23

Ошибка.
Попробуйте повторить позже

Задача 7#30056

Крабозавр закодировал буквы Ч, А, Й равномерным двоичным кодом. Известно, что буквам Ч, А соответствуют кодовые слова 0010, 1101. Также известно, что кодовые слова отличаются минимум двумя знаками. Найдите кодовое слово для буквы Й, при условии, что оно начинается и заканчивается 1.

Показать ответ и решение

Так как оно начинается и заканчивается единицей - оно уже отличается от кодового слова Ч на 2 знака. Чтобы оно отличалось от кодового слова буквы А на 2 знака, достаточно поменять 10 на 01 в середине слова.

Ответ: 1011

Ошибка.
Попробуйте повторить позже

Задача 8#30055

Машина дикая бешеная совсем взбесилась и закодировала заглавные буквы русского алфавита неравномерным двоичным кодом, удовлетворяющим условию Фано. Он вспомнил, что у всех кодовых слов длина больше $2$ символов, но при том минимально возможная. Слову ОБМАН соответствует код $111101011000001$ . Помогите машине дикой бешеной найти код для слова БОМБА.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

Так как длина каждого кодового слова не меньше $2$ символов и минимальна, а букв $5$ , то можно сделать вывод, что длина каждого кодового слова равна $3$ . Разобьём код слова ОБМАН на тройки справа налево: $111 101 011 000 001$ . Таким образом, букве О соответствует код $111$ , Б — $101$ , М — $011$ , А — $000$ , Н — $001$ . Тогда нетрудно записать код слова БОМБА, используя полученные выше коды.

Получаем ответ: $101111011101000$

Ответ: 101111011101000

Ошибка.
Попробуйте повторить позже

Задача 9#30054

Доктор Пескоедус кодирует фамилии пациентов неравномерным двоичным кодом, который удовлетворяет условию Фано. Для букв НОГЬ он использовал трехразрядное двоичное представление чисел 3, 4, 5, 6. Закодируйте слово ОГОНЬ таким образом и результат запишите в ответ.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

По условию, букве Н соответствует кодовое слово 011, О - 100, Г - 101, Ь - 110. Тогда несложно записать слово ОГОНЬ как $100101100011110$ .

Ответ: 100101100011110

Ошибка.
Попробуйте повторить позже

Задача 10#30053

Для кодирования букв МНРАК использовали неравномерный двоичный код, удовлетворяющий условию Фано. Известно, что у букв М, Н, Р кодовые слова соответственно равны 001, 01, 000 а у остальных букв они имеют минимальную длину. Также известно, что у буквы А численное значение кодового слова меньше, чем у буквы К. Расшифруйте последовательность 11100000011001. В ответ запишите последовательность больших букв.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

Так как у буквы А численное значение кодового слова меньше чем у К $⇒$ присвоим ей код 10.

11100000011001 = 11 10 000 001 10 01 = K A P M A H

Ответ: КАРМАН

Ошибка.
Попробуйте повторить позже

Задача 11#30052

Для передачи слова ПЛЮШКА решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Известно, что у букв П, Л, Ю, Ш кодовые слова соответственно равны 00, 010, 101, 011. Также известно, что у буквы К код имеет минимально возможную длину. Закодируйте последовательность ПЛЮШКА и запишите в ответ значение кода в шестнадцатеричной системе счисления.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

00 010 101 011 11 100 2 = 157C16

Ответ: 157C

Ошибка.
Попробуйте повторить позже

Задача 12#30051

Билл Гейтс шифрует слова. Для кодирования последовательности, состоящей из букв слова ЧИПИРИК решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Ч использовали кодовое слово 010, для буквы И — 11, П - 10. Укажите, какова наименьшая длина всех символов заданного слова.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

3 +2 + 2+ 2+ 3(2)+ 2+ 2(3) = 16

Ответ: 16

Ошибка.
Попробуйте повторить позже

Задача 13#30050

Мистер Крабс решил закодировать рецепт Крабсбургера двоичным кодом, удовлетворяющим условию Фано. Известно, что в рецепте содержится 136 букв и все кодовые слова имеют одинаковую длину. Определите длину кодового слова.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

Чтобы закодировать 2 буквы двоичным кодом с минимальным количеством символов, нам потребуется всего 2 цифры - 1 и 0. Чтобы закодировать 3 или 4 буквы - уже нужно будет 4 кода: 00, 01, 10, 11, при условии, что их длина должна быть одинаковой. Аналогично для большего числа букв.

Таким образом, получаем формулу $n−1 n 2 < I ≤ 2$ , где $I$ - количество символов, которые надо закодировать, а $n$ - длина одного кодового слова.

Подставляем значения из задачи $2n−1 < 136 ≤ 2n ⇒ n = 8$ .

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 14#30049

Программист по каналу связи передаёт сообщения, содержащие только заглавные русские буквы ИНФОРМАТ. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: И — 1, Н — 001, Ф — 000, О — 010. Какое минимальное количество бит потребуется, чтобы закодировать слово ИНФОРМАТ?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

Так как нам необходимо закодировать слово ИНФОРМАТ минимальным количеством бит $⇒$ оставшиеся 4 буквы будем кодировать минимальным количеством символов, то есть бит.

Итого: $1 + 3+ 3+ 3 + 5⋅4 = 30$

Ответ: 30

Ошибка.
Попробуйте повторить позже

Задача 15#30046

Для кодирования некоторой последовательности, состоящей из букв С, К, Л, Д, Р решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв С, К, Л, Д использовали соответственно кодовые слова 00, 010, 100, 11. Укажите кратчайшее возможное кодовое слово для буквы Р, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

$0112 < 1012 ⇒$ ответ 011.

Ответ: 011

Ошибка.
Попробуйте повторить позже

Задача 16#30045

Для кодирования слова $Щ ЕЛЧ ОК$ решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Известно, что буквы $Щ, Е, Л, Ч, О$ закодированы кодовыми словами $10, 11, 01, 000, 0010$ соответственно. Укажите кратчайшее возможное кодовое слово для буквы $К$ .

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

Ответ: 0011

Ошибка.
Попробуйте повторить позже

Задача 17#29439

По каналу связи передаются сообщения, содержащие только семь букв: П, И, Ф, А, Г, О, Р; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв П, И, Ф используются такие кодовые слова: П: $1$ , И: $011$ , Ф: $001$ . Укажите кратчайшее кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.

Показать ответ и решение

Ответ: 000

Ошибка.
Попробуйте повторить позже

Задача 18#29351

Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, удовлетворяющим условию Фано, где никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово ВОЛОС закодировано последовательностью букв соответственно $011$ $100$ $101$ $100$ $001.$ Какое наименьшее число двоичных знаков может содержать код слова ПОВОРОТ?

Показать ответ и решение

$PIC$

Так как в задаче сказано, что слово ВОЛОС закодировано соответственно некоторому кодовому слову, то каждой букве соответствует кодовое слово длины $3$ (они разделены между собой пробелами). Разместим буквы ПбР и Т на самые короткие веточки. Посчитаем общую длину слова ПОВОРОТ: $3+ 3+ 3 +3 + 3+ 3+ 3 = 21$

Ответ: 21

Ошибка.
Попробуйте повторить позже

Задача 19#28800

Для кодирования некоторой последовательности, состоящей из букв $А, Д, И, Л, Ь, Н$ решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв $Л$ и $Ь$ использовали кодовые слова $010$ и $10$ соответственно. Укажите минимальное количество бит, которое потребуется, чтобы закодировать слово $Д ИА НА$ ?

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

Так как буква $А$ в слове $ДИ АН А$ повторяется $2$ раза, то нужно разместить её на короткую веточку, но так, чтобы длина всего кодового слова была минимальна. Получим, что $Д$ — $011,$ $И$ — $110,$ $А$ — $00,$ $Н$ — $111.$

Длина кодового слова равна: $2 + 2+ 3+ 3+ 3 = 13$ .

Ответ: 13

Ошибка.
Попробуйте повторить позже

Задача 20#27986

По каналу связи передаются сообщения, содержащие только шесть букв: П, Р, О, Ф, Б, Ю; для передачи используется двоичный код, удовлетворяющий условию Фано. Буквы Б, Ю, Р имеют коды $110,011$ и $111$ соответственно. Укажите наименьшую возможную длину закодированной последовательности для слова РОБОПРОФ.

Условие Фано — никакое кодовое слово не является началом другого кодового слова.

Показать ответ и решение

Получаем общую длину: 3 + 2 + 3 + 2 + 2 + 3 + 2 + 3 = 20.

Ответ: 20