Задание 2: префиксный код и условие Фано

1. 1. Склеиваем поток без пробелов: 111001101001111. Читаем слева направо по одному биту.
2. 2. 1 — нет такой буквы; 11 — нет; 111 — нет; 1110 = Г. Остаток: 01101001111.
3. 3. 0 = А. Остаток: 1101001111. Далее 1 — нет; 11 — нет; 110 = В. Остаток: 1001111.
4. 4. 10 = Б. Остаток: 01111. 0 = А. Остаток: 1111 = Д.
5. 5. Получилось ГАВБАД — ровно шесть букв, как обещано в условии. Совпадение числа букв — главная проверка: если букв вышло больше или меньше, где-то отрезан не тот кусок.

Ответ: ГАВБАД

1. 1. Проверяем каждый вариант на условие Фано: кодовое слово не должно быть началом другого и другие не должны быть его началом.
2. 2. 1) 11 — является началом слова В (110). Нельзя.
3. 3. 2) 1100 — начинается со 110, то есть В является его началом. Нельзя.
4. 4. 3) 111 — сравниваем с 0, 10, 110: ни одно из них не начинается с 111, и 111 не начинается ни с одного из них (после 1 идёт 1, а у Б после 1 идёт 0; у В третий бит 0, а здесь 1). Подходит.
5. 5. 4) 0110 — начинается с 0, а это код буквы А. Нельзя.
6. 6. Ответ 3. Приём: проверяй пары в обе стороны, иначе легко пропустить случай, где новое слово длиннее старого.

Ответ: 3

1. 1. Выписываем код каждой буквы по порядку: Б = 10, А = 0, Г = 111, А = 0, В = 110.
2. 2. Склеиваем: 10 + 0 + 111 + 0 + 110 = 1001110110.
3. 3. Считаем длину: 2 + 1 + 3 + 1 + 3 = 10 бит.
4. 4. Смысл неравномерного кода: при равномерном кодировании четырёх букв нужно по 2 бита на каждую, то есть 10 бит на пять букв — столько же. Выигрыш появляется, когда частые буквы получают короткие коды: в тексте, где А встречается вдвое чаще остальных, такой код будет экономнее равномерного.

Ответ: 10

1. 1. Замысел: идём по потоку слева направо, копим биты в буфер; как только буфер совпал с каким-то кодовым словом, выводим букву и очищаем буфер. Так работает свойство префиксного кода — возвращаться назад не нужно.
2. 2. Код целиком (Python): code = {'0': 'А', '10': 'Б', '110': 'В', '1110': 'Г', '1111': 'Д'} / s = input() / buf = '' / res = '' / for bit in s: / buf = buf + bit / if buf in code: / res = res + code[buf] / buf = '' / print(res).
3. 3. Трассировка на входе 111001101001111: buf растёт 1 → 11 → 111 → 1110 (совпало, res = «Г», buf пуст) → 0 (совпало, res = «ГА») → 1 → 11 → 110 (совпало, «ГАВ») → 1 → 10 (совпало, «ГАВБ») → 0 (совпало, «ГАВБА») → 1 → 11 → 111 → 1111 (совпало, «ГАВБАД»).
4. 4. Что проверить перед сдачей: после цикла буфер обязан оказаться пустым. Если в нём что-то осталось, поток декодирован не до конца — значит, либо в последовательности ошибка, либо таблица кода неполная. Полезно добавить строку if buf: print('остаток:', buf) для себя, но в сдаваемом файле оставить один итоговый вывод, как требует задание 16.
5. 5. Как сохранять: обычный текстовый файл с расширением .py; эксперт читает текст программы, а не запускает её, поэтому важнее всего, чтобы алгоритм читался однозначно.

Ответ: decode.py: буфер битов, сверка со словарём кода, вывод одной строки