По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 1, 00, 0100, 0111 соответственно.
Укажите минимальную сумму длин кодовых слов для букв Д и Е, при которых код будет удовлетворять условию Фано.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа – результата работы данного алгоритма.
Укажите максимальное число N, для которого результат работы алгоритма будет меньше 131. В ответе это число запишите в десятичной системе счисления.
В таблице содержатся сведения о дорогах между населёнными пунктами (звёздочка означает, что дорога между соответствующими городами есть). На рисунке справа та же схема дорог изображена в виде графа.
Номер пункта
1
2
3
4
5
6
7
8
Номер пункта
1
*
*
*
2
*
*
3
*
*
4
*
*
5
*
*
*
6
*
*
7
*
*
*
8
*
*
*
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера населённых пунктов Е и В в таблице. В ответе напишите два числа без разделителей: сначала для пункта Е, затем для пункта В.
Исполнитель Редактор получает на вход строку символов и преобразовывает её.
Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
На вход приведённой ниже программы поступает строка, начинающаяся с символа «>», а затем содержащая 26 цифр 1, 10 цифр 2 и 14 цифр 3, расположенных в произвольном порядке.
Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.
Так, например, если результат работы программы представлял бы собой строку, состоящую из 50 цифр 4, то верным ответом было бы число 200.
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)
Исполнитель Вычислитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1.Прибавить 1
2.Прибавить 2
3.Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2.
Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые исходное число 4 преобразуют в число 15, и при этом траектория вычислений программы содержит число 11?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
На рисунке слева изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Номер пункта
1
2
3
4
5
6
7
Номер пункта
1
*
*
2
*
*
*
*
3
*
*
4
*
*
*
5
*
*
*
6
*
*
*
7
*
*
*
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам E и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Исполнитель Редактор получает на вход строку символов и преобразовывает её.
Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
На вход приведённой ниже программы поступает строка из 150 цифр, содержащая по 50 цифр 1, 2 и 3, расположенных в произвольном порядке.
Определите, какие цифры будут находиться на 10-м, 80-м и 140-м местах строки, получившейся в результате выполнения программы. Цифры в строке нумеруются последовательно слева направо, самая левая имеет номер 1, следующая – номер 2 и т.д.
В ответе запишите три полученные цифры подряд без пробелов и разделителей в порядке возрастания номеров их мест в получившейся строке. Так, например, если бы на 10-м месте стояла цифра 9, на 80-м – 4, а на 140-м – 8, то был бы ответ 948.
НАЧАЛО
ПОКА нашлось (21) ИЛИ нашлось (31) ИЛИ нашлось (32)
Миша заполнял таблицу истинности функции (x /\ y)\/ (y≡ z) \/ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
(x/\y)\/(y≡ z)\/w
1
0
0
0
0
1
0
0
1
1
0
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
¬x \/y
0
1
0
В этом случае первому столбцу соответствует переменная y, а второму столбцу –– переменная x. В ответе следует написать yx.
Миша заполнял таблицу истинности функции (x \/ y)/\ ¬(y ≡ z) /\ ¬w, но успел заполнить лишь фрагменты из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
(x\/y)/\¬(y ≡ z)/\¬w
1
1
0
0
1
0
1
1
1
0
1
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
¬x \/y
0
1
0
В этом случае первому столбцу соответствует переменная y, а второму столбцу –– переменная x. В ответе следует написать yx.
