ЕГЭ задания 4_5_12_уровень_С

Для кодирования букв А, Б, В, Г, Д, Е, Ж, З, И, использован неравномерный троичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 0; для буквы Б используется кодовое слово 10; для буквы В используется кодовое слово 11; для буквы Г используется кодовое слово 21; для буквы Д используется кодовое слово 22. Какова минимальная общая длина кодовых слов для букв Е, Ж, З, И?

(a)  

По каналу связи передаются сообщения, содержащие только шесть букв: Т, Е, Н, С, И, В. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: Т – 010, Е – 0100, Н – 1100, С – 01000, И – 0110, В – 1110. Как можно сократить код для буквы Н, чтобы сохранялось свойство однозначности декодирования? Если таких кодов несколько, в качестве ответа указать код наименьшей длины. Примечание. Условие Фано означает, что соблюдается одно из двух условий. Либо никакое кодовое слово не является началом другого кодового слова, либо никакое кодовое слово не является окончанием другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

(a)  

По каналу связи передаются сообщения из букв слова ГОРЕСТЬ. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв С, Е, Т, Ь используются кодовые слова 1, 0110, 01110, 011111, соответственно. Какое количество двоичных знаков потребуется для кодирования слова ГОРСТЬ, если известно, что оно закодировано минимально возможным количеством двоичных знаков? 

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

(a)  

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

1 Вычисляется сумма чётных цифр в десятичной записи числа N. Если чётных цифр в записи нет, сумма считается равной нулю.

2 Вычисляется сумма цифр, стоящих на чётных местах в десятичной записи числа N без ведущих нулей. Места отсчитываются слева направо (от старших разрядов к младшим, начиная с единицы). Если число однозначное (цифр на чётных местах нет), сумма считается равной нулю.

3 Результатом работы алгоритма становится модуль разности полученных двух сумм.

Пример. Дано число N = 2021 Алгоритм работает следующим образом:

1 Чётные цифры в записи: 2, 0, 2, их сумма равна 4

2 Цифры на чётных местах: 0, 1, их сумма равна 1

3 Модуль разности полученных сумм равен 3

Результат работы алгоритма R = 3

При каком наименьшем N в результате работы алгоритма получится R = 13?

(a)  

Автомат обрабатывает натуральное число N по следующему алгоритму:

1. Строится пятеричная запись числа N.

2. К полученной записи дописываются разряды. Если последняя цифра в пятеричной записи четная, справа дописывается 2, если нечетная – слева дописывается 2 и справа 3.

3. Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число N = 13. Алгоритм работает следующим образом:

1. Пятеричная запись числа N: 23.

2. Последняя цифра нечетная, следовательно слева дописываем 2, справа 3: 2+23+3 = 2233. Десятичная запись числа 318.

3. На экран выводится число 318.

В результате работы автомата на экране появилось число, меньшее 1000. Для какого наибольшего значения N данная ситуация возможна?

(a)  

На вход алгоритму Галиб-001 подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1) Строится девятиричная запись числа N.

2) Подсчитывается количество пятёрок и семёрок в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается чаще. Если таких цифр несколько, выбирается наибольшая по значению.

3) Шаг 2 повторяется ещё четыре раза.

4) Результат переводится в шестнадцатиричную систему счисления.

При каком наибольшем исходном числе N < 10000 в результате работы алгоритма получится число, которое содержит в себе сочетание BAC?  

(a)  

Дана программа для исполнителя Редактор:

Известно, что исходная строка A содержала ровно два нуля – на первом и на последнем месте, а также поровну единиц и двоек. После выполнения данной программы получилась строка B, содержащая 47 единиц и меньше 70 двоек. Какое наибольшее количество двоек может быть в строке B?

(a)  

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

заменить (v, w)

нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

Дана программа для Редактора:

На вход приведённой ниже программе поступает строка, содержащая 20 цифр 0 или 1, расположенных в произвольном порядке, и идущем после них символе “<”.

Определите максимальную сумму числовых значений цифр строки, которая может получиться в результате выполнения программы, если известно, что в первоначальной строке не может стоять подряд больше трех одинаковых символа.

(a)  

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

заменить (v, w)

нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

Дана программа для Редактора:

На вход приведённой ниже программе поступает строка, начинающаяся с символа «>», а затем содержащая 20 цифр 0 и 30 цифр 1, расположенных в произвольном порядке. Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.

(a)