Задача: 23D555

Ваня шифрует русские слова, записывая вместо каждой буквы её номер в алфавите (без пробелов). Номера букв даны в таблице. | А | 1 | Й | 11 | У | 21 | Э | 31 | | --- | --- | --- | --- | --- | --- | --- | --- | | Б | 2 | К | 12 | Ф | 22 | Ю | 32 | | В | 3 | Л | 13 | Х | 23 | Я | 33 | | Г | 4 | М | 14 | Ц | 24 | | | | Д | 5 | Н | 15 | Ч | 25 | | | | Е | 6 | О | 16 | Ш | 26 | | | | Ё | 7 | П | 17 | Щ | 27 | | | | Ж | 8 | Р | 18 | Ъ | 28 | | | | З | 9 | С | 19 | Ы | 29 | | | | И | 10 | Т | 20 | Ь | 30 | | | Некоторые шифровки можно расшифровать несколькими способами. Например, 311333 может означать «ВАЛЯ», может – «ЭЛЯ», а может – «ВААВВВ». Даны четыре шифровки: 916151 812030 322121 915113 Только одна из них расшифровывается единственным способом. Найдите её и расшифруйте. Получившееся слово запишите в качестве ответа. --- Номер задачи: 23D555 📚 # Тема 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" для новой буквы. Это нарушает Фано! В дереве у узла А нет потомков.