генератор заданийусловие Фанобез регистрации
Условие Фано: тренажёр «Подбери код»
Дерево кода — это двоичное дерево, где код буквы задаёт путь от корня: 0 — влево, 1 — вправо. Расставь коды для оставшихся букв так, чтобы выполнялось условие Фано и сумма длин была минимальной.
Стратегия: как расставлять буквы
- Код — это путь. Из корня влево идёт 0, вправо — 1. Код буквы — путь от корня до листа: чем ближе узел к корню, тем короче код.
- Условие Фано. Ни один код не должен быть началом другого. Поэтому занятый код — всегда лист: ни под ним, ни над ним места нет.
- Заданные коды неприкосновенны. Они уже стоят на дереве зелёным — их подветки не трогаем и не «доращиваем».
- Считай глубину свободных узлов. Сначала занимай самые короткие свободные места (ближе к корню). Важно: заняв узел, ты закрываешь всё под ним, поэтому короткое место особенно ценно.
- Если букв больше, чем коротких мест — спустись в свободную ветку и раздели её на две (0 и 1). Повторяй, пока свободных листьев не станет ровно столько, сколько букв.
- Проверь: ни один код не начало другого; все буквы размещены; сумма длин минимальна.
заданный кодсвободная ветка
Как пользоваться этим режимом. Выбери букву в палитре и щёлкни по свободному месту дерева — код будет поставлен. Затем нажми «Проверить».
Загрузка практикума…
Частые вопросы
Что такое условие Фано?
Это требование к кодам: никакое кодовое слово не является началом (префиксом) другого. Тогда поток нулей и единиц разбивается на буквы однозначно.
Как пользоваться тренажёром?
Выбери букву в палитре и щёлкни по свободному месту дерева — код будет поставлен. Нажми «Проверить»: тренажёр проверит условие Фано и суммарную длину кодов.
Почему сумма длин должна быть минимальной?
Чем короче коды, тем компактнее сообщение. Минимум достигается, когда буквы занимают самые короткие свободные места дерева.