Как в ЕГЭ · 23 из 28
№4. Самые короткие коды по Фано
По мотивам задания №4. По каналу передают сообщения двоичным кодом, и часть букв уже получила кодовые слова. Код однозначно раскодируется, если выполнено условие Фано: ни одно кодовое слово не начинается с другого кодового слова. Осталось подобрать коды для нескольких новых букв — так, чтобы условие не нарушилось, а коды были как можно короче.
Что сделать
Подберите коды для новых букв по условию Фано так, чтобы их суммарная длина была наименьшей, и верните её.
Что приходит
kody— уже выданные кодовые слова: строки из 0 и 1, ни одно не начало другого; хотя бы одно естьnovyh— сколько новых букв нужно закодировать
Что вернуть
Наименьшую суммарную длину кодов новых букв числом; если места для новых кодов нет — None.
Допишите функцию naimenshaya_summa в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Коды «0» и «10» уже заняты. Новый код не может начинаться с «0» и с «10», а «1» — начало «10», значит, остаётся «11»: длина 2. Одной новой букве — ответ 2.
naimenshaya_summa(["0", "10"], 1)
2
Новые кодовые слова — непустые строки из 0 и 1. Вместе со старыми они должны выполнять условие Фано: ни одно кодовое слово (ни старое, ни новое) не является началом другого. Новые слова все разные.
Верните наименьшую возможную сумму длин novyh новых слов. Если новые слова добавить нельзя вовсе (любое новое слово нарушит условие) — None; при novyh, равном 0, — 0.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.