Сколько единиц в двоичной записи числа 77716

ЕГЭ по информатике 2022 — Задание 5 (Линейный алгоритм)

Привет! В этой статье будут различные примеры решения задач из 5-ого задания ЕГЭ по информатике 2022.

Задание 5 решается не сложно, но, как всегда, нужно потренироваться решать подобные задачи, чтобы уверенно себя чувствовать на ЕГЭ по информатике 2022.

Рассмотрим классический пример.

Задача (Классическая)

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R по следующему принципу.

1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) Складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописываются в конец числа (справа). Например, запись 11100 преобразуется в запись 111001.
б) Над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите минимальное число R, которое превышает 42 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.

Решение на Python.

for n in range(1, 1000): s=format(n, 'b') s=s+str(s.count('1')%2) s=s+str(s.count('1')%2) r=int(s, 2) if r>42: print(r)

Программа будет выводить различные числа, но нас интересует самое маленькое. В ответе получается 46. Чтобы остановить поток чисел, можно нажать сочетание Ctrl + C.

В программе перебираем натуральные числа от 1 до 1000 с помощью цикла for. Каждое число подставляем в описанный алгоритм, в надежде получить в результате число r, удовлетворяющие условию задачи.

С помощью функции format переводим число n в двоичный вид. Получаем результат в виде строки s.

Чтобы найти сумму цифр получившейся двоичной записи, достаточно подсчитать количество единиц в строке s. Ведь только единицы в двоичной записи дают в сумму результат. Это можно сделать, применив функцию .count() к строке s.

Добавляем справа к строке s остаток от деления суммы цифр на 2. Остаток нужно превратить в строковый тип данных, чтобы «присоединить» к строке s справа.

Повторяем пункт Б, скопировав строку с пунктом А.

Чтобы обратно превратить строку двоичной записи в десятичное число, используем функцию int(), указав параметр 2.

В конце программы пропишем условие. Если r больше 42, то будем печатать эти значения. Остаётся выбрать минимальное число r.

Решение с помощью рассуждений.

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

Это число преобразуется в двоичную запись (пункт 1).

Во втором пункте правил формирования нового числа сказано, что к числу, полученному в первом пункте, дописываются справа ещё два дополнительных разряда.

Про 1 дополнительный разряд указано в подпункте а): «Складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописываются в конец числа (справа). Например, запись 11100 преобразуется в запись 111001.»

Если по простому сказать, то мы подсчитываем количество единиц в двоичном представлении числа N. Если количество единиц чётное, то пишем в 1 дополнительный разряд ноль, если нечётное, то пишем в 1 дополнительный разряд единицу.

Со вторым дополнительным разрядом происходит всё тоже самое, что и с первым разрядом, только когда подсчитываем количество единиц, мы так же подсчитываем и в 1-ом дополнительном разряде.

В вопросе просят указать входящее наименьшее число N, чтобы автомат выдал число R больше 42.

Возьмём наименьшее число, которое больше 42 (т.е. 43) и переведём его в двоичную систему. Это можно сделать с помощью стандартного windows калькулятора.

Вызываем калькулятор, выбираем Вид->Программист. Кликаем на отметку Dec (это означает, что мы находимся в десятичной системе) и набираем число 43. Затем кликаем на отметку Bin

Проверим число 101011₂. Может ли оно быть результатом работы нашего алгоритма?

Отделяем два дополнительных разряда справа. У нас, не считая двух дополнительных разрядов, количество единиц равно двум. Количество чётное, значит, в первом дополнительном разряде должен стоять 0. А у нас стоит 1.

Следовательно, число 101011₂ не может являться результатом работы алгоритма. И это число не подходит.

Проверим последующие числа. На калькуляторе можно прибавлять по 1 и получать следующее число в двоичной системе. Мы проверяем последовательно числа, чтобы не пропустить самое маленькое число.

Подходит число 101110₂. Количество единиц без двух дополнительных разрядов равно трём. Число нечётное. Значит, в первом дополнительном разряде должна стоять 1. В этом числе как раз стоит 1.

Количество единиц вместе с дополнительным разрядом равно 4. Число чётное, значит, во втором дополнительном разряде должен стоять 0. У нас и стоит во втором дополнительном разряде 0. Следовательно, число 101110₂ подходит по всем правилам и является наименьшим.

В десятичной системе это число 46.

Рассмотрим ещё одну интересную задачу для подготовки к ЕГЭ по информатике 2022.

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

1) Строится двоичная запись числа N.
2) Каждый разряд этой записи заменяется двумя разрядами по следующему правилу: если в разряде стоит 0, то вместо него пишется 01; если в разряде стоит 1, то 1 заменяется на 10.
Например, двоичная запись 1010 числа 10 будет преобразована в 10011001.

Полученная таким образом запись (в ней в два раза больше разрядов, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите максимальное нечётное число R, меньшее 256, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе.

Решение на Python.

for n in range(1, 1000): s=format(n, 'b') s2='' for x in s: if x=='0': s2 = s2 + '01' else: s2 = s2 + '10' r=int(s2, 2) if r%2!=0 and rprint(r)

Получается наибольшее число 169.

Здесь после того, как построена строка, содержащая двоичную запись числа n, мы с помощью цикла for перебираем каждый символ и анализируем его.

Предварительно создав переменную s2 для новой строки, мы записываем в неё ’01’ , если анализируемый символ является нулём, и ’10’ , если единицей.

Добавляем заменённые символы справа к строке s2, таким образом, самый первые символы окажутся постепенно слева, как положено.

Далее, делаем, как в прошлой задаче.

Решение с помощью рассуждений.

В этой задаче в начале строится двоичная запись числа N.

Каждый разряд превращается в два разряда! Единица превращается в 10. Ноль превращается в 01. На рисунке показан пример, как будет преобразовано число 10 = 1010₂.

Оценим первое число, которое меньше, чем 256. Это число 255.

Здесь количество разрядов равно 8. Это чётное число, значит, такое количество разрядов может быть в результате работы алгоритма. Только чётное количество разрядов может получится в результате работы алгоритма .

В старших двух разрядах должны быть цифры 10, т.к. исходное число N не может начинаться с нуля.

В остальных парах попробуем написать 10, чтобы число было как можно больше.

Получается, что число 10101010₂ удовлетворяет всем правилам алгоритма, является наибольшим, и оно меньше 256.

Но важный момент, нас просили в ответ записать нечётное число.

В двоичной системе число, которое оканчивается на ноль, является чётным.

В двоичной системе число, которое оканчивается на единицу, является нечётным.

Чтобы число было нечётным, изменим последние разряды на 01.

10101001₂ = 169
Ответ: 169

Набираем обороты в решении 5 задания из ЕГЭ по информатике 2022.

Задача(Классическая, закрепление)

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

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

2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конце числа справа дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1101 будет преобразована в 110111.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа — результата работы данного алгоритма.

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

Решение на Python.

for n in range(1, 1000): s=format(n, 'b') if n%2==0: s=s+'00' else: s=s+'11' r=int(s, 2) if r>130: print(n)

Минимальное число n получается 33.

Обратите внимание, что здесь уже анализируем число n. Если оно чётное, то к переменной s справа дописываем ’00’ , иначе ’11’ . Так же в этой задаче мы печатаем в ответе само число n.

Решение с помощью рассуждений.

После перевода в двоичную систему исходного числа N, алгоритм строит новое число по следующему правилу:

Бордовым прямоугольником показаны дополнительные разряды.

Нужно найти минимальное число больше 130. Будем проверять последовательно числа, начиная с 131.

Подходит число 135. В ответе нужно указать число N. Отбросим от числа 10000111₂ дополнительные разряды и переведём в десятичную систему.

100001₂ = 33
Ответ: 33

Похожие задачи встречались в сборнике С. С. Крылова для подготовке к ЕГЭ по информатике.

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

1. Из числа N вычитается остаток от деления N на 4.

2. Строится двоичная запись полученного результата.

3. К это записи справа дописываются ещё два дополнительных разряда по следующему правилу:

а) Складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописываются в конец числа (справа). Например, запись 11100 преобразуется в запись 111001.

б) Над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись является двоичной записью числа R.

Укажите наибольшее число N, для которого результат работы данного алгоритма меньше 47. В ответе число N укажите в десятичной системе.

Первый способ. Число R должно быть меньше 47. Переведём число 46 в двоичную систему.

Результат от второго пункта не должен превышать 1011₂. Если результат от второго пункта будет превышать это число, то после добавления дополнительных разрядов получится число R, которое не меньше 47.

Проверим число 1011₂ = 11. Видим, что это число не может являться результатом пункта 2.

11 + 0 = 11 ( остаток при делении 11 на 4 равен 3 ) —
11 + 1 = 12 ( остаток при делении 12 на 4 равен 0 ) —
11 + 2 = 13 ( остаток при делении 13 на 4 равен 1 ) —
11 + 3 = 14 ( остаток при делении 13 на 4 равен 2 ) —

Здесь мы перебираем все остатки при делении на 4. Чтобы число 11 могло являться результатом пункта 2, число, помеченное зелёным цветом , должно совпадать с числом, помеченное оранжевым цветом . Стоит заметить, что если в первой строчке не совпадают числа, то и в остальных они тоже не совпадут. Верно и обратное. Если в первой строчке совпадут числа, то и для остальных остатков тоже числа будут совпадать.

Найдём, число, для которого будут совпадать эти числа, отмеченные зелёным и оранжевым цветом.

10 + 0 = 10 ( остаток при делении 10 на 4 равен 2 ) Не подходит
9 + 0 = 9 ( остаток при делении 9 на 4 равен 1 ) Не подходит
8 + 0 = 8 ( остаток при делении 8 на 4 равен 0 ) Подходит!

