Что такое условие Фано?

Ни один код не совпадает с началом другого кода. Тогда сообщение без разделителей читается однозначно.

Как расшифровать сообщение руками?

Так же, как программа: слева направо, отделяя первый подходящий код.

Что если код записан в шестнадцатеричной системе?

Сначала переведите каждую цифру в четыре двоичных разряда, затем расшифровывайте.

Как посчитать способы расшифровки?

Рекурсией по позиции в сообщении: от каждой позиции пробуйте все коды, с которых начинается остаток строки, и складывайте результаты.

Задание 2 ОГЭ по информатике: решайте с автопроверкой

Задание 2 о кодировании. Каждой букве сопоставлен код из нулей и единиц, и сообщение записано без разделителей. Нужно расшифровать его или узнать, сколькими способами это можно сделать. Обычно номер решают на бумаге, а программа помогает проверить себя и разобраться, почему условие Фано делает расшифровку однозначной.

Решать задачи номера

Как решать программой

Если код удовлетворяет условию Фано (ни один код не начинает другой), расшифровка однозначна. Идите по сообщению слева направо и набирайте символы в группу: как только группа совпала с кодом буквы, допишите букву и начните новую группу.

В программе коды удобно хранить в словаре «код → буква». Проверка part in codes работает мгновенно.

Если условие Фано не выполнено, способов расшифровки может быть несколько. Их считает рекурсия: от текущей позиции пробуем каждый код, который подходит к началу оставшейся строки.

Задачи о том, сколькими способами можно расшифровать сообщение, проверяют понимание условия Фано. Если ответ больше одного, значит, условие нарушено.

Разбор примера

Коды букв: А 00, Б 010, В 011, Г 10, Д 110, Е 111. Расшифруем сообщение 10110111.

codes = {'00': 'А', '010': 'Б', '011': 'В', '10': 'Г', '110': 'Д', '111': 'Е'}
msg = '10110111'
word, part = '', ''
for bit in msg:
    part += bit
    if part in codes:
        word += codes[part]
        part = ''
print(word)

Программа печатает

ГДЕ

Сообщение делится на части 10, 110 и 111, это буквы Г, Д и Е. Код удовлетворяет условию Фано, поэтому другой способ разбить сообщение невозможен.

Решить эту задачу

Задачи к заданию 2

Расшифровка сообщения по кодуЛёгкаяРешать
Расшифровка с концаЛёгкаяРешать
Сколько способов расшифроватьСредняяРешать
Сообщение в шестнадцатеричной записиЛёгкаяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Что такое условие Фано?: Ни один код не совпадает с началом другого кода. Тогда сообщение без разделителей читается однозначно.
Как расшифровать сообщение руками?: Так же, как программа: слева направо, отделяя первый подходящий код.
Что если код записан в шестнадцатеричной системе?: Сначала переведите каждую цифру в четыре двоичных разряда, затем расшифровывайте.
Как посчитать способы расшифровки?: Рекурсией по позиции в сообщении: от каждой позиции пробуйте все коды, с которых начинается остаток строки, и складывайте результаты.