Государственное бюджетное
общеобразовательное учреждение
средняя общеобразовательная школа №556
с углублённым изучением английского языка
Курортного района Санкт-Петербурга
4-6. Элементы теории алгоритмов
и языки программирования
ЕГЭ-6-r. Формальное исполнение алгоритма, записанного на естественном языке. Б-4. ЕГЭ-6-w. Умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд. Б-4. ЕГЭ-8. a href=doc/ege/8.pdf>Знание основных конструкций языка программирования, понятия переменной, оператора присваивания.
Анализ алгоритмов с циклами. Б-3.
ЕГЭ-11. Умение исполнить рекурсивный алгоритм. Б-5.
ЕГЭ-14. Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд. П-6.
ЕГЭ-19. Работа с массивами. П-5. ЕГЭ-20. Умение анализировать алгоритмы с циклами и ветвлениями. П-5.
ЕГЭ-21. Умение анализировать программы с процедурами и функциями. П-6.
ЕГЭ-22. Умение анализировать результат исполнения алгоритма. Перебор вариантов. Динамическое программирование. П-7.
В2. Переменные. Операции над переменными. ВВ2. Вa href=doc/ege/bb2.doc> Выполнение алгоритма по блок-схеме.
ЕГЭ-24 (C1). Умение прочесть фрагмент программы на языке программирования и исправить допущенные ошибки. П-30.
ЕГЭ-25 (C2). Умение написать короткую (10–15 строк) простую программу на языке программирования или
записать алгоритм на естественном языке. В-30.
ЕГЭ-27 (C4). Умение создавать собственные программы (30–50 строк) для решения задач средней сложности. В-55.
Задание 1. Сколько существует натуральных чисел x, для которых выполнено неравенство 110111002 < x < DF16?
В ответе укажите только количество чисел, сами числа писать не нужно.
ЕГЭ - 2016: 1. Сколько единиц в двоичной записи шестнадцатеричного числа 12F016?
Задание 4. Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей.
Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID племянницы
Иваненко М.И. В ответе запишите только цифры ID.
Задание 5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать
неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10.
Какова наименьшая возможная сумма длин всех шести кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной
расшифровки закодированных сообщений.
Задание 9. Для хранения произвольного растрового изображения размером 1024×1024 пикселей отведено 512 Кбайт памяти, при этом для
каждого пикселя хранится двоичное число – код цвета этого пикселя. Для каждого пикселя для хранения кода выделено одинаковое
количество бит. Сжатие данных не производится. Какое максимальное количество цветов можно использовать в изображении?
Задание 10. Вася составляет 5-буквенные слова, в которых встречаются только буквы А, Б, В, Г, причём буква А
появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз
или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно
осмысленная. Сколько существует таких слов, которые может написать Вася?
ЕГЭ-2016.Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве
кодовых слов Игорь использует 5-буквенные слова, в которых есть только буквы П, И, Р, причём буква П появляется ровно 1 раз. Каждая из других
допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может
использовать Игорь?
Задание 12. В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети
относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-
адрес, – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала
(в старших разрядах) стоят единицы, а затем с некоторого разряда – нули. Адрес сети получается в результате применения
поразрядной конъюнкции к заданным IP-адресу узла и маске. Например, если IP-адрес узла равен 231.32.255.131, а маска равна
255.255.240.0, то адрес сети равен 231.32.240.0. Для узла с IP-адресом 119.83.208.27 адрес сети равен 119.83.192.0.
Каково наименьшее возможное количество единиц в разрядах маски?
Задание 17. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для
обозначения логической операции «И» – символ «&».
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц (в сотнях тысяч)
Бабочка
22
Гусеница
40
Трактор
28
Трактор & Гусеница
16
Трактор & Бабочка
0
Какое количество страниц (в сотнях тысяч) будет найдено по запросу Трактор | Бабочка | Гусеница? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова,
не изменялся за время выполнения запросов.
Задание 20.Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное число x, этот алгоритм печатает число R.
Укажите такое число x, при вводе которого алгоритм печатает двузначное число, сумма цифр которого равна 16.
Если таких чисел x несколько, укажите наименьшее из них.
Var x,d,R: longint;
Begin
readln(x); R := 0;
while x>0 do
begin
d := x mod 10; R := 10*R + d; x := x div 10
end;
writeln(R)
end.
ЕГЭ-2016. Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т.е. большее 100) число x, при вводе которого алгоритм печатает 26.
Часть 2. 1. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных,
не зависит от числа N и не превышает 1 килобайта.
2. Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.
3. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.
4. Максимальная оценка за правильную программу,неэффективную ни по времени, ни по памяти, – 2 балла.
5. Перед программой укажите версию языка и кратко опишите использованный алгоритм.