Значит, число 8 нам подходит. Число 8 — это результат работы алгоритма в первом пункте. Нас просят найти максимальное число. Следовательно, возьмём остаток 3, чтобы исходное число N было как можно больше. Тогда N будет:

Ответ получается 11.

Второй способ. Решим задачу с помощью Python’а.

Перебираем числа от 100 до 1 с помощью цикла for. Третий параметр «-1» в цикле for говорит о том, что мы перебираем числа в обратном порядке.

for i in range(100, 0, -1): n = i n = n - n % 4 # Выполняем первый пункт n = format(n, 'b') # Переводим в двоичную систему n = n + str(n.count('1') % 2) # Подпункт a) третьего пункта n = n + str(n.count('1') % 2) # Подпункт б) третьего пункта r = int(n, 2) # Переводим из двоичной системы в десятичную if r < 47: print(i)

В этой программе запрограммировали алгоритм, который указан в задаче. Если значение переменной r (результат работы алгоритма) меньше 47, то печатаем это значение на экран. Первое распечатанное число и есть ответ к задаче.

В переменную n по очереди подставляются числа из нашего диапазона (100-1). Команда % находит остаток от деления.

Функция count, в данном случае, подсчитывает количество единиц в строке, которая находится в переменной n.

Ответ: 11

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

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

2. Далее эта запись обрабатывается по следующему правилу:

a) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 6₁₀ = 110₂ результатом является число 1000₂ = 8₁₀, а для исходного числа 4₁₀ = 100₂ результатом является число 1101₂ = 13₁₀.

Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 40. В ответе запишите это число в десятичной системе счисления.

for n in range(1, 1000): s=format(n, 'b') if s.count('1')%2==0: s = s + '0' s = '10' + s[2:] else: s = s + '1' s = '11' + s[2:] r=int(s, 2) if r>40: print(n)

Здесь мы пишем программу, как было написано в уроке видеокурса ЕГЭ по информатике. Но, действительно, встречается и новый приём. Нужно изменить левые символы нашей строки s. Это можно сделать с помощью такой конструкции s[2:]. Таким образом, мы берём всю строку, кроме двух первых символов. Например, s=’football’, то s[2:] будет обозначать ‘otball’.

Повторим основные идеи такого подхода при решении пятого задания из ЕГЭ по информатике с помощью программирования. Перебираем числа от 1 до 999 с помощью цикла for. В этом диапазоне надеемся найти наш ответ. С помощью команды format() превращаем число в строку уже в двоичной системе. Сумма цифр в строке зависит только от количества единиц. Нули ничего не дают в сумму. Поэтому применяем функцию .count. Дальше всё делаем, как написано в условии задачи. Команда int(s, 2) превращает строку в двоичной системе в число опять в десятичной системе счисления.

Задача (Решаем с помощью Python)

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

1) Строится двоичная запись числа N.
2) В конец записи (справа) дописывается вторая справа цифра двоичной записи.
3) В конец записи (справа) дописывается вторая слева цифра двоичной записи.
4) Результат переводится в десятичную систему.

Пример. Дано число N = 11. Алгоритм работает следующим образом.
1) Двоичная запись числа N: 11 = 10112
2) Вторая справа цифра 1, новая запись 101112.
3) Вторая слева цифра 0, новая запись 1011102.
4) Десятичное значение полученного числа 46.

При каком наименьшем числе N в результате работы алгоритма получится R > 170? В ответе запишите это число в десятичной системе счисления.

Напишем программу на Python.

for n in range(2, 1000): s=format(n, 'b') s=s+s[-2] s=s+s[1] r=int(s, 2) if r>170: print(n)

Получается наименьшее число 43. К последнему символу можем обратится s[-1], к предпоследнему s[-2]. Но счёт слева начинается с нуля. Первый символ это s[0], второй символ s[1] и т.д.

Обратите внимание, что перебирать числа n в этой задаче начинаем с 2.

Задача(Восьмибитное число)

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

1) Строится восьмибитная двоичная запись числа N.
2) Удаляется последняя цифра двоичной записи.
3) Запись «переворачивается», то есть читается справа налево.
4) Полученное число переводится в десятичную запись и выводится на экран.

Каково наибольшее число, меньшее 100, которое после обработки автоматом не изменится?

for n in range(1, 256): s=format(n, 'b') # делаем 8-ое число while(len(s)<8): s='0'+s s=s[:-1] #удаляется последняя цифра s=s[::-1] #число переворачивается r=int(s, 2) if nand r==n: print(n)

Ответ получается 90.

Восьмибитное число имеет длину 8 символов. После того, как перевели число n в двоичный вид, с помощью цикла while добисываем нули слева к строке s, пока длина этой строки меньше 8.

Удалить последнюю цифру можно с помощью конструкции s[:-1]. Здесь мы оставляем все цифры, начиная с первой до последней (не включительно).

Перевернуть строку можно с помощью конструкции s[::-1].

Далее решаем как обычно. Число не изменится, если входное число n равно выходному числу r.

Разберём задачу, которая была в пробном варианте от 3.02.23 в одном из регионов.

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

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

2. Далее эта запись обрабатывается по следующему правилу:

a) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 1;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11;

Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 6₁₀ = 110₂ результатом является число 100₂ = 4₁₀, а для исходного числа 4₁₀ = 100₂ результатом является число 1101₂ = 13₁₀.

Укажите число N, после обработки которого с помощью этого алгоритма получается наименьшее значение R, большее 49. В ответе запишите это число в десятичной системе.

Напишем программу на языке Python.

for n in range(1, 1000): s=format(n, 'b') if s.count('1')%2==0: s = s + '0' s = '1' + s[2:] else: s = s + '1' s = '11' + s[2:] r=int(s, 2) if r>49: print(r, n)

Хитрость задачки заключается в том, что числа r возрастают неравномерно.

Нам необходимо глазами найти наименьше число r (первое число). Это число 50, а n для него равно 57.

При желании программу можно переписать следующим образом:

r_min=10**9 n_r_min = 0 for n in range(1, 1000): s=format(n, 'b') if s.count('1')%2==0: s = s + '0' s = '1' + s[2:] else: s = s + '1' s = '11' + s[2:] r=int(s, 2) if r > 49: if r < r_min: r_min=r n_r_min=n print(n_r_min)

Здесь ищется минимальное число r автоматически и для него запоминается значение n, которое пойдет в ответ.

Боковой вариант 5-ого задания из ЕГЭ по информатике.

Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам:

1. Перемножаются первая и вторая, а также третья и четвёртая цифры исходного числа.

2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).

Пример. Исходное число: 2465. Суммы: 2 * 4 = 8; 6 * 5 = 30. Результат: 308. Укажите наибольшее число, в результате обработки которого автомат выдаст число 124.

В подобных задачах из ЕГЭ по информатике нумерация происходит начиная со старшего разряда.

Первое правило можно представить следующим образом:

Второе правило заключается в том, что мы «соединяем» два числа, полученных в первом пункте, причём, сначала идёт большее число, а затем меньшее.

Проанализируем число 124.

Чтобы четырёхзначное число было наибольшим, выгодно, чтобы в старшем разряде стояла 9. Но, не у числа 12, не у числа 4, нет такого делителя. Какой наибольший делитель мы можем получить? Это число 6. Число 6 является делителем 12-ти. Значит, первая цифра будет 6, а вторая цифра будет 2 (6*2=12).

Рассмотрим второе число 4. Третий разряд тоже желательно сделать побольше. Значит, в четвёртый разряд поставим 4, а в младший разряд 1 (4*1=4).

Ответ получается 6241.

Ответ: 6241

Счастливых экзаменов! Видеоролик можете посмотреть ниже!

01581

YUMPU automatically turns print PDFs into web optimized ePapers that Google loves.

обогреватели тепла в цехах буржуйкаобогреватели тепловентиляторы купить в москвеобогреватели тепловые пушки в сочиобогреватели термия в одессе ценыобогреватели типа tip и ultraобогреватели топливных фильтров для добогреватели топлиного фильтра и могестралиобогреватели тосола производителя г. кировобогреватели тосола северс 2 мобогреватели уличные и внутри домаобогреватели ульев в г. омскеобогреватели уфо в днепропетровске контактыобогреватели уфо в донецке ценаобогреватели уфо в мелитополе ценаобогреватели уфо в рассрочку купитьобогреватели уфо и аналоги инфракрасныеобогреватели уфо купить в днепреобогреватели уфо купить в донецкеобогреватели уфо купить в житомиреобогреватели уфо купить в киевеобогреватели уфо купить в луганскеобогреватели уфо купить в одессеобогреватели уфо купить в украинеобогреватели уфо на 4 кв.мобогреватели уфо польза и вредобогреватели уфо преимущества и недостаткиобогреватели уфо цена в днепропетровскеобогреватели уфо цена в одесеобогреватели уфо эколайн в днепропетровскеобогреватели уют купить в волгоградеобогреватели фирмы керми в алматыобогреватели фото цены г харьковобогреватели черный с пультом красноярскобогреватели шкафов систем автоматики тобогреватели шкафов систем автоматики цобогреватели эберспехер в автомобилях volvoобогреватели эван в нижнем новгородеобогреватели эко свет в санкт-петербургеобогреватели эколайн в интернет магазинеобогреватели эколайн в огородном проездеобогреватели эколайн в теплице отзывыобогреватели эколайн купить в москвеобогреватели эколайн купить г каломнаобогреватели эколайн отзывы в с-петербургеобогреватели эколайн продажа в москвеобогреватели эколайн продажа в спбобогреватели эколайн цены в луганскеобогреватели эколайн цены и фотообогреватели электрические 220в в москвеобогреватели электрические general в одессеобогреватели электрические в виде батареиобогреватели электрические в виде каминобогреватели электрические в виде каминаобогреватели электрические в подвесной потолокобогреватели электрические за и противобогреватели электрические инфракрасные г стерлитамакобогреватели электрические комнатные с обдувомобогреватели электрические конвекторы в спбобогреватели электрические краснодарский край б/уобогреватели электрические купить в краснодареобогреватели электрические маленькие в актобеобогреватели электрические масляные с таймеромобогреватели электрические на 30 мобогреватели электрические настенные с увылажнителемобогреватели электрические оптом в москвеобогреватели электрические продажа в спбобогреватели электрические с пультом управленияобогреватели электрические с регулированире температурыобогреватели электрические с фото новочеркасскобогреватели электрические световые в севастополеобогреватели электрические тропик в краснодареобогреватели эленберг купить в кировограде

