Авезинор невезение егэ

По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, З, И, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А  — 101, В  — 010, И  — 00. Какое наименьшее количество двоичных знаков потребуется для кодирования слова НЕВЕЗЕНИЕ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Решение.

Буква Е повторяется в слове НЕВЕЗЕНИЕ чаще всего, поэтому закодируем её кодовым словом 11. Буква Н повторяется в слове НЕВЕЗЕНИЕ 2 раза, поэтому закодируем её кодовым словом 100. Букву З закодировать кодовым словом длины 3 нельзя, поскольку не останется кодовых слов для оставшихся букв, которые удовлетворяли бы условию Фано. Поэтому букву З закодируем кодовым словом 0110. Тогда количество двоичных знаков, которые потребуются для кодирования слова НЕВЕЗЕНИЕ равно 4 · 1 + 2 · 5 + 3 · 3  =  23.

Ответ: 23.

Примечание.

Ответ в данной задаче  — 23. Тем, у кого получается другой ответ, рекомендуем сделать следующее:

1.  Построить дерево возможных кодовых слов (в дальнейшем  — кодов), длина которых не превышает 4.

2.  Отметить на данном дереве заданные коды для букв А, В, И.

3.  Вычеркнуть запрещенные коды, то есть коды, расположенные на ветках дерева, исходящих из отмеченных кодов, а также на ветках, соединяющих отмеченные коды с вершиной дерева.

4.  Последовательно отмечать на дереве выбранный код для очередной буквы и вычеркивать коды, которые оказываются запрещенными после выбора данного кода.

После кодирования всех букв, входящих в слово НЕВЕЗЕНИЕ, в дереве кодов должен остаться хотя бы один свободный (не отмеченный и не запрещенный) код. Он необходим, чтобы на его основе построить коды для букв О и Р, которые хотя и не входят в слово НЕВЕЗЕНИЕ, но тоже могут передаваться по каналу связи и, следовательно, должны иметь свои коды. Если такого свободного кода не осталось, то решение является неверным, и необходимо выбрать другой код для последней кодируемой буквы.

Покажем, как могло бы выглядеть решение в этом случае.

Строим дерево кодовых слов, отмечаем коды заданных букв (выделено красным) и вычеркиваем запрещенные коды (выделено серым).

Выбираем для буквы, чаще всего встречающейся в слове (это буква Е, встречается 4 раза) свободный код с наименьшей длиной, отмечаем его (выделено синим) и вычеркиваем запрещенные коды (выделено серым).

Выбираем для следующей буквы, чаще встречающейся в заданном слове (это буква Н, встречается 2 раза) свободный код с наименьшей длиной (выделено синим) и вычеркиваем запрещенные коды (выделено серым).

Пытаемся выбрать код для следующей буквы (это буква З), отмечаем его и вычеркиваем запрещенные коды. В получившемся дереве не осталось ни одного свободного кода, следовательно, наш выбор неправильный.

Тогда для буквы З придется использовать код большей длины.

Если сосчитать суммарную длины кодовых слов все букв, входящих в слово НЕВЕЗЕНИЕ, то получим 23.

Канал видеоролика: Info Ege Tactics

Смотреть видео:

Свежая информация для ЕГЭ и ОГЭ по Информатике (листай):

С этим видео ученики смотрят следующие ролики:

Облегчи жизнь другим ученикам — поделись! (плюс тебе в карму):

28.06.2019

Рекомендации по самостоятельной подготовке к ЕГЭ 2022 по русскому языку от ФИПИ

Задание №1 ЕГЭ по русскому языку — тренировочные материалы от ФИПИ

Пробные варианты ЕГЭ 2022 по русскому языку

Задание 16 ЕГЭ 2022 по русскому языку — тренировочные задания

Задание 10 ЕГЭ по русскому языку — теория и практика