Задание №4 ЕГЭ Информатика с ответом и решением
Ответ: 101
Условие
По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т — 111, О — 0, П — 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Подсказки — как подойти к решению
- Проверяй слова-кандидаты по возрастанию длины: сначала однобитные, потом двубитные, затем трёхбитные. Для каждого проверяй условие Фано в обе стороны: слово не должно быть началом чужого и чужое слово не должно быть его началом.
- Отметь занятые ветви на дереве: одно из заданных слов закрывает целую ветвь, а ветвь, начинающаяся с единицы, разбита двумя другими словами. Искомое — самый короткий свободный лист, у которого нет ни занятых предков, ни занятых потомков.
- Если подходящих слов одинаковой длины несколько, выбери то, у которого меньше числовое значение: переведи кандидатов в десятичную запись и сравни. В ответ запиши само кодовое слово, а не его длину.
Решение
Буква С не может кодироваться строкой, которая начинается с 0, поскольку О имеет код 0.
Буква С не может кодироваться как 1, так как кодирование буквы Т начинается с 1.
Буква С не может кодироваться как 10, так как кодирование буквы П начинается с 10.
Буква С не может кодироваться как 11, так как кодирование буквы Т начинается с 11.
Буква С может кодироваться как 101 — это наименьшее возможное значение.
Ответ: 101.
Типичные ошибки
- Это слово является началом уже заданного кодового слова, поэтому расшифровка станет неоднозначной. Проверяй условие Фано в обе стороны, а не только «снизу вверх».
- Слово допустимое, но не наименьшее по числовому значению: среди слов такой же длины есть меньшее. Найдя длину, перебери все свободные слова этой длины и сравни их как числа.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №4 по информатике