• Page 2 and 3: обогреватели энерг
• Page 4 and 5: обогреватель в дне
• Page 6 and 7: обогреватель для д
• Page 8 and 9: обогреватель инфра
• Page 10 and 11: обогреватель на си
• Page 12 and 13: обогреватель с теп
• Page 14 and 15: обогреватель-карти
• Page 16 and 17: обода с высоким про
• Page 18 and 19: ободки с розами на
• Page 20 and 21: ободок с завязками
• Page 22 and 23: обоеполые цветы об
• Page 24 and 25: обожаю я тебя шуфут
• Page 26 and 27: обозначать электро
• Page 28 and 29: обозначение n в эле
• Page 30 and 31: обозначение алюмин
• Page 32 and 33: обозначение букв в
• Page 34 and 35: обозначение в аукц
• Page 36 and 37: обозначение в прое
• Page 38 and 39: обозначение в элек
• Page 40 and 41: обозначение внесен
• Page 42 and 43: обозначение высоты
• Page 44 and 45: обозначение дальне
• Page 46 and 47: обозначение домов
• Page 48 and 49: обозначение заряда
• Page 50 and 51: обозначение и карт
• Page 52 and 53: обозначение игрока
• Page 54 and 55: обозначение кабеле
• Page 56 and 57: обозначение клаксо
• Page 58 and 59: обозначение кондиц
• Page 60 and 61: обозначение лейкоц
• Page 62 and 63: обозначение мериди
• Page 64 and 65: обозначение на кар
• Page 66 and 67: обозначение натура
• Page 68 and 69: обозначение окрасо
• Page 70 and 71: обозначение перстн
• Page 72 and 73: обозначение пола в
• Page 74 and 75: обозначение прикур
• Page 76 and 77: обозначение размер
• Page 78 and 79: обозначение родино
• Page 80 and 81: обозначение северн
• Page 82 and 83: обозначение слов в
• Page 84 and 85: обозначение спайде
• Page 86 and 87: обозначение тv розе
• Page 88 and 89: обозначение татуир
• Page 90 and 91: обозначение телефо
• Page 92 and 93: обозначение тройни
• Page 94 and 95: обозначение фамили
• Page 96 and 97: обозначение цвета
• Page 98 and 99: обозначение череп
• Page 100 and 101: обозначение эл сче
• Page 102 and 103: обозначение эм в пр
• Page 104 and 105: обозначения антист
• Page 106 and 107: обозначения в гран
• Page 108 and 109: обозначения в прин
• Page 110 and 111: обозначения в схем
• Page 112 and 113: обозначения в элек
• Page 114 and 115: обозначения газора
• Page 116 and 117: обозначения знаков
• Page 118 and 119: обозначения инертн
• Page 120 and 121: обозначения контак
• Page 122 and 123: обозначения на крю
• Page 124 and 125: обозначения операц
• Page 126 and 127: обозначения радиал
• Page 128 and 129: обозначения состав
• Page 130 and 131: обозначения упаков
• Page 132 and 133: обозначения электр
• Page 134 and 135: обозначьте структу
• Page 136 and 137: обозреватель компь
• Page 138 and 139: обои — ужасы и мисти
• Page 140 and 141: обои + в москве деше
• Page 142 and 143: обои + в хорошем кач
• Page 144 and 145: обои + с именем ната
• Page 146 and 147: обои 1024 х 768 рабочий
• Page 148 and 149: обои 1366×768 с логотип
• Page 150 and 151: обои 1920х1080 аниме с
• Page 152 and 153: обои 320х480 мужчина и
• Page 154 and 155: обои art 11-121-09 в ново
• Page 156 and 157: обои elitis в санкт пе
• Page 158 and 159: обои hookedonwalls купить
• Page 160 and 161: обои next wall в интерь
• Page 162 and 163: обои rasch с ветками о
• Page 164 and 165: обои vw jetta 2002 гобои w
• Page 166 and 167: обои а рабочий стол
• Page 168 and 169: обои айгерим в алма
• Page 170 and 171: обои аниме девушки
• Page 172 and 173: обои бауцентр в кра
• Page 174 and 175: обои блондинка в ко
• Page 176 and 177: обои бумажные и т д
• Page 178 and 179: обои в английском с
• Page 180 and 181: обои в виде природн
• Page 182 and 183: обои в гостинную ан
• Page 184 and 185: обои в детскую комн
• Page 186 and 187: обои в екатеринбур
• Page 188 and 189: обои в интерьере ку
• Page 190 and 191: обои в кирпич на ку
• Page 192 and 193: обои в комнату с ба
• Page 194 and 195: обои в кухни в фото
• Page 196 and 197: обои в марьино любл
• Page 198 and 199: обои в отличном кач
• Page 200 and 201: обои в прихожую и ц
• Page 202 and 203: обои в северной ком
• Page 204 and 205: обои в спб для кухн
• Page 206 and 207: обои в стиле ар нув
• Page 208 and 209: обои в стиле пост р
• Page 210 and 211: обои в тёмном стиле
• Page 212 and 213: обои в черно белом
• Page 214 and 215: обои весна с разреш
• Page 216 and 217: обои виниловые цен
• Page 218 and 219: обои г екатеринбур
• Page 220 and 221: обои голые девушки
• Page 222 and 223: обои грэм и браун 197
• Page 224 and 225: обои девушек с bmw 3о
• Page 226 and 227: обои девушка и мото
• Page 228 and 229: обои девушки в боди
• Page 230 and 231: обои девушки и авто
• Page 232 and 233: обои девушки с мужч
• Page 234 and 235: обои джоли в 2008 год
• Page 236 and 237: обои для андроид с
• Page 238 and 239: обои для детской ко
• Page 240 and 241: обои для зала три д
• Page 242 and 243: обои для компа с ко
• Page 244 and 245: обои для компютера
• Page 246 and 247: обои для кухни с по
• Page 248 and 249: обои для пк в архив
• Page 250 and 251: обои для рабочего с
• Page 252 and 253: обои для ремонта в
• Page 254 and 255: обои для спальни г.
• Page 256 and 257: обои для стен в инт
• Page 258 and 259: обои для стен в сам
• Page 260 and 261: обои для стен с бус
• Page 262 and 263: обои для стен с соз
• Page 264 and 265: обои для телефона с
• Page 266 and 267: обои дорогих котте
• Page 268 and 269: обои жидкий камень
• Page 270 and 271: обои зима и красивы
• Page 272 and 273: обои и заставки window
• Page 274 and 275: обои и картинки в 240
• Page 276 and 277: обои и картинки так
• Page 278 and 279: обои и полы sims 2обои
• Page 280 and 281: обои и темы для ps3об
• Page 282 and 283: обои и фото брендон
• Page 284 and 285: обои и фото эмилия
• Page 286 and 287: обои из бамбука г. в
• Page 288 and 289: обои из мультфильм
• Page 290 and 291: обои или покраска в
• Page 292 and 293: обои к 8 марта цветы
• Page 294 and 295: обои к дня святого
• Page 296 and 297: обои к к ф видокобо
• Page 298 and 299: обои к программе бо
• Page 300 and 301: обои к фильму little chi
• Page 302 and 303: обои к фильму зал с
• Page 304 and 305: обои к фильму подзе
• Page 306 and 307: обои к фильмукровь
• Page 308 and 309: обои картинки день
• Page 310 and 311: обои клевые кошки и
• Page 312 and 313: обои коттеджи и заг
• Page 314 and 315: обои красный закат
• Page 316 and 317: обои ландшафты гор
• Page 318 and 319: обои м. бибирево ст
• Page 320 and 321: обои машина в занос
• Page 322 and 323: обои море девушка и
• Page 324 and 325: обои мягкие игрушк
• Page 326 and 327: обои на десктоп с д
• Page 328 and 329: обои на компьютер и
• Page 330 and 331: обои на кухню в сар
• Page 332 and 333: обои на почепской в
• Page 334 and 335: обои на рабочий сто
• Page 336 and 337: обои на стену в ква
• Page 338 and 339: обои на стены в дет
• Page 340 and 341: обои на стол г. влад
• Page 342 and 343: обои на у nokia 5800обои
• Page 344 and 345: обои настенные с фл
• Page 346 and 347: обои новый год а ка
• Page 348: обои образцы в г. ст

Сколько единиц в двоичной записи числа 77716

