Слова (2 часть). №4 ЕГЭ
2 часть подборки задач на нахождение минимального количества двоичных знаков для кодирования слова. Код, удовлетворяет условию Фано.
В заданиях этого вида нужно не просто найти кратчайшие кодовые слова для части букв, но и распределить их с учётом того, сколько раз встречаются буквы в заданном слове.
Подробнее о нахождении кодового слова для букв в 5 букв. №4 ЕГЭ. Шаблон двоичного дерева здесь.
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
№038AED
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Л, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Ч – 1, Л – 011. Для трёх оставшихся букв А, З и К кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЧАЛКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
решение
Отметим известные буквы и выберем возможные варианты для букв с неизвестными кодами.
Рассчитаем количество знаков и выберем лучший вариант:
Минимальное количество знаков – 14.
Добавляем знаки для ещё не посчитанных букв.
Количество двоичных знаков для слова: 14 + 1 + 3
№9AF5CD
По каналу связи передаются сообщения, содержащие только буквы из набора: А, В, Д, К, Р, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Р – 1, К – 0000. Для четырёх оставшихся букв А, В, Д и Н кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАРАВАН, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
решение
Отметим известные буквы и выберем возможные варианты для букв с неизвестными кодами.
Рассчитаем количество знаков и выберем лучший вариант:
Минимальное количество знаков – 14.
Считаем общее количество двоичных знаков в слове. Для этого к 14 добавляем длину кодовых слов ещё не учтённых букв.
Количество двоичных знаков для слова: 14 + 4 + 1
№36D956
По каналу связи передаются сообщения, содержащие только буквы из набора: В, Д, К, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 0, К – 1001. Для четырёх оставшихся букв В, Д, О и Р кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КОНОВОД, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
решение
Отметим известные буквы и выберем возможные варианты для букв с неизвестными кодами.
Рассчитаем количество знаков и выберем лучший вариант:
Минимальное количество знаков – 14.
Добавляем знаки для ещё не посчитанных букв.
Количество двоичных знаков для слова: 14 + 4 + 1
№B2EEE9
По каналу связи передаются сообщения, содержащие только буквы из набора: Г, Д, К, С, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: С – 0, К – 1011. Для четырёх оставшихся букв Г, Д, О и Р кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КОСОГОР, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
решение
Отметим известные буквы и выберем возможные варианты для букв с неизвестными кодами.
Рассчитаем количество знаков и выберем лучший вариант:
Минимальное количество знаков – 14.
Добавляем знаки для ещё не посчитанных букв.
Количество двоичных знаков для слова: 14 + 4 + 1
Примеры из Банка заданий ЕГЭ