Слова (1 часть). №4 ЕГЭ
1 часть подборки задач на нахождение минимального количества двоичных знаков для кодирования слова. Код, удовлетворяет условию Фано.
В заданиях этого вида нужно не просто найти кратчайшие кодовые слова для части букв, но и распределить их с учётом того, сколько раз встречаются буквы в заданном слове.
Подробнее о нахождении кодового слова для букв в 5 букв. №4 ЕГЭ. Шаблон двоичного дерева здесь.
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
№B85498
По каналу связи передаются сообщения, содержащие только буквы из набора: А, Б, К, Р, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 01, Р – 001. Для трёх оставшихся букв Б, Н и А кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова БАРАБАН, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
решение
Отметим известные буквы и выберем возможные варианты для букв с неизвестными кодами.
Нужно найти кратчайшие кодовые слова для трёх букв.
Выпишем, сколько раз встречается каждая из этих букв в слове БАРАБАН в порядке убывания:
А –3, Б – 2, Н – 1.
По каждому варианту определяем количество знаков на 1 букву. Чем чаще встречается буква, тем короче должно быть для неё кодовое слово и меньше количество знаков.
Определим, сколько знаков получилось для каждой буквы в слове. Например, буква А встречается в слове 3 раза, кодируется двумя знаками (2 вариант). 3 * 2 = 6
Сложим количество знаков, чтобы определить их общее количество в слове для букв А, Б, Н.
1 вариант: 3 * 1 + 2 * 4 + 1 * 4 = 15
2 вариант: 3 * 2 + 2 * 2 + 1 * 3 = 13
3 вариант: 3 * 3 + 2 * 3 + 1 * 3 = 18
Расчёты можно делать сразу в таблице:
Выбираем вариант с наименьшим количеством знаков, приходящихся на буквы в слове – второй.
Считаем общее количество двоичных знаков в слове. Для этого к уже посчитанному количеству знаков нужно добавить длину кодового слова буквы Р, она равна трём.
Количество двоичных знаков для слова: 16
№04FD12
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
решение
Отметим известные буквы и выберем возможные варианты для букв с неизвестными кодами.
Рассчитаем количество знаков и выберем лучший вариант:
Наименьшее количество знаков, приходящихся на буквы в слове – 11.
Добавляем знаки для ещё не посчитанных букв.
Не учли только букву З. Её кодовое слово 110, состоит из трёх знаков.
Количество двоичных знаков для слова: 11 + 3 = 14
№B17711
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 1, Н – 001. Для трёх оставшихся букв А, З и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАНТАТА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
решение
Отметим известные буквы и выберем возможные варианты для букв с неизвестными кодами.
Рассчитаем количество знаков и выберем лучший вариант:
Наименьшее количество знаков, приходящихся на буквы в слове – 14.
Добавляем знаки для ещё не посчитанных букв.
Код буквы К – 1, один знак. Код буквы Н – 001, три знака.
Количество двоичных знаков для слова: 14 + 1 + 3 = 18
Примеры из Банка заданий ЕГЭ