Задание 5 в ЕГЭ по информатике на кодирование и декодирование информации. Задание чрезвычайно простое. Даже особых знаний не надо. Условие Фано в в формулировке дано. Я предлагаю решать такие задания 9 классу наряду с похожими заданиями из ОГЭ.
Рассмотрим на примере:
Формулировка задания ёмкая, но в ней есть все для решения задачи.
Давайте разбираться.
Есть 6 букв: К, Л, М, Н, П и Р. Их закодировали, используя двоичный код. Неравномерный код означает, что длины кодовых слов могут быть различны, т.е. состоять из разного количества символов.
Условие Фано описано: никакое кодовое слово не может быть началом другого кодового слова. Ну, например, если мы закодируем какую-нибудь букву только одним 0, то другие буквы мы уже не сможем закодировать словами, начинающимися с 0.
Для четырех букв кодовые слова в задаче даны:
К-000, Л - 001, М - 010, Н - 11.
Нужно указать кратчайшее кодовое слово для буквы П.
Но для буквы Р нам так же кодовое слово не известно. Поэтому это тоже надо учесть.
Начинаем рассуждать. Перебираем возможные кодовые слова, начиная с самых коротких, по возрастанию количества символов в кодовом слове, проверяя при этом выполнение условия Фано.
Кодовые слова 0 и 1 брать мы не можем, так как уже есть кодовые слова, которые начинаются с 0 и 1 (000, 001, 010, 11).
Кодовые слова, состоящие из двух символов:
00 - не подходит, так как является началом кодовых слов 000 и 001.
01 - не подходит, так как является началом кодового слова 010.
10 - это кодовое мы можем использовать для кодирования одной из букв П или Р, так как оно не является началом никакого из кодовых слов.
На этом мы можем остановиться. По задаче нам надо указать кратчайшее возможное кодовое слово для буквы П, про букву Р ничего не сказано, поэтому П мы можем закодировать как 10, а Р кодовым словом подлиннее.
Ответ: 10.
Рассмотрим еще пример:
Надо закодировать 7 букв, несмотря на то, что в сообщении СИДИДОМА используется только 6 букв.
Для трех букв кодовые слова даны:
А- 00, С - 010, И - 10.
Нам остается закодировать наименьшим возможным количеством знаков буквы Д, О, М и П.
Для решения задачи предлагаю построить дерево, из которого сразу найдем решение:
Я отметила те коды, которые уже заняты. Отброшу эти ветви дерева.
Получили только две ветви, а нам надо закодировать четыре буквы, поэтому продолжим каждую ветвь еще на один ярус.
Теперь поясню свой выбор кодовых слов для каждой буквы. Так как в сообщении СИДИДОМА буква Д встречается дважды, то для нее я выбрала код, состоящий из меньшего количества знаков, а так как буква П вообще не встречается в данном сообщении, то для нее я взяла код с наибольшим количеством знаков.
Для букв М и О оставшиеся два кода.
Теперь арифметика. Считаем длину кодового слова каждой буквы, а затем и всего сообщения:
А - 00 = 2, С - 010 = 3, И - 10 = 2,
Д - 111 = 3, О - 110 = 3, М - 0111 = 4.
СИДИДОМА = 3+2+3+2+3+3+4+2 = 22.
Ответ: 22.
Если остались вопросы, пишите в комментариях. Обязательно отвечу. Если нужно разобрать конкретный пример, также - в комментарии.
Читайте также: Задание 1, Задание 2, Задание 3, Задание 4, Задание 6, Задание 7, Задание 8, Задание 9, Задание 10, Задание 11, Задание 12, Задание 13, Задание 14, Задание 15, Задание 18, Задание 19, Задание 22, Задание 16, Задание 17, Задание 20, Задание 21, Задание 23, Задание 24, Задание 25, Задание 26, Задание 27.