Задача ЕГЭ по Информатике
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Г, Й, К, Л. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 00, Г — 010, К — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАЛАЛАЙКА?
Разве это правильный ответ?
-
-
пояснение.
Букву А закодируем кодовым словом 11, поскольку буква А повторяется в слове БАЛАЛАЙКА 4 раза. Букву Л закодируем кодовым словом 011, поскольку буква Л повторяется в слове БАЛАЛАЙКА 2 раза. Буквы Й и В закодируем кодовыми словами 1000 и 1001 соответственно. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова БАЛАЛАЙКА равно 2 + 2 + 3 + 2 + 3 + 2 + 4 + 3 + 2 = 23.
Как мне кажется ответ 22. т. к буквы можно закодировать как 10, 110, 111 получается БАЛАЛАЙКА равно 2+2+2+2+2+3+3+3+3 = 22 .
"т. к буквы можно закодировать как 10, 110, 111"
Какие буквы?
ты рисовал дерево по этой задаче?
10 использовать нельзя. Почитайте, что означает "условие Фано".
Б-00,- это по условию.
Т. е. из 2-значных можно использовать 11 только (т. к. уже заданы 010 "Г"- значит 01 нельзя и 101 "К" - значит 10 нельзя).
Итого 2-значные используем 00-Б и 11-А, на основе двух оставшихся двузначных (01 и 10) можно 4 трехзначных придумать (010 (занято "Г") , 101 (занято "К"), 011 и 100). Т. е. можно присвоить 011 и 100, но у нас без кода три буквы - Л, Й и В. Значит все равно придется вместо одного трехзначного (011 или 100 - не важно) использовать 2 четырехзначных. А там уж не важно, 011 присвоить Л, а 100 разбить на 1000 и 1001 для Й и В, или 100 присвоить Л, а 011 разбить на 0110 и 0111 для Й и В. Ответ на задачу от этого не изменится - 23.
Учитес сами.