12+ ИНФОРМАТИКА Я. Н. Зайдельман М. А. Ройтберг ДИАГНОСТИЧЕСКИЕ РАБОТЫ Библиотечка ЕГЭ 2019 ИНФОРМАТИКА н рг абрис.рф • www.textbook.ru Москва: 8 (495) 229-67-59 Санкт-Петербург: 8 (812) 327-04-50 e-mail: [email protected] Оптовые заказы: [email protected] Розничные заказы: Интернет-магазин UMLIT.RU www.umlit.ru • e-mail: [email protected] 8 (495) 981-10-39 ОПТОВЫЕ И РОЗНИЧНЫЕ ЗАКАЗЫ В МОСКВЕ И РЕГИОНАХ – В МАГАЗИНЕ «МАТЕМАТИЧЕСКАЯ КНИГА» в здании Московского центра непрерывного математического образования (МЦНМО) biblio.mccme.ru e-mail: [email protected] Интернет-магазин biblio.mccme.ru 8 (495) 745-80-31 ОПТОВЫЕ И РОЗНИЧНЫЕ ЗАКАЗЫ В РЕГИОНАХ – КНИГОТОРГОВАЯ КОМПАНИЯ «АБРИС» 119002, Москва, Большой Власьевский пер., 11. (м. «Смоленская», «Кропоткинская») Ежедневно, 10.00–20.00, кроме воскресенья 2019

Государственное автономное образовательное учреждение дополнительного профессионального образования города Москвы «Центр педагогического мастерства» Я. Н. Зайдельман, М. А. Ройтберг Информатика и ИКТ Подготовка к ЕГЭ в  году Диагностические работы Библиотечка СтатГрад Материалы книги соответствуют Федеральному государственному образовательному стандарту (ФГОС) Москва Издательство МЦНМО 

УДК :. ББК .я З Научно-методическая экспертиза: Евгения Игоревна Фурлетова З Зайдельман Я. Н., Ройтберг М. А. Информатика и ИКТ. Подготовка к ЕГЭ в  году. Диагностические работы. — М.: МЦНМО, . ISBN ---- Данное пособие предназначено для отработки практических умений и навыков учащихся при подготовке к экзамену по информатике в  классе в формате ЕГЭ. Оно содержит варианты диагностических работ по информатике, содержание которых соответствует контрольноизмерительным материалам, разработанным Федеральным институтом педагогических измерений для проведения Единого государственного экзамена. В книгу входят также ответы к заданиям и критерии проверки и оценивания выполнения заданий с развёрнутым ответом. Авторы пособия являются разработчиками тренировочных и диагностических работ для системы СтатГрад (http://statgrad.org). Материалы книги рекомендованы учителям и методистам для выявления уровня и качества подготовки учащихся по предмету, определения степени их готовности к Единому государственному экзамену. Издание соответствует Федеральному государственному образовательному стандарту (ФГОС). ББК .я Оригинал-макет издания подготовлен в ГАОУ ДПО ЦПМ. Приказом №  Министерства образования и науки Российской Федерации Московский центр непрерывного математического образования включён в перечень организаций, осуществляющих издание учебных пособий, допущенных к использованию в образовательном процессе. Учебно-методическое издание Яков Наумович Зайдельман, Михаил Абрамович Ройтберг ИНФОРМАТИКА И ИКТ. ПОДГОТОВКА К ЕГЭ В 2019 ГОДУ. ДИАГНОСТИЧЕСКИЕ РАБОТЫ Подписано в печать .. г. Формат 70 × 90 /. Бумага офсетная. Печать офсетная. Тираж  экз. Заказ № . Издательство Московского центра непрерывного математического образования. , Москва, Большой Власьевский пер., д. . Тел. () --. Отпечатано в ООО «Типография ” Миттель Пресс“». г. Москва, ул. Руставели, д. , стр. . Тел./факс + () --, --. E-mail: [email protected] Книги издательства МЦНМО можно приобрести в магазине «Математическая книга», Москва, Большой Власьевский пер., д. . Тел. () --. E-mail: [email protected] 12+ ISBN ---- © Зайдельман Я. Н., Ройтберг М. А., . © МЦНМО, .

3 Предисловие СтатГрад – это всероссийский интернет-проект, созданный для того, чтобы обеспечить каждое образовательное учреждение качественными дидактическими и методическими материалами. Основные направления деятельности СтатГрада – система диагностики образовательных достижений учащихся, методическая поддержка систем внутришкольного контроля, учебно-методические материалы для подготовки учащихся к ЕГЭ и ОГЭ. СтатГрад предоставляет методические материалы по всем ведущим дисциплинам школьной программы: математике, физике, биологии, русскому языку, литературе, истории, обществознанию, химии, информатике, географии, иностранным языкам. Использование на уроках и при самостоятельной работе тренировочных и диагностических работ в формате ЕГЭ и ОГЭ, диагностических работ для 5–11 классов позволит учителям выявить пробелы в знаниях учащихся, а учащимся – подготовиться к государственным экзаменам, заранее попробовать свои силы. Авторы и эксперты СтатГрада – специалисты высокого класса, кандидаты и доктора наук, авторы учебной литературы для средней и высшей школы. В настоящее время СтатГрад сотрудничает более чем с 13 000 образовательных учреждений России. Настоящий сборник содержит варианты работ, разработанных специалистами СтатГрада для подготовки учащихся выпускных классов к ЕГЭ по информатике. Каждый вариант содержит 27 заданий − 23 задания с кратким ответом и 4 задания с развёрнутым ответом. Материалы соответствуют нормативным документам ФИПИ 2018 года.

4 Инструкция по выполнению работы Экзаменационная работа по информатике состоит из двух частей, включающих в себя 27 заданий. Часть 1 содержит 23 задания с кратким ответом. Часть 2 содержит 4 задания с развёрнутым ответом. На выполнение работы отводится 3 часа 55 минут (235 минут). Ответы к заданиям 1–23 записываются в виде числа, последовательности букв или цифр. Для выполнения заданий 24–27 Вам необходимо написать развёрнутый ответ в произвольной форме. При выполнении заданий можно пользоваться черновиком. Записи в черновике не учитываются при оценивании работы. Баллы, полученные Вами за выполненные задания, суммируются. Постарайтесь выполнить как можно больше заданий и набрать наибольшее количество баллов. Желаем успеха!

5 В заданиях используются следующие соглашения. 1. Обозначения для логических связок (операций): a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А); b) конъюнкция (логическое умножение, логическое И) обозначается /\ (например, А /\ В) либо & (например, А & В); c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/ (например, А \/ В) либо | (например, А | В); d) следование (импликация) обозначается → (например, А → В); e) тождество обозначается ≡ (например, A ≡ B); выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны); f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания). 2. Два логических выражения, содержащие переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А \/ В и А /\ В неравносильны (значения выражений разные, например при А = 1, В = 0). 3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А /\ В \/ С /\ D означает то же, что и ((¬А) /\ В) \/ (С /\ D). Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится и к дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С. 4. Обозначения Мбайт и Кбайт используются в традиционном для информатики смысле – как обозначения единиц измерения, соотношение которых с единицей «байт» выражается степенью двойки.

6 Вариант 1 Часть 1 Ответами к заданиям 1–23 являются число, последовательность букв или цифр. Запишите ответы в указанном месте без пробелов, запятых и других дополнительных символов. Сколько единиц в двоичной записи числа 77716? Ответ: ___________________________. Логическая функция F задаётся выражением z /\ ¬w /\ (y → x). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z. Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция . . . . F 1 0 0 0 1 1 0 1 0 1 1 0 1 1 1 В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x → y, зависящее от двух переменных, x и y, и таблица истинности: Переменная 1 Переменная 2 Функция . . F 0 0 1 0 1 0 1 0 1 1 1 1 Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx. Ответ: ___________________________. 1 2

Вариант 1 7 На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. П1 П2 П3 П4 П5 П6 П7 П8 П1 37 23 П2 25 44 46 П3 25 П4 37 34 42 П5 34 24 28 П6 44 24 29 П7 42 28 29 31 П8 23 46 31 Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Г. В ответе запишите целое число. ВНИМАНИЕ. Длины отрезков на схеме не отражают длины дорог. Ответ: ___________________________. 3

Вариант 1 8 Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. На основании приведённых данных определите, сколько всего внуков и внучек у Буряка Б.Ф. Таблица 1 Таблица 2 ID Фамилия_И.О. Пол ID_Родителя ID_Ребёнка 1224 Крицюк Д.К. Ж 1224 1269 1225 Буряк Б.Ф. М 1224 1296 1237 Семак В.А. Ж 1225 1269 1243 Кахиани К.Г. М 1225 1296 1258 Мазуркевич Л.А. Ж 1269 1237 1262 Иштоян А.И. Ж 1269 1399 1269 Буряк А.Б. Ж 1269 1414 1290 Крук П.А. Ж 1296 1353 1296 Буряк И.Б. М 1296 1375 1307 Решко Г.Р. Ж 1307 1353 1328 Мазуркевич А.П. М 1307 1375 1353 Буряк Т.И. Ж 1328 1237 1375 Буряк П.И. М 1328 1399 1384 Сафина Р.Г. Ж 1328 1414 1399 Онопко М.А. Ж 1384 1258 1414 Мазуркевич П.А. М 1384 1290 … … … … … Ответ: ___________________________. По каналу связи передаются сообщения, содержащие только четыре буквы: Р, Е, К, А; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Р, Е используются такие кодовые слова: А: 111, Р: 0, Е: 100. Укажите кратчайшее кодовое слово для буквы К. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Ответ: ___________________________. 4 5

