ФИПИ · ОГЭ · все форматы ответа · 1585 заданий
Тип задачи: Кодирование и декодирование.
| КЭС: | 2.1 Дискретность данных. Возможность описания непрерывных объектов и процессов с помощью дискретных данных. Символ. Алфавит. Мощность алфавита. Двоичный алфавит. Количество всевозможных слов (кодовых комбинаций) фиксированной длины в двоичном алфавите. Преобразование любого алфавита к двоичному. Количество различных слов фиксированной длины в алфавите определённой мощности. Кодирование символов одного алфавита с помощью кодовых слов в другом алфавите, кодовая таблица, декодирование. Кодирование текстов. Равномерный код. Неравномерный код. Кодировка ASCII. Восьмибитные кодировки. Понятие о кодировках UNICODE. Декодирование сообщений с использованием равномерного и неравномерного кода. Информационный объём текста |
| Тип ответа: | Краткий ответ |
Ответ: ОВОД
1. Как восстановить границы кодов.
В сообщении нет разделителей между буквами, а коды могут иметь разную длину. Поэтому нельзя произвольно отделять одинаковое число символов. Используем только коды из условия и проверяем, что вся цепочка разбивается на них без остатка.
Кодовая таблица: А — «01»; В — «011»; Д — «100»; О — «111»; Р — «010»; У — «001».
2. Разберём варианты.
Цепочка 01001001. «АУУ»: 01 | 001 | 001; «РАУ»: 010 | 01 | 001. Эти два различных разбиения уже доказывают неоднозначность; такая цепочка не подходит.
Цепочка 0100100101. «АУУА»: 01 | 001 | 001 | 01; «РАУА»: 010 | 01 | 001 | 01. Эти два различных разбиения уже доказывают неоднозначность; такая цепочка не подходит.
Цепочка 111011111100. «ОВОД»: 111 | 011 | 111 | 100. Найдено единственное разбиение; ниже проверим его единственность.
3. Почему других подходящих расшифровок нет.
Пронумеруем позиции между символами выбранной цепочки от 0 до 12. Для конца цепочки число способов продолжения равно 1: ничего добавлять не нужно. Двигаясь справа налево, в каждой позиции складываем числа способов для тех следующих позиций, куда ведёт целый код из таблицы. Если ни один код не подходит, получаем 0. Это учитывает все возможные границы букв.
Число способов для позиций от 0 до 12:
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1.
Первое число равно 1, значит, полное разбиение единственно. Оно даёт «ОВОД».
4. Проверка.
Заменим буквы «ОВОД» их кодами:
111 | 011 | 111 | 100.
После удаления разделителей получаем исходную цепочку «111011111100». Длина совпадает: 3 + 3 + 3 + 3 = 12 символов. Все символы использованы по порядку, ни один не пропущен и не добавлен.
Ответ: ОВОД.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании OGEINF2BBE27.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.