задание 4 егэ кодирование, как найти минимальную длину кода для буквы
Застрял на задании 4 ЕГЭ. Дают коды нескольких букв, например А=00, Б=01, В=100, и просят: какой кратчайший код можно дать ещё одной букве Г, чтобы выполнялось условие Фано (однозначное декодирование)?
Я понимаю что код Г не должен конфликтовать с остальными, но как перебирать варианты и не запутаться — не соображу. Боюсь на этом задании потерять балл, оно вроде лёгкое.
2 ответа
Это классическое задание 4. Условие Фано двустороннее: новый код Г не должен быть началом чужих кодов И чужие коды не должны быть началом Г. Ищем САМЫЙ КОРОТКИЙ свободный код.
Дано: А=00, Б=01, В=100.
Идём по длинам, от коротких к длинным.
Длина 1. Кандидаты: 0 и 1.
0: является началом А (00) и Б (01) → нельзя.1: является началом В (100) → нельзя. Длина 1 не подходит.
Длина 2. Кандидаты: 00, 01, 10, 11.
00занят (А),01занят (Б).10: является началом В (100) → нельзя.11: ни с чем не конфликтует. Никакой код не начинается на11, и11не начинается ни с одного чужого. ПОДХОДИТ!
Ответ: кратчайший код для Г = 11, длина 2.
Как не путаться, держи алгоритм:
- Перебирай длины по возрастанию: сначала все коды длины 1, потом длины 2 и т.д.
- Для каждого кандидата проверь обе стороны: (а) не начинается ли кандидат с чужого кода, (б) не начинается ли чужой код с кандидата.
- Первый прошедший = ответ.
Удобная картинка — двоичное дерево: занятые коды «перекрывают» все ветки под собой. Свободные листья на минимальной глубине и есть кандидаты. Но на экзамене проще тупо перебрать как выше, кодов там немного.
Типичная ошибка — проверять только в одну сторону («чтобы Г не был началом чужих»), а забывать вторую («чтобы чужой не был началом Г»). Проверяй ОБА направления, иначе на длинных кодах словишь неправильный ответ.
И перебирай строго от коротких к длинным — как только нашёл подходящий, это и есть минимум, дальше не ищи.