Вариант 1 9 Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам. 1. Складываются отдельно первая и вторая, а также вторая и третья цифры. 2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей. Пример. Исходное число: 872. Суммы: 8 + 7 = 15; 7 + 2 = 9. Результат: 915. Укажите наименьшее число, при обработке которого автомат выдаёт результат 812. Ответ: ___________________________. Дан фрагмент электронной таблицы. A B C D 1 7 4 5 2 = B2 + C2 + D2 = C2 = (A1 – D1) * (B1 – 3) = (A1 – D1) * C1 Какое целое число должно быть записано в ячейке B1, чтобы диаграмма, построенная по значениям ячеек диапазона A2:D2, соответствовала рисунку? Известно, что все значения ячеек из рассматриваемого диапазона неотрицательны. Ответ: ___________________________. Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования. Бейсик Python DIM S, N AS INTEGER S = 25 N = 0 WHILE 400 < S*S S = S - 1 N = N + 2 WEND PRINT N s = 25 n = 0 while 400 < s*s: s = s - 1 n = n + 2 print(n) 6 7 8

Вариант 1 10 Алгоритмический язык Паскаль алг нач цел s, n n := 0 s := 25 нц пока 400 < s*s s := s - 1 n := n + 2 кц вывод n кон var s, n: integer; begin s := 25; n := 0; while 400 < s*s do begin s := s - 1; n := n + 2 end; writeln(n) end. С++ #include using namespace std; int main() < int s = 25, n = 0; while (400 < s*s) < s = s - 1; n = n + 2; >cout Ответ: ___________________________. Производится четырёхканальная (квадро) звукозапись с частотой дискретизации 32 кГц и 32-битным разрешением. Запись длится 3 минуты, её результаты записываются в файл, сжатие данных не производится. Определите приблизительно размер полученного файла в Мбайт. В качестве ответа укажите ближайшее к размеру файла целое число, кратное 10. Ответ: ___________________________. Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 4-буквенные слова, в которых есть только буквы A, B, C, D, X, Y, Z, причём буквы X, Y и Z встречаются только на двух первых позициях, а буквы A, B, C, D – только на двух последних. Сколько различных кодовых слов может использовать Олег? Ответ: ___________________________. 9 10

Вариант 1 11 Ниже на пяти языках программирования записаны рекурсивные функции F и G. Бейсик Паскаль FUNCTION F(n) IF n > 2 THEN F = F(n-1) + G(n-2) ELSE F = n+1 END IF END FUNCTION FUNCTION G(n) IF n > 2 THEN G = G(n-1) + F(n-2) ELSE G = n END IF END FUNCTION function F(n: integer): integer; begin if n > 2 then F := F(n-1) + G(n-2) else F := n+1; end; function G(n: integer): integer; begin if n > 2 then G := G(n-1) + F(n-2) else G := n; end; С++ Алгоритмический язык int F(int n) < if (n >2) return F(n-1) + G(n-2); else return n+1; > int G(int n) < if (n >2) return G(n-1) + F(n-2); else return n; > алг цел F(цел n) нач если n > 2 то знач := F(n-1) + G(n-2) иначе знач := n+1 все кон алг цел G(цел n) нач если n > 2 то знач := G(n-1) + F(n-2) иначе знач := n все кон Python def F(n): if n > 2: return F(n-1) + G(n-2) else: return n+1 def G(n): if n > 2: return G(n-1) + F(n-2) else: return n Чему будет равно значение, вычисленное при выполнении вызова F(7)? Ответ: ___________________________. 11

Вариант 1 12 В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места – нули. Обычно маска записывается по тем же правилам, что и IP-адрес – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0. Для узла с IP-адресом 93.138.88.47 адрес сети равен 93.138.80.0. Чему равен третий слева байт маски? Ответ запишите в виде десятичного числа. Ответ: ___________________________. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 20 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом пользователе отведено одинаковое минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым минимально возможным количеством бит. Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено 12 байт на каждого пользователя. Сколько байт нужно для хранения сведений о 25 пользователях? В ответе запишите только целое число – количество байт. Ответ: ___________________________. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется. 12 13 14

Вариант 1 13 Цикл ПОКА условие последовательность команд КОНЕЦ ПОКА выполняется, пока условие истинно. В конструкции ЕСЛИ условие ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ выполняется команда1 (если условие истинно) или команда2 (если условие ложно). Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 85 идущих подряд цифр 7? В ответе запишите полученную строку. НАЧАЛО ПОКА нашлось (333) ИЛИ нашлось (777) ЕСЛИ нашлось (333) ТО заменить (333, 7) ИНАЧЕ заменить (777, 3) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Ответ: ___________________________. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Т? Ответ: ___________________________. 15

Вариант 1 14 В системе счисления с основанием N запись числа 9310 оканчивается на 2 и содержит не менее трёх цифр. Чему равно число N? Ответ: ___________________________. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Запрос Найдено страниц (в тысячах) Линкор | Корвет 3400 Линкор & Корвет 1300 Линкор 2100 Какое количество страниц (в тысячах) будет найдено по запросу Корвет? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. Ответ: ___________________________. На числовой прямой даны два отрезка: P = [17, 40] и Q = [20, 57]. Отрезок A таков, что приведённая ниже формула истинна при любом значении переменной х: ¬(x A) → (((x P) /\ (x Q)) → (x A)) Какова наименьшая возможная длина отрезка A? Ответ: ___________________________. 16 17 18

