выбор кода при неиспользуемых сигналах
Выбор кода при неиспользуемых сигналах
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Следующая буква должна кодироваться как 11, поскольку 10 мы взять не можем. 100 взять не можем из-за Г, значит, следующая буква должна быть закодирована кодом 101. Следующая буква должна кодироваться как 000, поскольку 00 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 001. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно 2 + 3 + 3 + 3 + 3 = 14.
Заметим, что после кодирования всех букв, входящих в слово МАГИЯ, должен остаться хотя бы один свободный код для кодирования буквы Р, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
При такой кодировке невозможно подобрать кодовое слово для буквы «Р», удовлетворяющее условию Фано.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Следующая буква должна кодироваться как 011, поскольку 01 мы взять не можем, иначе код для буквы А не будет удовлетворять условию Фано. 10 из-за Г взять не можем, тогда следующая буква будет кодироваться как 100. Следующая буква должна кодироваться как 110, поскольку 11 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 111. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно
Заметим, что после кодирования всех букв, входящих в слово МАГИЯ, должен остаться хотя бы один свободный код для кодирования буквы Р, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, И — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Для трёх букв кодовые слова уже известны, осталось подобрать для оставшихся четырёх букв такие кодовые слова, которые обеспечат наименьшее количество двоичных знаков для кодирования слова ГРАММ.
Закодируем букву М кодовым словом 00, поскольку буква М повторяется в слове ГРАММ два раза. Для буквы Г возьмём кодовое слово 110. Кодовое слово 111 взять не можем, поскольку для остальных букв не останется кодовых слов, удовлетворяющих условию Фано. Оставшиеся две буквы закодируем кодовыми словами длины 4.
Таким образом, наименьшее количество двоичных знаков, которые потребуются для кодирования слова ГРАММ, равно 3 + 4 + 3 + 2 + 2 = 14.
Заметим, что после кодирования всех букв, входящих в слово ГРАММ, должен остаться хотя бы один свободный код для кодирования буквы Я, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
Выбор кода при неиспользуемых сигналах
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Следующая буква должна кодироваться как 11, поскольку 10 мы взять не можем. 100 взять не можем из-за Г, значит, следующая буква должна быть закодирована кодом 101. Следующая буква должна кодироваться как 000, поскольку 00 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 001. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно 2 + 3 + 3 + 3 + 3 = 14.
Заметим, что после кодирования всех букв, входящих в слово МАГИЯ, должен остаться хотя бы один свободный код для кодирования буквы Р, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
При такой кодировке невозможно подобрать кодовое слово для буквы «Р», удовлетворяющее условию Фано.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Следующая буква должна кодироваться как 011, поскольку 01 мы взять не можем, иначе код для буквы А не будет удовлетворять условию Фано. 10 из-за Г взять не можем, тогда следующая буква будет кодироваться как 100. Следующая буква должна кодироваться как 110, поскольку 11 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 111. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно
Заметим, что после кодирования всех букв, входящих в слово МАГИЯ, должен остаться хотя бы один свободный код для кодирования буквы Р, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, И — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Для трёх букв кодовые слова уже известны, осталось подобрать для оставшихся четырёх букв такие кодовые слова, которые обеспечат наименьшее количество двоичных знаков для кодирования слова ГРАММ.
Закодируем букву М кодовым словом 00, поскольку буква М повторяется в слове ГРАММ два раза. Для буквы Г возьмём кодовое слово 110. Кодовое слово 111 взять не можем, поскольку для остальных букв не останется кодовых слов, удовлетворяющих условию Фано. Оставшиеся две буквы закодируем кодовыми словами длины 4.
Таким образом, наименьшее количество двоичных знаков, которые потребуются для кодирования слова ГРАММ, равно 3 + 4 + 3 + 2 + 2 = 14.
Заметим, что после кодирования всех букв, входящих в слово ГРАММ, должен остаться хотя бы один свободный код для кодирования буквы Я, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
5 задание ЕГЭ информатика на анализ алгоритмов
Объяснение 5 задания
5-е задание: «Анализ алгоритмов и исполнители»
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 4 минуты.
Проверяемые элементы содержания: Формальное исполнение алгоритма, записанного на естественном языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд
«Как и в других заданиях базового уровня сложности, источником ошибок служит недостаточная внимательность и отсутствие или поверхностность самостоятельной проверки полученного ответа»
Исполнитель для возведения в квадрат, деления, умножения и сложения
Проверка числовой последовательности на соответствие алгоритму
Теперь будем рассматривать конкретные типовые экзаменационные варианты по информатике с объяснением их решения.
Разбор 5 задания
Задание демонстрационного варианта 2022 года ФИПИ
Плейлист видеоразборов задания на YouTube: 
Решение задания про алгоритм, который строит число R
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше 129. В ответе это число запишите в десятичной системе счисления.
✍ Решение:
Результат: 8
Для более детального разбора предлагаем посмотреть видео решения данного 5 задания ЕГЭ по информатике:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
✍ Решение:
Результат: 86
Подробное решение данного 5 (раньше №6) задания из демоверсии ЕГЭ 2018 года смотрите на видео:
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа еще два разряда по следующему правилу:
— если N делится нацело на 4, в конец числа (справа) дописывается сначала ноль, а затем еще один ноль;
— если N при делении на 4 дает в остатке 1, то в конец числа (справа) дописывается сначала ноль, а затем единица;
— если N при делении на 4 дает в остатке 2, то в конец числа (справа) дописывается сначала один, а затем ноль;
— если N при делении на 4 дает в остатке 3, в конец числа (справа) дописывается сначала один, а затем еще одна единица.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R — результата работы данного алгоритма.
Укажите максимальное число R, которое меньше 100 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
✍ Решение:
Результат: 96
Предлагаем посмотреть видео решения:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. К этой записи дописывается (дублируется) последняя цифра.
3. Затем справа дописывается бит чётности: 0, если в двоичном коде полученного числа чётное число единиц, и 1, если нечётное.
4. К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, большее 114, которое может быть получено в результате работы этого алгоритма. В ответе это число запишите в десятичной системе.
✍ Решение:
2. В полученное числе N = 1110 дублируется последняя цифра и получается 11100.
3. Поскольку число единиц (3) — нечетное, то справа добавляется 1: 111001.
4. Т.к. в полученном наборе цифр четное число единиц, то добавляем 0: 1110010
Результат: 126
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа – результата работы данного алгоритма.
Укажите минимальное число N, для которого результат работы алгоритма будет больше 134. В ответе это число запишите в десятичной системе счисления.
Ответ: 33
Автомат обрабатывает целое число N (0 ≤ N ≤ 255) по следующему алгоритму:
1. Строится восьмибитная двоичная запись числа N.
2. Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).
3. Полученное число переводится в десятичную запись.
4. Из нового числа вычитается исходное, полученная разность выводится на экран.
Какое число нужно ввести в автомат, чтобы в результате получилось 45?
Ответ: 105
Смотрите разбор задания на видео и подписывайтесь на наш канал:
Решение заданий для темы Проверка числовой последовательности (Автомат)
Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 114.
Укажите наименьшее число, в результате обработки которого, автомат выдаст число 1311.
✍ Решение:
Результат: 2949
Процесс решения данного 5 задания представлен в видеоуроке:
Автомат получает на вход четырехзначное число. По нему строится новое число по следующим правилам:
Пример: Исходное число: 7531. Суммы: 7+5=12; 5+3=8; 3+1=4. Результат: 4812.
Укажите наибольшее число в результате обработки которого автомат выдаст 2512.
✍ Решение:
Подробное решение данного 5 задания можно просмотреть на видео:
Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам:
Пример: Исходные числа: 25, 66. Поразрядные суммы: 8, B. Результат: B8.
Какие из предложенных чисел могут быть результатом работы автомата?
Перечислите в алфавитном порядке буквы, соответствующие этим числам, без пробелов и знаков препинания.
Варианты:
A) 127
B) C6
C) BA
D) E3
E) D1
✍ Решение:
Подробное решение данного 5 задания можно просмотреть на видео:
Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 7 (если в числе есть цифра больше 7, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.
1. Вычисляются два шестнадцатеричных числа: сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.
2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходные числа: 66, 43. Поразрядные суммы: A, 9. Результат: 9A.
Определите, какое из предложенных чисел может быть результатом работы автомата.
Варианты:
1) AD
2) 64
3) CF
4) 811
✍ Решение:
Результат: 1
Решение 4 задания ГВЭ 11 класса смотрите на видео:
Автомат получает на вход натуральное число X. По этому числу строится трёхзначное число Y по следующим правилам:
1. Первая цифра числа Y (разряд сотен) – остаток от деления X на 7.
2. Вторая цифра числа Y (разряд десятков) – остаток от деления X на 2.
3. Третья цифра числа Y (разряд единиц) – остаток от деления X на 5.
Сколько существует двузначных чисел, при обработке которого автомат выдаёт результат 312?
✍ Решение:
Выбор кода при неиспользуемых сигналах
По каналу связи передаются сообщения, содержащие только 4 буквы: П, А, Р, К. Для кодирования букв П, А, Р используются 6-битовые кодовые слова:
П — 111111, А — 110001, Р — 001001.
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее, чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Нужно подобрать кодовое слово для буквы К так, чтобы указанное свойство выполнялось для всех четырёх кодовых слов.
Можно ли использовать одно из таких слов: 000001, 111001, 000111?
4) нет, не подходит ни одно из указанных выше слов
Проанализируем каждый вариант кодового слова. Первое слово: 000001 отличается от буквы А только в двух позициях. Второе слово: 111001 отличается от буквы А только в одной позиции. Третье слово: 000111 отличается от любой буквы П, А или Р не менее чем в трёх позициях. Таким образом, в качестве кодового слова для буквы К можно использовать слово 000111.
Правильный ответ указан под номером 3.
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А — 0; Б — 110; В — 101.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения:
1 — нельзя, буквы Б, В начинаются с 1.
000 — нельзя из-за А.
001 — нельзя из-за А.
100 — можно использовать.
101 — нельзя из-за В.
110 — нельзя из-за Б.
111 — можно использовать.
Таким образом, поскольку, если кратчайших кодов несколько, необходимо указать код с наибольшим числовым значением, кратчайшее кодовое слово для буквы Г — 111.
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Б, В, Г используются такие кодовые слова: Б — 101; В — 110; Г — 0.
Укажите кратчайшее кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Для трёх букв кодовые слова уже известны, осталось подобрать для оставшейся буквы такое кодовое слово, которое будет являться кратчайшим и удовлетворять условию Фано.
Кодовым словом не могут быть ни 0, ни 1, потому что есть кодовые слова, начинающиеся с 0 и 1. Для оставшейся буквы можно использовать кодовые слова 100 и 111. Кратчайшее слово с наибольшим числовым значением — 111.
По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: В — 1110, Г — 110, Д — 0000, Е — 01. Известно, что для кодирования слова БАОБАБ потребовалось 16 двоичных знаков. Какое кодовое слово соответствует букве А?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Кодовыми словами для буквы А не могут быть 0 или 1, поскольку будет нарушаться условие Фано. Поскольку буква Б встречается в слове БАОБАБ 3 раза, возьмём кодовое слово для буквы Б равным 10. Буква А встречается в слове БАОБАБ 2 раза, значит, кодовым словом для буквы А будет 001. Букву О закодируем кодовым словом 0001. Тогда для кодирования слова БАОБАБ потребуется 16 двоичных знаков. Значит, ответ — 001.
Выбор кода при неиспользуемых сигналах
По каналу связи передаются сообщения, содержащие только восемь букв: К, Л, М, Н, О, П, Р, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К — 001, Н — 100, Р — 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МОЛОКОСОС?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Буква О повторяется в слове МОЛОКОСОС чаще всего, поэтому закодируем её кодовым словом 01. Буква С повторяется в слове МОЛОКОСОС 2 раза, поэтому закодируем её кодовым словом 000. Букву М закодируем кодовым словом 101. Букву Л закодировать кодовым словом длины 3 нельзя, поскольку не останется кодовых слов для оставшихся букв, которые удовлетворяли бы условию Фано. Поэтому букву Л закодируем кодовым словом 1100. Тогда количество двоичных знаков, которые потребуются для кодирования слова МОЛОКОСОС равно 4 · 1 + 2 · 4 + 3 · 4 = 24.
Заметим, что после кодирования всех букв, входящих в слово МОЛОКОСОС, должен остаться хотя бы один свободный код для кодирования буквы П, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 000, Б — 01, В — 1101, Г — 111, Д — 0010, Е — 100. Для кодирования слова ГОРОД потребовалось 17 двоичных знаков. Какое кодовое слово соответствует букве О?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Кодовые слова для букв Г и Д уже известны, для кодирования этих двух букв потребуется 7 двоичных знаков. Поскольку буква О повторяется в слове ГОРОД два раза, закодируем её кодовым словом 101. Букву Р закодируем кодовым словом длины 4. Всего для кодирования слова ГОРОД в таком случае потребуется 17 двоичных знаков. Таким образом, ответ — 101.
По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 101, В — 1001, Г — 111, Д — 0110, Е — 110. Для кодирования слова ОГОРОД потребовалось 17 двоичных знаков. Какое кодовое слово соответствует букве О?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Кодовые слова для букв Г и Д уже известны, для кодирования этих двух букв потребуется 7 двоичных знаков. Поскольку буква О повторяется в слове ОГОРОД три раза, закодируем её кодовым словом 00. Букву Р закодируем кодовым словом длины 4. Всего для кодирования слова ОГОРОД в таком случае потребуется 17 двоичных знаков. Таким образом, ответ — 00.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, О, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 01, Д — 001, Р — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВОДОВОРОТ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Букву О закодируем кодовым словом 11, поскольку буква О повторяется в слове ВОДОВОРОТ 4 раза. Букву В закодируем кодовым словом 101, поскольку буква В повторяется в слове ВОДОВОРОТ 2 раза. Букву Т нельзя закодировать словом 000, так как в этом случае невозможно будет закодировать букву А, поэтому букву Т закодируем словом 0000. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова ВОДОВОРОТ равно 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 4 = 24.
Заметим, что после кодирования всех букв, входящих в слово ВОДОВОРОТ, должен остаться хотя бы один свободный код для кодирования буквы А, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 000, Б — 01, В — 1101, Г — 111, Д — 0010, Е — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОКОС?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Буква К повторяется в слове КОКОС 2 раза. Закодируем её кодовым словом 101. Буква О повторяется в слове КОКОС 2 раза. Закодируем её кодовым словом 1100. Букву С закодировать кодовым словом длины 4 нельзя, поскольку не останется кодовых слов для других букв. Значит, букву С закодируем кодовым словом 00110. Тогда ответ — 3 · 2 + 4 · 2 + 5 = 19.
Заметим, что при кодировании буквы К последовательностью 101 и буквы О последовательностью 1100 букву С нельзя закодировать кодовым словом 0011, поскольку при этом не останется ни одной четырехсимвольной последовательности, с которой могли бы начинаться коды для других букв, передаваемых по каналу связи (по условию задачи могут передаваться все заглавные русские буквы).
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Следующая буква должна кодироваться как 11, поскольку 10 мы взять не можем. 100 взять не можем из-за Г, значит, следующая буква должна быть закодирована кодом 101. Следующая буква должна кодироваться как 000, поскольку 00 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 001. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно 2 + 3 + 3 + 3 + 3 = 14.
Заметим, что после кодирования всех букв, входящих в слово МАГИЯ, должен остаться хотя бы один свободный код для кодирования буквы Р, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
При такой кодировке невозможно подобрать кодовое слово для буквы «Р», удовлетворяющее условию Фано.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Следующая буква должна кодироваться как 011, поскольку 01 мы взять не можем, иначе код для буквы А не будет удовлетворять условию Фано. 10 из-за Г взять не можем, тогда следующая буква будет кодироваться как 100. Следующая буква должна кодироваться как 110, поскольку 11 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 111. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно
Заметим, что после кодирования всех букв, входящих в слово МАГИЯ, должен остаться хотя бы один свободный код для кодирования буквы Р, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
Белый — 0, Зелёный — 11111, Фиолетовый — 11110, Красный — 1110, Чёрный — 10. Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет допускать однозначное декодирование.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Заметим, что кодовые слова, начинающиеся с 0, мы взять не можем, поскольку Белый уже закодирован кодовым словом 0. Кодовое слово 10 занято Чёрным. Кодовые слова, состоящие только из единиц, составить нельзя, иначе однозначное декодирование будет негарантированно. Значит, можем взять кодовое слово 110.
По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: В — 1110, Г — 110, Д — 0000, Е — 01. Известно, что для кодирования слова БАОБАБ потребовалось 16 двоичных знаков. Какое кодовое слово соответствует букве А?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Кодовыми словами для буквы А не могут быть 0 или 1, поскольку будет нарушаться условие Фано. Поскольку буква Б встречается в слове БАОБАБ 3 раза, возьмём кодовое слово для буквы Б равным 10. Буква А встречается в слове БАОБАБ 2 раза, значит, кодовым словом для буквы А будет 001. Букву О закодируем кодовым словом 0001. Тогда для кодирования слова БАОБАБ потребуется 16 двоичных знаков. Значит, ответ — 001.
По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 10, Г — 1110, Д — 0111, Е — 010. Известно, что для кодирования слова АНАНАС потребовалось 16 двоичных знаков. Какое кодовое слово соответствует букве Н?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Кодовыми словами для буквы Н не могут быть 0 или 1, поскольку будет нарушаться условие Фано. Поскольку буква А встречается в слове АНАНАС 3 раза, возьмём кодовое слово для буквы А равным 00. Буква Н встречается в слове АНАНАС 2 раза, значит, кодовым словом для буквы Н будет 110. Букву С закодируем кодовым словом 0110. Тогда для кодирования слова АНАНАС потребуется 16 двоичных знаков. Значит, ответ — 110.
По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Буква С не может кодироваться строкой, которая начинается с 0, поскольку О имеет код 0.
Буква С не может кодироваться как 1, так как кодирование буквы Т начинается с 1.
Буква С не может кодироваться как 10, так как кодирование буквы П начинается с 10.
Буква С не может кодироваться как 11, так как кодирование буквы Т начинается с 11.
Буква С может кодироваться как 101 − это наименьшее возможное значение.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Однозначные коды не подходят по условию Фано. Кратчайшее подходящее кодовое слово — 01. Но выбирая его, не останется вариантов закодировать букву E, значит, нужно взять минимум трехзначный код. Минимальный из них, подходящий по условию Фано — 010. Тогда букву Е можно закодировать как 011.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, И — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Для трёх букв кодовые слова уже известны, осталось подобрать для оставшихся четырёх букв такие кодовые слова, которые обеспечат наименьшее количество двоичных знаков для кодирования слова ГРАММ.
Закодируем букву М кодовым словом 00, поскольку буква М повторяется в слове ГРАММ два раза. Для буквы Г возьмём кодовое слово 110. Кодовое слово 111 взять не можем, поскольку для остальных букв не останется кодовых слов, удовлетворяющих условию Фано. Оставшиеся две буквы закодируем кодовыми словами длины 4.
Таким образом, наименьшее количество двоичных знаков, которые потребуются для кодирования слова ГРАММ, равно 3 + 4 + 3 + 2 + 2 = 14.
Заметим, что после кодирования всех букв, входящих в слово ГРАММ, должен остаться хотя бы один свободный код для кодирования буквы Я, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Для трёх букв кодовые слова уже известны, осталось подобрать для оставшихся четырёх букв такие кодовые слова, которые обеспечат наименьшее количество двоичных знаков для кодирования слова ГРАММ.
Закодируем букву М кодовым словом 11, поскольку буква М повторяется в слове ГРАММ два раза. Для буквы Р возьмём кодовое слово 011. Для оставшихся букв можно будет использовать кодовые слова, начинающиеся с 100.
Таким образом, наименьшее количество двоичных знаков, которые потребуются для кодирования слова ГРАММ, равно 3 + 3 + 3 + 2 + 2 = 13
Для передачи сообщений, составленных из заглавных букв русского алфавита, используется неравномерный двоичный код, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова, назначенные для некоторых букв: А — 000, Б — 0010, В — 101, Г — 11. Какое наименьшее количество двоичных знаков может содержать сообщение, кодирующее слово КОЛОБОК?
Буква О повторяется в слове КОЛОБОК три раза, поэтому закодируем её кодовым словом 01. Буква К повторяется в слове КОЛОБОК два раза, поэтому закодируем её кодовым словом 100. Букву Л закодировать кодовым словом длины 4 нельзя, поскольку не останется кодовых слов для остальных букв, поэтому закодируем букву Л кодовым словом 00110. Таким образом, сообщение, кодирующее слово КОЛОБОК будет содержать 2 · 3 + 3 · 2 + 5 + 4 = 21 двоичный знак.
Заметим, что после кодирования всех букв, входящих в слово КОЛОБОК, должен остаться хотя бы один свободный код для построения кодов остальных букв русского алфавита, которые не входит в данное слово, но могут передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.
Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слову КАША соответствует код 011011010. Какое наименьшее количество двоичных знаков может содержать сообщение, кодирующее слово ОСОКА?
Заметим, что буква А повторяется в слове КАША 2 раза. Буква А стоит на конце слова, кодовое слово 0 для кодирования буквы А использоваться не может, поскольку будет нарушено условие Фано, кодовое слово 010 использоваться не может, поскольку второго такого кодового слова в коде 011011010 не найдётся, значит, буква А кодируется словом 10. Тогда буква Ш соответствует кодовому слову 110, а буква К соответствует кодовому слову 01.
Буква О повторяется в слове ОСОКА 2 раза, закодируем её кодовым словом 00. Букву С кодовым словом длины 3 закодировать нельзя, поскольку не останется кодовых слов для других букв, тогда закодируем её кодовым словом 1110. Тогда количество двоичных знаком в сообщении, кодирующем слово ОСОКА, равно 2 · 4 + 4 = 12.
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
| Цвет | Кодовое слово |
|---|---|
| Белый | 0 |
| Зелёный | 11111 |
| Красный | 1110 |
| Цвет | Кодовое слово |
|---|---|
| Синий | |
| Фиолетовый | 11110 |
| Чёрный | 10 |
Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Подберём кодовое слово для синего цвета. Слово 0 занято. Слово 1 является началом других кодов. Слово 10 занято. Слово 11 является началом других кодов. Слова 100 и 101 использовать нельзя, так как их начало совпадает с кодом черного цвета. Можно использовать только кодовое слово 110.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 110, Б — 01, И — 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВВЕДЕНИЕ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Букву Е закодируем кодовым словом 10, поскольку буква Е повторяется в слове ВВЕДЕНИЕ 3 раза. Букву В закодируем кодовым словом 111, поскольку буква В повторяется в слове ВВЕДЕНИЕ 2 раза. Буквы Д и Н закодируем кодовыми словами 0010 и 0011 соответственно. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова ВВЕДЕНИЕ, равно 3 + 3 + 2 + 4 + 2 + 4 + 3 + 2 = 23.
По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 101, В — 1001, Г — 111, Д — 0110, Е — 110. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ЛИЛИЯ?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Буква Л повторяется в слове ЛИЛИЯ 2 раза. Закодируем её кодовым словом 000. Буква И повторяется в слове ЛИЛИЯ 2 раза. Закодируем её кодовым словом 001. Букву Я закодировать кодовым словом длины 3 нельзя, поскольку будет нарушено условие Фано. Значит, букву Я закодируем кодовым словом 0111. Тогда ответ — 3 · 4 + 4 = 16. Заметим, что остальные буквы можно будет закодировать кодами длины не менее 5, начинающимися с 1000.
Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слову УДОД соответствует код 100011101. Какое наименьшее количество двоичных знаков может содержать сообщение, кодирующее слово УДАЧА?
Заметим, что буква Д повторяется в слове УДОД 2 раза. Буква Д стоит на конце слова, кодовое слово 1 для кодирования буквы Д использоваться не может, поскольку будет нарушено условие Фано, кодовое слово 101 использоваться не может, поскольку второго такого кодового слова в коде 100011101 не найдётся, значит, буква Д кодируется словом 01. Тогда буква О соответствует кодовому слову 11, а буква У соответствует кодовому слову 100.
Буква А повторяется в слове УДАЧА 2 раза, закодируем её кодовым словом 00. Букву Ч кодовым словом длины 3 закодировать нельзя, поскольку не останется кодовых слов для других букв, тогда закодируем её кодовым словом 1010. Тогда количество двоичных знаком в сообщении, кодирующем слово УДАЧА, равно 2 · 3 + 3 + 4 = 13.