Задача к ЕГЭ по информатике на тему «Общая длина кода» №1

Просмотров 6 Комментарии 0

Мистер Крабс решил закодировать рецепт Крабсбургера двоичным кодом, удовлетворяющим условию Фано. Известно, что в рецепте содержится 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