ОГЭ, задание 2
Второе задание экзамена. Даны кодовая таблица и цепочка символов. Надо понять, где кончается один код и начинается следующий.
Задание стоит 1 балл и решается за две-три минуты — но только если знать, что делать на развилке. Именно развилка и есть вся задача.
как устроен код
Каждой букве назначен свой код. Слово кодируют, склеивая коды подряд — без пробелов и разделителей.
| А | Д | К | Н | О | С |
| 01 | 100 | 101 | 10 | 111 | 000 |
НОС → 10111000
Закодировать легко: смотрим в таблицу и выписываем. Вся работа — в обратную сторону.
в чём подвох
В той же таблице Н = 10, а К = 101 и Д = 100. Код одной буквы оказался началом кода другой.
Дошли до 101… — и не знаете сразу: это К целиком или Н, а единица уже от следующей буквы?
Проверить можно только одним способом: попробовать и посмотреть, что будет дальше.
Если ни один код не является началом другого, разрез единственный и очевидный. Это называют условием Фано.
Но экзаменационные задачи почти всегда его нарушают — намеренно. Иначе задачи бы не было.
метод
Главная ошибка: дойти почти до конца, увидеть, что последние символы не складываются, и решить, что ошибся в таблице. Нет — надо вернуться к последней развилке.
разбираем развилку
Та же таблица, цепочка 10111101. С начала подходят Н = 10 и К = 101.
Сошлось до последнего символа: НОК.
Осталось 01 — это А, тоже сходится: КОА. Два разбора!
Здесь оба варианта дошли до конца — значит у цепочки две расшифровки. На экзамене такие цепочки и дают в задаче «найди ту, у которой расшифровка одна».
что даёт однозначность
| что написано в условии | что это значит для разбора |
|---|---|
| ничего дополнительно | цепочка подобрана так, что разрез единственный: все лишние ветки упрутся в тупик |
| «буквы в нём не повторяются» |
развилку режет не тупик, а оговорка: уже занятую букву второй раз брать нельзя. Без неё разрезов было бы несколько — значит пользоваться ей обязательно |
| «найдите ту, у которой одна расшифровка» |
мало найти один разрез — надо у каждой цепочки перебрать все и посчитать |
особый случай
Тогда развилок нет вовсе: делим длину цепочки на длину кода и режем на равные части.
| А | Б | В | Г | Д | Е |
| ..o.. | .o..o | .oo.o | .oooo | ...o. | .o.oo |
25 символов : 5 = 5 букв. Дальше просто выписываем их и смотрим, какие встретились дважды.
Такие задачи и спрашивают не текст, а какие буквы повторяются. Ответ — сами буквы, порядок любой: официальный ключ демоверсии так и записан — «АБ; БА».
одно и то же в разной одежде
Разрезать цепочку из нулей и единиц или из точек и тире — одна и та же работа. Символы кода на решение не влияют никак, они только меняют вид условия.
как записывают ответ
Информатику сдают за компьютером: ответ вы набираете с клавиатуры в экзаменационной программе. Лишний пробел или приписанное слово — и верное решение засчитано не будет. Набрали — перечитайте, что стоит в поле.
итог
Разрезать цепочку на коды. Различаются только две вещи.
Тупиком — лишняя ветка не доходит до конца
Оговоркой «буквы не повторяются»
Ничем — надо самому посчитать разборы у каждой из нескольких цепочек
Равномерностью кода — развилок нет
Сообщение — буквы подряд
Сколько букв — число
Какие буквы повторяются — сами буквы
Прочитайте вопрос до конца: разобрать цепочку и записать не то, что спросили, — самая обидная потеря балла в этом задании.
Дальше — тренажёр: двенадцать задач, по две на каждый тип. Таблицы и цепочки у всех свои, проверка сразу.