5 букв
Задания, в которых для кодирования используется 5 букв. Для части букв кодовые слова известны. Нужно найти минимальную сумму длин кодовых слов для для оставшихся букв или же для всех пяти букв. Код соответствует условию Фано.
Подробнее о нахождении кодового слова для буквы в 4 буквы. №4 ЕГЭ (№3D61E7).
№A98AE0
По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код. Для букв А, Б и В используются кодовые слова 1100, 1110, 11010 соответственно. Укажите минимальную сумму длин кодовых слов для букв Г и Д, при котором код будет удовлетворять условию Фано.
решение
Таким образом, 2 кодовых слова, дающих в сумме минимальную длину – это 0 и 10. Для решения этой задачи не имеет значения какой именно букве будет соответствовать каждое слово. Сумма их длин равна 3.
№F4F332
По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код. Для букв А, Б и В используются кодовые слова 101, 110, 1000 соответственно. Укажите минимальную сумму длин кодовых слов для букв Г и Д, при котором код будет удовлетворять условию Фано.
решение
№76E4A0
По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код. Для букв А, Б и В используются кодовые слова 001, 010, 0111 соответственно. Укажите минимальную сумму длин кодовых слов для букв Г и Д, при которых код будет удовлетворять условию Фано.
решение
Возможны два варианта, когда сумма длин минимальна:
В обоих случаях сумма длин кодовых слов равна 4.
№15013A
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0. Какова наименьшая возможная сумма длин всех пяти кодовых слов?
решение
Найдём минимальную сумму длин неизвестных кодовых слов для 4 букв. Сложим с длиной кодового слова буквы А (слово состоит из одной цифры, значит длина равна 1).
Ищем 4 листа, расположенные как можно ближе к корню двоичного дерева. Подходящий вариант:
Сумма длин кодовых слов = 3 * 4 + 1
Примеры из Банка заданий ЕГЭ