Задание №1025: Системы счисления
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова. Буква Кодовое слово Буква Кодовое слово А 00 Л 1101 Б Р 1000 Е 010 С 1110 И 011 Т 1001 К 1111 У 101 Укажите кратчайшее кодовое слово для буквы Б, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Что проверяет это задание
Задание относится к теме «Системы счисления». Для решения понадобятся:
- формализация задачи
- построение алгоритма
- проверка граничных случаев
Источник: ФИПИ — открытый банк заданий
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- ФИПИ — открытый банк заданий
- Организатор
- ФИПИ
- Материалы
- 0 файла
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Системы счисления» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Информатика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
Проверим свободные кодовые слова по условию Фано. Слова длины 1 и 2 использовать нельзя: они либо совпадут с началом уже заданного слова, либо сами будут иметь заданное слово 00 в качестве начала. Все трёхбитные варианты также заняты или конфликтуют: 000 и 001 начинаются с 00; 010, 011 и 101 уже используются; 100 является началом слов 1000 и 1001; 110 — началом 1101; 111 — началом 1110 и 1111. Среди четырёхбитных слов наименьшее допустимое — 1100: оно не совпадает ни с одним кодом и не является началом другого кодового слова. Ответ: 1100.
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Перепутать основание системы счисления.
- Не учесть границы диапазона.
- Проверить алгоритм только на одном примере.