Задача: C4051E

Вася и Петя играли в шпионов и кодировали сообщения собственным шифром. Фрагмент кодовой таблицы приведён ниже. | К | Л | М | П | О | И | | --- | --- | --- | --- | --- | --- | | **@ +** | **~ +** | **+ @** | **@ ~ +** | **+** | **~** | Расшифруйте сообщение, если известно, что буквы в нём **не повторяются**. **+ ~ + ~ + @ @ ~ +** Запишите в ответе расшифрованное сообщение. --- Номер задачи: C4051E 📚 # Тема 02. Кодирование и декодирование информации На ОГЭ эта тема проверяет умение расшифровывать сообщения по кодовой таблице и составлять коды, удовлетворяющие условию однозначного декодирования. --- ## 1. Что такое префиксный код **Префиксный (безпрефиксный) код** — система кодирования, где ни один код не является началом другого. Это позволяет однозначно декодировать любое сообщение. **Условие Фано (условие однозначного декодирования):** > Ни один кодовый символ не должен быть **началом** другого кодового символа. ### Пример допустимой таблицы: | Буква | Код | |-------|-----| | А | 0 | | Б | 10 | | В | 110 | | Г | 111 | Здесь `0` не является началом `10`, `110`, `111` → условие Фано выполнено ✓ ### Пример недопустимой таблицы: | Буква | Код | |-------|-----| | А | 0 | | Б | 01 | Код `А = 0` — это начало кода `Б = 01` → однозначное декодирование **невозможно** ✗ --- ## 2. Дерево кодирования Самый надёжный способ проверить условие Фано — построить **двоичное дерево**. **Правила построения:** - Из каждого узла выходит 2 ветки: **0** (влево) и **1** (вправо). - Буква помещается в **листовой узел** (из него нет продолжений). - Если в узле уже стоит буква — дальше по этой ветке идти нельзя. ``` [ ] / \ 0 1 / \ / \ А [B] [C] [D] / \ Б В ``` > **Совет:** Рисуйте дерево при каждой задаче. Это занимает 1-2 минуты, но исключает ошибки. --- ## 3. Типы задач на ОГЭ ### Тип 1: Декодирование сообщения **Задача:** Дана строка из 0 и 1, дана кодовая таблица. Расшифровать сообщение. **Алгоритм:** 1. Берём первый символ строки. 2. Проверяем — есть ли такой код в таблице? - Если да — записываем букву, переходим к следующему символу. - Если нет — добавляем следующий символ и снова проверяем. 3. Повторяем до конца строки. **Пример:** Таблица: А=0, Б=10, В=110, Г=111. Строка: `01011010` - `0` → А - `1` — нет. `10` → Б - `1` — нет. `10` → Б - `1` — нет. `10` → Б Ответ: А Б Б Б (но проверьте сами — задача может иметь другое решение) --- ### Тип 2: Проверить, выполнено ли условие Фано **Алгоритм:** 1. Для каждой пары кодов проверяем: является ли более короткий код началом более длинного? 2. Если хотя бы одна такая пара найдена — условие НЕ выполнено. **Быстрая проверка:** Нарисуйте дерево. Если все буквы оказались в листовых узлах — условие выполнено. --- ### Тип 3: Добавить новую букву с минимальным кодом **Задача:** Дана таблица. Добавить новую букву так, чтобы суммарная длина сообщения была минимальной. **Алгоритм:** 1. Нарисовать дерево с существующими кодами. 2. Найти свободные листовые узлы, ближайшие к корню (короткие коды). 3. Выбрать узел с наименьшей глубиной — это и будет новый код. > **Совет:** Минимальный код — самый короткий из доступных. Смотрите на свободные "ветки" дерева. --- ## 4. Типичные ошибки - **Читать слева направо без проверки.** Некоторые строки можно декодировать несколькими способами — если это так, значит условие Фано нарушено. - **Не строить дерево.** Без дерева легко пропустить конфликты. - **Забыть нули.** Код `0` и код `00` — разные! И `0` является началом `00`, что нарушает условие Фано. - **Перепутать "начало" и "конец".** Условие Фано — это про **начало** (префикс), а не конец суффикс кода. --- ## 5. Лайфхаки для ОГЭ > **Совет:** Если все коды имеют одинаковую длину — условие Фано всегда выполнено автоматически. > **Совет:** Для декодирования удобно подчёркивать каждую найденную букву в строке. > **Совет:** Чтобы быстро добавить новую букву — найдите в дереве самую "свободную" ветку. Если у узла на глубине 2 обе ветки свободны — возьмите одну из них (глубина 3 — это код из 3 символов). > **Совет:** Популярная ловушка — код "0" уже занят буквой А, а вы пытаетесь поставить "01" для новой буквы. Это нарушает Фано! В дереве у узла А нет потомков.