ЕГЭ Информатика 2020: Задание 5 — Код Фано

Задание связано с кодированием последовательности букв (К, Л, М, Н, О, П, Р) неравномерным двоичным кодом, удовлетворяющим условию Фано. Для букв К, Л, М, Н, О используются кодовые слова 000, 001, 010, 10, 11 соответственно. Необходимо найти кратчайшее кодовое слово для буквы П, при котором код удовлетворяет условию Фано. При наличии нескольких таких кодов следует выбрать код с наименьшим числовым значением.

Условие Фано

Условие Фано: никакое кодовое слово не должно быть началом другого кодового слова. Например:

  • Буква V: 1101
  • Буква W: 011

Условие Фано не выполняется, поскольку кодовое слово для V (1101) начинается с кодового слова для W (011). Для соблюдения условия Фано, никакое кодовое слово не должно быть префиксом другого.

Построение кодов

Используем имеющиеся кодовые слова:

  • К = 000
  • Л = 001
  • М = 010
  • Н = 10
  • О = 11

Построим кодовые слова для П и Р с помощью бинарного дерева.

Начнём с дерева, корень которого — 0. Ветви 000, 001 и 010 заняты. Единственно возможный вариант для Р – 011.

Теперь дерево с корнем 1. Ветви 10 и 11 заняты. Кратчайшим кодовым словом для П будет 10.

Выбор наименьшего кодового слова

Возможные варианты для кодового слова П: 011 и 10. Выбираем 10, так как оно имеет наименьшее числовое значение.

Кратчайшее кодовое слово для буквы П, удовлетворяющее условию Фано и имеющее наименьшее числовое значение — 10. Использование бинарных деревьев упрощает поиск подходящих кодовых слов и проверку условия Фано.

Что будем искать? Например,программа