Вариант 1 15 Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы. В программе описан одномерный целочисленный массив A; в представленном фрагменте обрабатываются элементы массива с индексами от 1 до 10. Бейсик Паскаль n = 10 d = 6 FOR j = 1 TO d s = A(1) FOR i = 1 TO n-1 A(i) = A(i+1) NEXT i A(10) = s NEXT j n := 10; d := 6; for j:=1 to d do begin s := A[1]; for i:=1 to n-1 do begin A[i] := A[i+1]; end; A[10] := s; end; С++ Алгоритмический язык n = 10; d = 6; for (j = 1; j A[10] = s; > n := 10 d := 6 нц для j от 1 до d s := A[1] нц для i от 1 до n-1 A[i] := A[i+1] кц A[10]:= s кц Python n = 10 d = 6 for j in range(1,d+1): s = A[1] for i in range(1,n): A[i] = A[i+1] A[10] = s Перед началом выполнения программы эти элементы массива имели значения 0, 1, 2, 3, 4, 5, 4, 3, 2, 1 (т.е. A[1] = 0; A[2] = 1; …; A[10] = 1). Значение какого из этих элементов массива будет наибольшим после выполнения фрагмента программы? В ответе укажите индекс элемента – число от 1 до 10. Ответ: ___________________________. 19

Вариант 1 16 Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наибольшее из таких чисел x, при вводе которого алгоритм печатает сначала 3, а потом 14. Бейсик Паскаль DIM X, A, B AS INTEGER INPUT X A = 0: B = 0 WHILE X > 0 A = A + 1 IF X MOD 2 = 0 THEN B = B + X MOD 10 END IF X = X \ 10 WEND PRINT A PRINT B var x, a, b: integer; begin readln(x); a := 0; b := 0; while x > 0 do begin a := a + 1; if x mod 2= 0 then b := b + x mod 10; x := x div 10; end; writeln(a); write(b); end. С++ Алгоритмический язык #include using namespace std; int main() < int x, a, b; cin >> x; a = 0; b = 0; while (x > 0) < a = a+1; if (x%2 == 0) < b = b + x%10; >x = x / 10; > cout алг нач цел x, a, b ввод x a := 0; b := 0 нц пока x > 0 a := a+1 если mod(x,2)=0 то b := b + mod(x,10) все x := div(x,10) кц вывод a, нс, b кон Python x = int(input()) a=0; b=0 while x>0: a = a+1 if x%2==0: b += x%10 x = x//10 print(a, b) Ответ: ___________________________. 20

Вариант 1 17 Напишите в ответе наименьшее значение входной переменной k, при котором программа выдаёт ответ 11. Для Вашего удобства программа приведена на пяти языках программирования. Бейсик С++ DIM K, I AS LONG INPUT K I = 1 WHILE F(I) < K I = I + 1 WEND PRINT I FUNCTION F(N) F = N * N END FUNCTION #include using namespace std; long f(long n) < return n * n; >int main() < long k, i; cin >> k; i = 1; while (f(i) < k) i++; cout Алгоритмический язык Паскаль алг нач цел k, i ввод k i := 1 нц пока f(i) < k i := i + 1 кц вывод i кон алг цел f(цел n) нач знач := n * n кон var k, i : longint; function f(n: longint): longint; begin f := n * n; end; begin readln(k); i := 1; while f(i) < k do i := i+1; writeln(i) end. Python def f(n): return n*n k = int(input()) i = 1 while f(i) < k: i += 1 print (i) Ответ: ___________________________. 21

Вариант 1 18 Исполнитель Тренер преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя Тренер – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 11? Ответ: ___________________________. Сколько существует различных наборов значений логических переменных x1, x2, . x8, y1, y2, . y8, которые удовлетворяют всем перечисленным ниже условиям? (x1→x2) /\ (y1→y2) = 1 (x2→x3) /\ (y2→y3) = 1 … (x7→x8) /\ (y7→y8) = 1 В ответе не нужно перечислять все различные наборы значений переменных x1, x2, . x8, y1, y2, . y8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов. Ответ: ___________________________. 22 23

Вариант 1 19 Часть 2 Для записи ответов на задания этой части (24–27) используйте отдельный лист. Запишите сначала номер задания (24, 25 и т. д.), а затем – полное решение. Ответы записывайте чётко и разборчиво. Даны целые числа A и B, 0 ≤ B ≤ A. Последовательно вычисляются значения A – 1, A – 1 – 2, A – 1 – 2 – 3 и т. д. Необходимо вывести наибольшее из этих значений, которое меньше B. Для решения этой задачи ученик написал программу, но, к сожалению, его программа неправильная. Ниже эта программа для Вашего удобства приведена на пяти языках программирования. Паскаль Python var a, b, s, k: integer; begin read(a,b); if not ((0 <=b) and (b<=a)) then writeln('Неверные данные') else begin s := 0; k := 0; while s >b do begin k := k+1; s := s-k; end; writeln(s) end end. a = int(input()) b = int(input()) if not 0 b: k = k+1 s = s-k print(s) Алгоритмический язык Бейсик алг нач цел a, b, s, k ввод a, b если не 0 b k := k+1 s := s-k кц вывод s все кон DIM A,B,S,K AS INTEGER INPUT A, B IF NOT (0 B K = K + 1 S = S — K WEND PRINT S END IF END 24

Вариант 1 20 С++ #include using namespace std; int main()< int a, b, s, k; cin >> a >> b; if (!(0 b) < k = k+1; s = s-k; >cout return 0; > Последовательно выполните следующее. 1. Напишите, что выведет эта программа при вводе чисел 12345 и 1234. 2. Приведите пример таких значений A и B, при вводе которых программа выведет правильный числовой ответ. 3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде. Достаточно указать ошибки и способ их исправления для одного языка программирования. Обратите внимание: Вам нужно исправить приведённую программу, а не написать свою. Вы можете только заменять ошибочные строки, но не можете удалять строки или добавлять новые. Заменять следует только ошибочные строки: за исправления, внесённые в строки, не содержащие ошибок, баллы будут снижаться.

Вариант 1 21 Дан массив, содержащий 2018 положительных целых чисел, не превышающих 10 000. Необходимо найти и вывести максимальный из тех элементов этого массива, десятичная и шестнадцатеричная запись которых заканчивается одним и тем же символом. Если таких чисел в массиве нет, ответ считается равным нулю. Например, для массива из четырёх элементов, равных 80, 91, 162 и 250, в ответе должно получиться 162. В шестнадцатеричном виде эти числа записываются как 50, 5B, A2 и FA. Последний символ в десятичной и шестнадцатеричной записи совпадает у первого и третьего чисел, большее из них – третье, то есть 162. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных. Бейсик Python CONST N=2018 DIM A(N) AS INTEGER DIM I, M, K AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I … END # допускается также использо- # вание целочисленных # переменных m, k a = [] N = 2018 for i in range(0, N): a.append(int(input())) … Алгоритмический язык Паскаль алг нач цел N=2018 целтаб a[1:N] цел i, m, k нц для i от 1 до N ввод a[i] кц … кон const N=2018; var a: array [1..N] of integer; i, m, k: integer; begin for i:=1 to N do readln(a[i]); … end. С++ #include using namespace std; const int N = 2018; int main()< int a[N]; int i, m, k; for (i=0; i> a[i]; … return 0; > 25

Вариант 1 22 В качестве ответа необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и версию языка программирования, например Free Pascal 2.6). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 38. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 38 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 37. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника. Выполните следующие задания. Во всех случаях обосновывайте свой ответ. Задание 1. У кого из игроков есть выигрышная стратегия при S = 12? Опишите эту стратегию. Задание 2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого из указанных значений S опишите выигрышную стратегию Пети. Задание 3. Укажите значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, однако у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте в виде рисунка или таблицы дерево всех партий, возможных при этой выигрышной стратегии Вани. На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции. 26

Вариант 1 23 Дан набор из N целых положительных чисел. Для каждого числа вычисляется сумма двух последних цифр в его десятичной записи (для однозначных чисел предпоследняя цифра считается равной нулю). Необходимо определить, какая сумма при этом получается чаще всего. Если таких сумм несколько, необходимо вывести наибольшую из них. Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N. Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла. Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла. Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́ льшая из двух оценок. Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Пример входных данных: 5 15 417 123 6 4841 Пример выходных данных для приведённого выше примера входных данных: 6 Суммы двух последних цифр для чисел из данного набора равны 6, 8, 5, 6, 5. Чаще других (по два раза) встречаются 6 и 5, в ответе выводится бо́ льшая из этих сумм. 27

24 Вариант 2 Часть 1 Ответами к заданиям 1–23 являются число, последовательность букв или цифр. Запишите ответы в указанном месте без пробелов, запятых и других дополнительных символов. Сколько единиц в двоичной записи числа 7778? Ответ: ___________________________. Логическая функция F задаётся выражением z /\ ¬y /\ (w → x). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z. Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция . . . . F 1 0 0 0 1 1 0 1 0 1 1 0 1 1 1 В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x → y, зависящее от двух переменных, x и y, и таблица истинности: Переменная 1 Переменная 2 Функция . . F 0 0 1 0 1 0 1 0 1 1 1 1 Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx. Ответ: ___________________________. 1 2

Вариант 2 25 На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. П1 П2 П3 П4 П5 П6 П7 П8 П1 62 84 56 58 П2 62 46 92 П3 46 74 П4 92 50 88 П5 50 П6 84 74 68 П7 56 68 48 П8 58 88 48 Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Г. В ответе запишите целое число. ВНИМАНИЕ. Длины отрезков на схеме не отражают длины дорог. Ответ: ___________________________. 3

Вариант 2 26 Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. На основании приведённых данных определите, сколько всего внуков и внучек у Кравец Д.К. Таблица 1 Таблица 2 ID Фамилия_И.О. Пол ID_Родителя ID_Ребёнка 866 Кравец Д.К. Ж 866 911 867 Тошич Б.Ф. М 866 938 879 Гонтарь В.А. Ж 867 911 885 Крон К.Г. М 867 938 900 Кислюк Л.А. Ж 911 879 904 Петраш А.И. М 911 1041 911 Тошич А.Б. Ж 904 900 932 Петраш П.А. Ж 938 995 938 Тошич И.Б. М 938 1017 949 Седых Г.Р. Ж 949 995 970 Кислюк А.П. М 949 1017 995 Тошич Т.И. Ж 970 879 1017 Тошич П.И. М 970 1041 1026 Мухина Р.Г. Ж 904 932 1041 Сайко М.А. Ж 1026 900 1056 Кислюк П.А. М 1026 932 … … … … … Ответ: ___________________________. По каналу связи передаются сообщения, содержащие только четыре буквы: М, О, Р, Е; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв О, Р, Е используются такие кодовые слова: О: 111, Р: 0, Е: 100. Укажите кратчайшее кодовое слово для буквы М. Если таких кодов несколько, укажите код с наибольшим числовым значением. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Ответ: ___________________________. 4 5

Вариант 2 27 Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам. 1. Складываются отдельно первая и вторая, а также вторая и третья цифры. 2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей. Пример. Исходное число: 872. Суммы: 8 + 7 = 15; 7 + 2 = 9. Результат: 915. Укажите наименьшее число, при обработке которого автомат выдаёт результат 714. Ответ: ___________________________. Дан фрагмент электронной таблицы. A B C D 1 9 2 5 2 = B2 + C2 + D2 = C2 = (A1 – D1) * (B1 – 5) = (A1 – D1) * C1 Какое целое число должно быть записано в ячейке B1, чтобы диаграмма, построенная по значениям ячеек диапазона A2:D2, соответствовала рисунку? Известно, что все значения ячеек из рассматриваемого диапазона неотрицательны. Ответ: ___________________________. Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования. Бейсик Python DIM S, N AS INTEGER S = 25 N = 0 WHILE 400 < S*S S = S - 1 N = N + 3 WEND PRINT N s = 25 n = 0 while 400 < s*s: s = s - 1 n = n + 3 print(n) 6 7 8

Вариант 2 28 Алгоритмический язык Паскаль алг нач цел s, n s := 25 n := 0 нц пока 400 < s*s s := s - 1 n := n + 3 кц вывод n кон var s, n: integer; begin s := 25; n := 0; while 400 < s*s do begin s := s - 1; n := n + 3 end; writeln(n) end. С++ #include using namespace std; int main() < int s = 25, n = 0; while (400 < s*s) < s = s - 1; n = n + 3; >cout Ответ: ___________________________. Производится двухканальная (стерео) звукозапись с частотой дискретизации 32 кГц и 32-битным разрешением. Запись длится 3 минуты, её результаты записываются в файл, сжатие данных не производится. Определите приблизительно размер полученного файла в Мбайт. В качестве ответа укажите ближайшее к размеру файла целое число, кратное 5. Ответ: ___________________________. Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 4-буквенные слова, в которых есть только буквы A, B, C, D, E, X, Z, причём буквы X и Z встречаются только на двух первых позициях, а буквы A, B, C, D, E – только на двух последних. Сколько различных кодовых слов может использовать Олег? Ответ: ___________________________. 9 10

Вариант 2 29 Ниже на пяти языках программирования записаны рекурсивные функции F и G. Бейсик Паскаль FUNCTION F(n) IF n > 2 THEN F = F(n-1) + G(n-2) ELSE F = n+1 END IF END FUNCTION FUNCTION G(n) IF n > 2 THEN G = G(n-1) + F(n-2) ELSE G = n END IF END FUNCTION function F(n: integer): integer; begin if n > 2 then F := F(n-1) + G(n-2) else F := n+1; end; function G(n: integer): integer; begin if n > 2 then G := G(n-1) + F(n-2) else G := n; end; С++ Алгоритмический язык int F(int n) < if (n >2) return F(n-1) + G(n-2); else return n+1; > int G(int n) < if (n >2) return G(n-1) + F(n-2); else return n; > алг цел F(цел n) нач если n > 2 то знач := F(n-1) + G(n-2) иначе знач := n+1 все кон алг цел G(цел n) нач если n > 2 то знач := G(n-1) + F(n-2) иначе знач := n все кон Python def F(n): if n > 2: return F(n-1) + G(n-2) else: return n+1 def G(n): if n > 2: return G(n-1) + F(n-2) else: return n Чему будет равно значение, вычисленное при выполнении вызова G(7)? Ответ: ___________________________. 11

Вариант 2 30 В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места – нули. Обычно маска записывается по тем же правилам, что и IP-адрес – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0. Для узла с IP-адресом 93.138.96.47 адрес сети равен 93.138.64.0. Чему равен третий слева байт маски? Ответ запишите в виде десятичного числа. Ответ: ___________________________. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 20 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом пользователе отведено одинаковое минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым минимально возможным количеством бит. Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено 12 байт на каждого пользователя. Сколько байт нужно для хранения сведений о 35 пользователях? В ответе запишите только целое число – количество байт. Ответ: ___________________________. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется. 12 13 14

Вариант 2 31 Цикл ПОКА условие последовательность команд КОНЕЦ ПОКА выполняется, пока условие истинно. В конструкции ЕСЛИ условие ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ выполняется команда1 (если условие истинно) или команда2 (если условие ложно). Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 76 идущих подряд цифр 9? В ответе запишите полученную строку. НАЧАЛО ПОКА нашлось (666) ИЛИ нашлось (999) ЕСЛИ нашлось (666) ТО заменить (666, 9) ИНАЧЕ заменить (999, 6) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Ответ: ___________________________. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Т? Ответ: ___________________________. 15

Вариант 2 32 В системе счисления с основанием N запись числа 14410 оканчивается на 1 и содержит не менее трёх цифр. Чему равно число N? Ответ: ___________________________. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Запрос Найдено страниц (в тысячах) Линкор | Корвет 3320 Линкор & Корвет 1300 Линкор 2100 Какое количество страниц (в тысячах) будет найдено по запросу Корвет? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. Ответ: ___________________________. На числовой прямой даны два отрезка: P = [17, 46] и Q = [22, 57]. Отрезок A таков, что приведённая ниже формула истинна при любом значении переменной х: ¬(x A) → (((x P) /\ (x Q)) → (x A)) Какова наименьшая возможная длина отрезка A? Ответ: ___________________________. 16 17 18

Вариант 2 33 Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы. В программе описан одномерный целочисленный массив A; в представленном фрагменте программы обрабатываются элементы массива с индексами от 1 до 10. Бейсик Паскаль n = 10 d = 6 FOR j = 1 TO d s = A(1) FOR i = 1 TO n-1 A(i) = A(i+1) NEXT i A(10) = s NEXT j n := 10; d := 6; for j:=1 to d do begin s := A[1]; for i:=1 to n-1 do begin A[i] := A[i+1]; end; A[10] := s; end; С++ Алгоритмический язык n = 10; d = 6; for (j = 1; j A[10] = s; > n := 10 d := 6 нц для j от 1 до d s := A[1] нц для i от 1 до n-1 A[i] := A[i+1] кц A[10]:= s кц Python n = 10 d = 6 for j in range(1,d+1): s = A[1]; for i in range(1,n): A[i] = A[i+1] A[10] = s Перед началом выполнения программы эти элементы массива имели значения 0, 1, 4, 9, 6, 5, 6, 8, 4, 1 (т.е. A[1] = 0; A[2] = 1; …; A[10] = 1). Значение какого из этих элементов массива будет наибольшим после выполнения фрагмента программы? В ответе укажите индекс элемента – число от 1 до 10. Ответ: ___________________________. 19

Вариант 2 34 Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наибольшее из таких чисел x, при вводе которого алгоритм печатает сначала 3, а потом 12. Бейсик Паскаль DIM X, A, B AS INTEGER INPUT X A = 0: B = 0 WHILE X > 0 A = A + 1 IF X MOD 2 = 0 THEN B = B + X MOD 10 END IF X = X \ 10 WEND PRINT A PRINT B var x, a, b: integer; begin readln(x); a := 0; b := 0; while x > 0 do begin a := a + 1; if x mod 2= 0 then b := b + x mod 10; x := x div 10; end; writeln(a); write(b); end. С++ Алгоритмический язык #include using namespace std; int main() < int x, a, b; cin >> x; a = 0; b = 0; while (x > 0) < a = a+1; if (x%2 == 0) < b = b + x%10; >x = x / 10; > cout алг нач цел x, a, b ввод x a := 0; b := 0 нц пока x > 0 a := a+1 если mod(x,2)=0 то b := b + mod(x,10) все x := div(x,10) кц вывод a, нс, b кон Python x = int(input()) a=0; b=0 while x>0: a = a+1 if x%2==0: b += x%10 x = x//10 print(a, b) Ответ: ___________________________. 20

Вариант 2 35 Напишите в ответе наименьшее значение входной переменной k, при котором программа выдаёт ответ 10. Для Вашего удобства программа приведена на пяти языках программирования. Бейсик С++ DIM K, I AS LONG INPUT K I = 1 WHILE F(I) < K I = I + 1 WEND PRINT I FUNCTION F(N) F = N * N END FUNCTION #include using namespace std; long f(long n) < return n * n; >int main() < long k, i; cin >> k; i = 1; while (f(i) < k) i++; cout Алгоритмический язык Паскаль алг нач цел k, i ввод k i := 1 нц пока f(i) < k i := i + 1 кц вывод i кон алг цел f(цел n) нач знач := n * n кон var k, i : longint; function f(n: longint): longint; begin f := n * n; end; begin readln(k); i := 1; while f(i) < k do i := i+1; writeln(i) end. Python def f(n): return n*n k = int(input()) i = 1 while f(i) < k: i += 1 print (i) Ответ: ___________________________. 21

Вариант 2 36 Исполнитель Тренер преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя Тренер – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 12? Ответ: ___________________________. Сколько существует различных наборов значений логических переменных x1, x2, . x9, y1, y2, . y9, которые удовлетворяют всем перечисленным ниже условиям? (x1→x2) /\ (y1→y2) = 1 (x2→x3) /\ (y2→y3) = 1 … (x8→x9) /\ (y8→y9) = 1 В ответе не нужно перечислять все различные наборы значений переменных x1, x2, . x9, y1, y2, . y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов. Ответ: ___________________________. 22 23

Вариант 2 37 Часть 2 Для записи ответов на задания этой части (24–27) используйте отдельный лист. Запишите сначала номер задания (24, 25 и т. д.), а затем – полное решение. Ответы записывайте чётко и разборчиво. Даны целые числа A и B, 0 ≤ B ≤ A. Последовательно вычисляются значения A – 1, A – 1 – 2, A – 1 – 2 – 3 и т. д. Необходимо вывести наибольшее из этих значений, которое меньше B. Для решения этой задачи ученик написал программу, но, к сожалению, его программа неправильная. Ниже эта программа для Вашего удобства приведена на пяти языках программирования. Паскаль Python var a, b, s, k: integer; begin read(a,b); if not ((0 <=b) and (b<=a)) then writeln('Неверные данные') else begin s := a; k := 0; while s >b do begin s := s-k; k := k+1; end; writeln(k) end end. a = int(input()) b = int(input()) if not 0 b: s = s-k k = k+1 print(k) Алгоритмический язык Бейсик алг нач цел a, b, s, k ввод a, b если не 0 b s := s-k k := k+1 кц вывод k все кон DIM A,B,S,K AS INTEGER INPUT A, B IF NOT (0 B S = S — K K = K + 1 WEND PRINT K END IF END 24

Вариант 2 38 С++ #include using namespace std; int main()< int a, b, s, k; cin >> a >> b; if (!(0 b) < s = s-k; k = k+1; >cout return 0; > Последовательно выполните следующее. 1. Напишите, что выведет эта программа при вводе чисел 6 и 2. 2. Приведите пример таких значений A и B, при вводе которых программа выведет правильный числовой ответ. 3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде. Достаточно указать ошибки и способ их исправления для одного языка программирования. Обратите внимание: Вам нужно исправить приведённую программу, а не написать свою. Вы можете только заменять ошибочные строки, но не можете удалять строки или добавлять новые. Заменять следует только ошибочные строки: за исправления, внесённые в строки, не содержащие ошибок, баллы будут снижаться Дан массив, содержащий 2018 положительных целых чисел, меньших 10 000. Необходимо найти и вывести минимальный из тех элементов этого массива, десятичная и шестнадцатеричная запись которых заканчивается одним и тем же символом. Если таких чисел в массиве нет, ответ считается равным 10000. Например, для массива из четырёх элементов, равных 80, 91, 162 и 250, в ответе должно получиться 80. В шестнадцатеричном виде эти числа записываются как 50, 5B, A2 и FA. Последний символ в десятичной и шестнадцатеричной записи совпадает у первого и третьего чисел, меньшее из них – первое, то есть 80. 25

Вариант 2 39 Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных. Бейсик Python CONST N=2018 DIM A(N) AS INTEGER DIM I, M, K AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I … END # допускается также использо- # вание целочисленных # переменных m, k a = [] N = 2018 for i in range(0, N): a.append(int(input())) … Алгоритмический язык Паскаль алг нач цел N=2018 целтаб a[1:N] цел i, m, k нц для i от 1 до N ввод a[i] кц … кон const N=2018; var a: array [1..N] of integer; i, m, k: integer; begin for i:=1 to N do readln(a[i]); … end. С++ #include using namespace std; const int N = 2018; int main()< int a[N]; int i, m, k; for (i=0; i> a[i]; … return 0; > В качестве ответа необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и версию языка программирования, например Free Pascal 2.6). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии.

Вариант 2 40 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 37. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 37 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 36. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника. Выполните следующие задания. Во всех случаях обосновывайте свой ответ. Задание 1. У кого из игроков есть выигрышная стратегия при S = 12? Опишите эту стратегию. Задание 2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого из указанных значений S опишите выигрышную стратегию Пети. Задание 3. Укажите значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, однако у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте в виде рисунка или таблицы дерево всех партий, возможных при этой выигрышной стратегии Вани. На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции. 26

Вариант 2 41 Дан набор из N целых положительных чисел. Для каждого числа вычисляется сумма двух последних цифр в его десятичной записи (для однозначных чисел предпоследняя цифра считается равной нулю). Необходимо определить, какая сумма при этом получается реже всего (но не менее одного раза). Если таких сумм несколько, необходимо вывести наименьшую из них. Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N. Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла. Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла. Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бóльшая из двух оценок. Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Пример входных данных: 5 14 417 123 3 4841 Пример выходных данных для приведённого выше примера входных данных: 3 Суммы двух последних цифр для чисел из данного набора равны 5, 8, 5, 3, 5. Реже других (по одному разу) встречаются 8 и 3, в ответе выводится меньшая из этих сумм. 27

42 Вариант 3 Часть 1 Ответами к заданиям 1–23 являются число, последовательность букв или цифр. Запишите ответы в указанном месте без пробелов, запятых и других дополнительных символов. Сколько нулей в двоичной записи десятичного числа 1021? Ответ: ___________________________. Логическая функция F задаётся выражением (x \/ y) → (y ≡ z). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z. Переменная 1 Переменная 2 Переменная 3 Функция . . . F 0 0 0 0 0 В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x → y, зависящее от двух переменных, x и y, и фрагмент таблицы истинности: Переменная 1 Переменная 2 Функция . . F 0 1 0 Тогда первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе нужно написать yx. Ответ: ___________________________. 1 2

Вариант 3 43 На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. П1 П2 П3 П4 П5 П6 П7 П1 3 7 4 П2 15 2 П3 3 6 П4 6 8 12 П5 7 15 8 9 П6 4 9 П7 2 12 Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта А в пункт Д, если передвигаться можно только по указанным дорогам. В ответе укажите целое число – длину дороги в километрах. Ответ: ___________________________. 3 Б В Г Д Е К А

Вариант 3 44 Даны фрагменты двух таблиц из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. На основании приведённых данных определите, у скольких детей в момент рождения матерям было больше 35 полных лет. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц. Таблица 1 Таблица 2 ID Фамилия_И.О. Пол Год рождения ID_Родителя ID_Ребёнка 866 Кравец Д.К. Ж 1942 866 911 867 Тошич Б.Ф. М 1938 866 938 879 Гонтарь В.А. Ж 1998 867 911 885 Крон К.Г. М 1990 867 938 900 Кислюк Л.А. Ж 2012 911 879 904 Петраш А.И. М 1981 911 1041 911 Тошич А.Б. Ж 1971 1026 900 932 Петраш П.А. Ж 2016 938 995 938 Тошич И.Б. М 1974 938 1017 949 Седых Г.Р. Ж 1966 949 995 970 Кислюк А.П. М 1968 949 1017 995 Тошич Т.И. Ж 2004 970 879 1017 Тошич П.И. М 2003 970 1041 1026 Мухина Р.Г. Ж 1983 1026 932 1041 Сайко М.А. Ж 2010 904 900 1056 Кислюк П.А. М 1989 904 932 … … … … … Ответ: ___________________________. По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Буква Кодовое слово Буква Кодовое слово А 11 И Б 0010 М 01 Г 1011 Р 000 Е 0011 Т 1010 Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Ответ: ___________________________. 4 5

Вариант 3 45 Автомат получает на вход четырёхзначное число (число не может начинаться с нуля). По этому числу строится новое число по следующим правилам. 1. Складываются отдельно первая и вторая, вторая и третья, третья и четвёртая цифры заданного числа. 2. Наименьшая из полученных трёх сумм удаляется. 3. Оставшиеся две суммы записываются друг за другом в порядке неубывания без разделителей. Пример. Исходное число: 1984. Суммы: 1 + 9 = 10, 9 + 8 = 17, 8 + 4 = 12. Удаляется 10. Результат: 1217. Укажите наименьшее число, при обработке которого автомат выдаёт результат 613. Ответ: ___________________________. В ячейки электронной таблицы записаны числа, как показано на рисунке: A B C D E F 1 10 20 30 40 2 1 11 21 31 41 3 2 12 22 32 42 4 3 13 23 33 43 5 4 14 24 34 44 6 5 15 25 35 45 В ячейку A5 записали формулу = $C6 + E$3. После этого ячейку A5 скопировали в ячейку B1. Какое число будет показано в ячейке B1? Примечание. Знак $ обозначает абсолютную адресацию. Ответ: ___________________________. Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования. Бейсик Python DIM S, N AS INTEGER S = 25 N = 0 WHILE S < S*S S = S - 1 N = N + 2 WEND PRINT N s = 25 n = 0 while s < s*s: s = s - 1 n = n + 2 print(n) 6 7 8

Вариант 3 46 Алгоритмический язык Паскаль алг нач цел s, n s := 25 n := 0 нц пока s < s*s s := s - 1 n := n + 2 кц вывод n кон var s, n: integer; begin s := 25; n := 0; while s < s*s do begin s := s - 1; n := n + 2 end; writeln(n) end. C++ #include using namespace std; int main() < int s = 25, n = 0; while (s < s*s) < s = s - 1; n = n + 2; >cout Ответ: ___________________________. Автоматическая фотокамера производит растровые изображения размером 800 х 600 пикселей. При этом объём файла с изображением не может превышать 600 Кбайт, упаковка данных не производится. Какое максимальное количество цветов можно использовать в палитре? Ответ: ___________________________. 9

Вариант 3 47 Все трёхбуквенные слова, составленные из букв П, А, Р, У, С, записаны в алфавитном порядке и пронумерованы, начиная с 1. Начало списка выглядит так: 1. ААА 2. ААП 3. ААР 4. ААС 5. ААУ 6. АПА … Под каким номером в списке идёт первое слово, которое начинается с буквы Р? Ответ: ___________________________. Ниже на пяти языках программирования записана рекурсивная функция F. Бейсик Паскаль FUNCTION F(n) IF n > 2 THEN F = F(n-2) + F(n\2) ELSE F = n END IF END FUNCTION function F(n: integer): integer; begin if n > 2 then F := F(n-2) + F(n div 2) else F := n end; C++ Python int F(int n) < if (n >2) return F(n-2) + F(n/2); else return n; > def F(n): if n > 2: return F(n-2) + F(n//2) else: return n Алгоритмический язык алг цел F(цел n) нач если n > 2 то знач := F(n-2) + F(div(n,2)) иначе знач := n все кон Чему будет равно значение, вычисленное при выполнении вызова F(9)? Ответ: ___________________________. 10 11

Вариант 3 48 В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места – нули. Обычно маска записывается по тем же правилам, что и IP-адрес – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0. Для узла с IP-адресом 93.138.161.49 адрес сети равен 93.138.160.0. Какое наименьшее количество нулей может быть в двоичной записи маски? Ответ: ___________________________. При регистрации в компьютерной системе для каждого пользователя формируется индивидуальный идентификатор, состоящий из 14 символов. Для построения идентификатора используют только латинские буквы (26 заглавных и 26 строчных букв). В базе данных для хранения сведений о каждом пользователе отведено одинаковое минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым минимально возможным количеством бит. Кроме идентификатора для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено 19 байт на каждого пользователя. Сколько байт нужно для хранения сведений о 25 пользователях? В ответе запишите только целое число – количество байт. Ответ: ___________________________. 12 13

Вариант 3 49 Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется. Цикл ПОКА условие последовательность команд КОНЕЦ ПОКА выполняется, пока условие истинно. В конструкции ЕСЛИ условие ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ выполняется команда1 (если условие истинно) или команда2 (если условие ложно). Часть ИНАЧЕ может отсутствовать, в этом случае, если условие ложно, никакие действия не выполняются. Какая строка получится в результате применения приведённой ниже программы к строке вида 1…12…2 (8 единиц, затем 8 двоек)? В ответе запишите полученную строку. НАЧАЛО ПОКА нашлось (111) ИЛИ нашлось (222) ЕСЛИ нашлось (111) ТО заменить (111, 2) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (222) ТО заменить (222, 1) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Ответ: ___________________________. 14

Первое ЕГЭ-задание по информатике: Сколько единиц в двоичной записи шестнадцатеричного числа 10FA16?

Если переводить в двоичную систему с помощью ТЕТРАД, то получается 7 единиц, и это правильный ответ. А вот если перевести это число сначала в десятичную, а потом в двоичную, а конкретнее- делить на два и считать сколько единиц будет в остатках. Единиц будет 11. Второй способ мне кажется логичным, хоть и медленным, но почему-то не сходиться с ответом. Объясните почему.

Дополнен 7 лет назад

Забыл в скобки взять число 16.Думаю, вы поняли.

Лучший ответ

0b1000011111010 Никаких тетрадов я не знаю, перевод hex->bin производится очень просто — по разрядам. С этим переводом приходится иметь дело постоянно: при написании программ для микроконтроллеров десятичная система вообще нужна крайне редко. А почему способ лечить зуб через ж.. (еще и приводящий к ошибке) может казаться более логичным — мне не понять никогда.

Остальные ответы

Похожие вопросы