Префиксные коды, условие Фано и выбор допустимого кодового слова.
В типовых задачах дан набор двоичных кодов и требуется подобрать ещё один код так, чтобы сообщение декодировалось однозначно. Удобнее всего мыслить двоичным деревом.
Последовательность битов, назначенная символу.
Начальная часть другого кодового слова.
Ни одно кодовое слово не является началом другого.
Если слово 01 уже используется, нельзя добавлять ни 0 (это префикс 01), ни 010 (01 станет префиксом нового слова).
От корня ветвь 0 идёт влево, 1 — вправо. Занеси уже заданные слова.
Если вершина уже является кодовым словом, ниже неё новые слова брать нельзя.
Для минимальной длины сначала рассматривай 1 бит, потом 2, затем 3.
Новое слово не должно быть префиксом старого, и старое — префиксом нового.
Пусть A=00, B=01, C=10. Какой кратчайший код можно дать символу D?
Ветви 0 и 1 нельзя использовать как отдельные коды, потому что они стали бы префиксами уже существующих слов. Свободный двухбитовый лист — 11.
Коды 0 и 1 запрещены: каждый станет префиксом уже заданных слов.
00, 01 и 10 заняты. Остаётся 11.
Кратчайший допустимый код D = 11.
Ответь на оба вопроса. Проверка работает прямо в браузере; правильные ответы автоматически отмечают практику выполненной.
Тематика урока сверена с актуальным каталогом ЕГЭ‑2026. Каталог заданий ↗