Условие Фано — ★ решаем программой

★ Решаем программой

Эта тетрадь — со звёздочкой. Всё задание 4 спокойно решается деревом на полях, и на экзамене так и делают: быстрее и надёжнее. Программа тут не замена карандашу, а проверка.

Зачем она нужна. Дерево даёт ответ, но не доказательство: а вдруг есть расстановка похитрее? Перебор отвечает на это честно — он не пропускает варианты по определению. Плюс на десяти буквах дерево уже не влезает на лист, а код не замечает разницы.

Ниже — шесть программ, по одной на каждую тетрадь урока. Все они собраны из одного кирпича, так что читать стоит подряд.

Кирпич первый: проверка условия Фано

С него начинается всё остальное. Условие Фано — это «никакое слово не является началом другого», и в Python «начинается с» — готовый метод startswith.

Перебираем все пары кодов. Условие i != j обязательно: без него слово сравнится само с собой, а любая строка начинается сама с себя — и функция всегда возвращала бы False.

Вторая функция, alldec, перебирает все способы разрезать строку на кодовые слова. Работает рекурсивно: примеряет к началу строки каждый код, и если код подошёл — откусывает его и решает ту же задачу для остатка. Когда строка кончилась, накопленное слово попадает в список. Если способов больше одного — код бракованный, и мы увидим оба прочтения.

Что выводит

False
['АВ', 'БА']

Вердикт и обе расшифровки строки 010 — ровно то, что мы разбирали на картинках в первой тетради. Только теперь это не рассуждение, а факт.

Кирпич второй: перебор кодовых слов

Чтобы найти свободное место, нужно уметь перечислять двоичные слова в правильном порядке: сначала все короткие, потом длиннее, а внутри одной длины — по возрастанию значения. Именно так ты сам просматриваешь дерево.

Внешний цикл идёт по длине L, внутренний — по числам от 0 до 2**L−1. Функция bin(i)[2:] переводит число в двоичную запись, а rjust(L, "0") дополняет её нулями слева до нужной длины — иначе код 011 превратился бы в 11.

Порядок перебора гарантирует, что первый найденный ответ и есть кратчайший, а среди равных по длине — наименьший по значению. Это ровно те две оговорки, что стоят в условиях экзамена.

Что выводит

11

То же, что мы нашли по дереву. exit() останавливает программу на первом же слове — искать дальше незачем, оно и так кратчайшее.

Кирпич третий: не забыть про оставшиеся буквы

Вот здесь программа обыгрывает карандаш. Главная ловушка задания — занять точку повыше и оставить остальные буквы без места. Код физически не может про них забыть: они прописаны в проверке.

Функция vlezut отвечает на вопрос «поместятся ли ещё n букв при таких занятых кодах». Она идёт по свободным словам и жадно набирает их, пропуская конфликтующие. Главный цикл берёт кандидатов в правильном порядке и принимает первого, кто прошёл обе проверки: и условие Фано, и «остальным хватило места».

Самое полезное здесь — переменная ostalos. Поставь 0, потом 1 — и увидишь, как один и тот же вопрос даёт разные ответы.

Что выводит

110

Не 11, а 110 — потому что ostalos = 1. Поменяй на 0 и запусти снова: ответ станет 11. Одна переменная — и совсем другая задача.

Кирпич четвёртый: доказать, что меньше не бывает

Дерево даёт хорошую расстановку. Перебор доказывает, что лучшей не существует, — и в этом вся его ценность.

combinations(pool, n) из модуля itertools выдаёт все сочетания по n слов из списка кандидатов. Каждое проверяется вместе с занятыми кодами, у прошедших считается сумма длин, а переменная best хранит лучшее из встреченного.

Кандидатов ограничиваем длиной 6: коды длиннее в таких задачах заведомо не нужны, а без ограничения перебор был бы бесконечным.

Что выводит

11

Это сумма для оставшихся букв. Прибавь то, что дано в условии — 1 за А и 2 за Б, — и получишь сумму всех пяти: 14. Если перебор говорит 11, значит меньше невозможно, и дерево нас не обмануло.

Кирпич пятый: расшифровка

Функция rasshifrovat делает буквально то же, что ты делаешь глазами, только не сбивается. Она копит биты в переменной bufer и на каждом шаге проверяет, не стал ли буфер чьим-то кодом. Стал — приписываем букву и обнуляем буфер.

Проверка bufer != "" в конце ловит испорченное сообщение: если биты остались, а буквы не вышло, значит сообщение не по этому коду.

Словарь obratno переворачивает таблицу — из «код → буква» делает «буква → код». После этого длина слова в битах считается сложением длин.

Что выводит

АБВГАБАВ
16

Слово и его длина в битах. Заметь: расшифровали сообщение и тут же посчитали длину — то есть закодировали обратно и получили те же 16 бит, с которых начали.

Кирпич шестой: обратное условие

Самая приятная программа урока, потому что писать её почти не пришлось. Разница с первой проверкой ровно в одном методе: вместо startswith стоит endswith — «заканчивается на». Всё остальное — те же строчки.

Это и есть главный вывод: одна замена слова в одной строке, и вся наработанная техника продолжает работать. Не нужно держать в голове второй способ решения — нужно помнить, где поменять начало на конец.

Что выводит

True
100

Вердикт и кратчайшее слово, которое можно добавить. Проверь руками: ни один из кодов 1, 010, 000 не является окончанием 100.