ЕГЭ по информатике 28.05.2018. Основная волна, вариант А. Имаева — «Котолис».
При выполнении заданий с кратким ответом впишите в поле для ответа цифру, которая соответствует номеру правильного ответа, или число, слово, последовательность букв (слов) или цифр. Ответ следует записывать без пробелов и каких-либо дополнительных символов. Дробную часть отделяйте от целой десятичной запятой. Единицы измерений писать не нужно.
Если вариант задан учителем, вы можете вписать или загрузить в систему ответы к заданиям с развернутым ответом. Учитель увидит результаты выполнения заданий с кратким ответом и сможет оценить загруженные ответы к заданиям с развернутым ответом. Выставленные учителем баллы отобразятся в вашей статистике.
Версия для печати и копирования в MS Word
Вычислите значение выражения 8E16 − 8B16.
В ответе запишите вычисленное значение в десятичной системе счисления.
Ответ:
Логическая функция F задаётся выражением (x ∧ ¬y) ∨ (y ≡ z ) ∨ w.
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| ??? | ??? | ??? | ??? | F |
| 1 | 0 | |||
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
| Переменная 1 | Переменная 1 | Функция |
|---|---|---|
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Ответ:
На рисунке схема дорог изображена в виде графа, в таблице звёздочкой обозначено наличие дороги между населёнными пунктами. Отсутствие звёздочки означает, что такой дороги нет.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | * | * | |||||
| П2 | * | * | * | ||||
| П3 | * | * | |||||
| П4 | * | * | * | ||||
| П5 | * | * | |||||
| П6 | * | * | * | ||||
| П7 | * | * | * |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какие номера населённых пунктов соответствуют населённым пунктам Б и В. В ответе запишите эти два номера в порядке возрастания без пробелов и знаков препинания.
Пример. Пусть населённым пунктам Д и Е соответствуют номера П1 и П2. Тогда в ответе нужно написать «12».
Ответ:
Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных, сколько жителей родились в том же городе, что и их внук или внучка. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.
|
|
Ответ:
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 0, Б — 1011. Укажите сумму длин кратчайших кодовых слов для
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Ответ:
Автомат обрабатывает натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу: если
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа — результата работы данного алгоритма.
Укажите максимальное число R, которое не
Ответ:
Дан фрагмент электронной таблицы. Из ячейки C3 в ячейку D2 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке D2?
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | 40 | 5 | 400 | 4 | 4 |
| 2 | 30 | 6 | 40 | 3 | |
| 3 | 20 | 8 | =$B$4+C2 | 30 | 2 |
| 4 | 10 | 400 | 100 | 40 | 15 |
Примечание: знак $ обозначает абсолютную адресацию.
Ответ:
Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования.
| Бейсик | Python |
|---|---|
DIM S, N AS INTEGER S = 80 N = 0 WHILE S + N < 150 S = S − 5 N = N + 15 WEND PRINT N
| s = 80 n = 0 while s + n < 150: s = s − 5 n = n + 15 print(n)
|
| Паскаль | Алгоритмический язык |
var s, n: integer; begin s := 80; n := 0; while s + n < 150 do begin s := s − 5; n := n + 15; end; writeln(n) end. | алг нач цел s, n s := 80 n := 0 нц пока s + n < 150 s := s − 5 n := n + 15 кц вывод n кон |
| Си++ | |
#include <iostream> using namespace std; int main() { int s = 80, n = 0; while (s + n < 150) { s = s − 5; n = n + 15; } cout << n; return 0; }
| |
Ответ:
Автоматическая фотокамера производит растровые изображения размером
Ответ:
Все шестибуквенные слова, составленные из букв К, Л, Н, Т, Э, записаны в алфавитном порядке и пронумерованы, начиная с 1. Начало списка выглядит так:
1. КККККК
2. КККККЛ
3. КККККН
4. КККККТ
5. КККККЭ
...
Под каким номером в списке идёт
Ответ:
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
| Бейсик | Python |
|---|---|
SUB F(n) IF n > 2 THEN PRINT N F(n \ 2) F(n − 1) END IF END SUB
| def F(n): if n > 2: print(n) F(n // 2) F(n − 1)
|
| Паскаль | Алгоритмический язык |
procedure F(n: integer); begin if n > 2 then begin write(n); F(n div 2); F(n − 1); end end;
| алг F(цел n) нач если n > 2 то вывод n F(div(n,2)) F(n − 1) все кон
|
| С++ | |
void F (int n) { if (n > 2) { std::cout << n; F (n / 2); F (n − 1); } }
| |
Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(7). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Ответ:
В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места — нули. Обычно маска записывается по тем же правилам, что и IP-адрес, — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.
Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.
Для узла с IP-адресом 111.81.88.168 адрес сети равен 111.81.88.160. Найдите наименьшее значение последнего байта маски. В ответ запишите наименьшее значение последнего байта маски в десятичном виде.
Ответ:
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из
Ответ:
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение
Если в строке нет вхождений
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из
НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
ЕСЛИ нашлось (11111)
ТО заменить (11111, 88)
ИНАЧЕ
ЕСЛИ нашлось (888)
ТО заменить (888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Ответ:
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Л?
Ответ:
Значение выражения
Сколько
Ответ:
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» – символ «&».
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
| Запрос | Найдено страниц (в тысячах) |
|---|---|
| Поле | 90 |
| Пшеница | 83 |
| Солнце | 62 |
| Поле | Солнце | 142 |
| Пшеница & Поле | 20 |
| Пшеница & Солнце | 0 |
Какое количество страниц (в тысячах) будет найдено по запросу Поле | Пшеница | Солнце?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Ответ:
Для какого наибольшего целого неотрицательного
тождественно истинно, то есть принимает
Ответ:
Представленный ниже на пяти языках программирования фрагмент программы обрабатывает элементы одномерного целочисленного массива A с индексами от 0 до 9. Перед началом выполнения данного фрагмента эти элементы массива имели значения 2, 3, 5, 3, 7, 8, 4, 2, 5, 1 (т. е. A[0] = 2, A[1] = 3, …, A[9] = 1). Определите значение переменной b после выполнения фрагмента.
| Бейсик | Python |
|---|---|
b = 0 FOR i = 1 TO 9 IF A(i-1) < A(i) THEN t = A(i) A(i) = A(i-1) A(i-1) = t b = b + 1 END IF NEXT i
| b = 0 for i in range(1,10): if A[i-1] < A[i]: t = A[i] A[i] = A[i-1] A[i-1] = t b = b + 1
|
| Паскаль | Алгоритмический язык |
b := 0; for i:=1 to 9 do begin if A[i-1] < A[i] then begin t := A[i]; A[i] := A[i-1]; A[i-1] := t; b := b + 1 end end;
| b := 0 нц для i от 1 до 9 если A[i-1] < A[i] то t := A[i] A[i] := A[i-1] A[i-1] := t b := b + 1 все кц |
| С++ | |
b = 0; for (i = 1; i <= 9; ++i) { if (A[i-1] < A[i]) { t = A[i]; A[i] = A[i-1]; A[i-1] = t; b = b + 1; } } | |
Ответ:
Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа L и M. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 25, а потом 3.
| Бейсик | Python |
|---|---|
DIM X, L, M AS INTEGER INPUT X L = 0: M = 1 WHILE X > 0 L = L + 1 IF X MOD 2 > 0 THEN M = M * (X MOD 8) END IF X = X \ 8 WEND PRINT M PRINT L
| x = int(input()) l=0 m=1 while x > 0: l += 1 if x%2 > 0: m *= x%8 x = x//8 print(m, l)
|
| Паскаль | Алгоритмический язык |
var x, L, M: longint; begin readln(x); L := 0; M := 1; while x > 0 do begin L := L+ 1; if x mod 2 <> 0 then M := M * (x mod 8); x := x div 8; end; writeln(M); write(L); end.
| алг нач цел x, L, M ввод x L := 0; M := 1 нц пока x > 0 L := L + 1; если mod(x,2)<>0 то M := M * mod(x,8) все x := div(x,8) кц вывод M, нс, L кон
|
| С++ | |
#include <iostream> using namespace std; int main() { int x, L, M; cin >> x; L = 0; M = 1; while (x > 0) { L++; if (x%2 > 0) M *= x%8; x = x / 8; } cout << M << endl << L << endl; return 0; }
| |
Ответ:
Какое число будет напечатано в результате работы следующей программы? Для Вашего удобства программа приведена на пяти языках программирования.
| Бейсик | Python |
|---|---|
DIM A, B, T, M, R AS INTEGER A = −20: B = 20 M = A : R = F(A) FOR T = A TO B IF F(T) <= R THEN M = T R = F(T) END IF NEXT T PRINT M+R
FUNCTION F(x) F=abs(abs(x−6)+abs(x+6)−16)+2 END FUNCTION
| def F(x): return(abs(abs(x−6)+abs(x+6)−16)+2)
a = −20 b = 20 M = a R = F(a) for t in range(a,b+1): if F(t) <= R: M = t R = F(t) print(M+R)
|
| Паскаль | Алгоритмический язык |
var a, b, t, M, R: integer;
function F(x: integer): integer; begin f:=abs(abs(x−6)+abs(x+6)−16)+2; end;
begin a := −20; b := 20; M := a; R:= F(a) for t := a to b do begin if F(t) <= R then begin M := t; R := F(t); end; end; write(M+R); end.
| алг нач цел a, b, t, M, R a := −20; b := 20 M := a; R := F(a) нц для t от a до b если F(t) <= R то M := t; R := F(t) все кц вывод M + R кон
алг цел f(цел x) нач знач:=abs(abs(x−6)+abs(x+6)−16)+2 кон
|
| С++ | |
#include <iostream> using namespace std; long f(int x) { return (abs(abs(x−6)+abs(x+6)−16)+2); }
int main() { int a, b, t, M, R; a = −20; b = 20; M = a; R = F(a); for (t = a; t <=b; ++t) { if (F(t) <= R) { M = t; R = F(t); } } cout << M + R; return 0; }
| |
Ответ:
Исполнитель Вычислитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера.
1. Прибавить 2.
2. Умножить на 2.
3. Прибавить 3.
Первая команда увеличивает число на экране
Программа для исполнителя Вычислитель — это последовательность команд.
Сколько существует программ, которые преобразуют исходное
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном
Ответ:
Сколько существует различных наборов значений логических переменных x1, x2,…, x9, y1, y2, ..., y9, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∨ y1)≡¬(x2 ∨ y2) = 1
(x2 ∨ y2)≡¬(x3 ∨ y3) = 1
...
(x8 ∨ y8)≡¬(x9 ∨ y9) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ..., x9, y1, y2, ..., y9 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Ответ:
Дано натуральное число N (1 ≤ N ≤ 109). Необходимо найти и вывести наименьшую нечётную цифру в десятичной записи N или вывести сообщение «NO», если таких цифр нет.
Для решения этой задачи ученик написал программу, но, к сожалению, его программа неправильная.
Ниже эта программа для Вашего удобства приведена на пяти языках программирования.
| Бейсик | Python |
|---|---|
DIM N, DIGIT, MINDIGIT AS INTEGER INPUT N MINDIGIT = N MOD 10 WHILE N > 0 DIGIT = N MOD 10 IF DIGIT MOD 2 <> 0 THEN IF DIGIT < MINDIGIT THEN DIGIT = MINDIGIT END IF END IF N = N \ 10 WEND IF MINDIGIT <= 9 THEN PRINT MINDIGIT ELSE PRINT "NO" END IF END
| n = int(input()) mindigit = n%10 while n > 0: digit = n % 10 if digit%2 != 0: if digit < mindigit: digit = mindigit n = n // 10 if mindigit <= 9: print(mindigit) else: print("NO")
|
| Паскаль | Алгоритмический язык |
var n, digit, mindigit: integer; begin read(n); mindigit := n mod 10; while N > 0 do begin digit := n mod 10; if (digit mod 2 <> 0) then if digit < mindigit then digit := mindigit; n := n div 10; end; if mindigit <= 9 then writeln(mindigit) else writeln('No') end.
| алг нач цел n, digit, mindigit ввод n mindigit := mod(n,10) нц пока n > 0 digit := mod(n,10) если mod(digit,2)<>0 то если digit < mindigit то digit = mindigit все все n := div(n,10) кц если mindigit <= 9 то вывод mindigit иначе вывод "NO" все кон |
| С++ | |
#include <iostream> using namespace std; int main(){ int n, digit, mindigit; cin >> n; mindigit = n%10; while (n > 0) { digit = n%10; if (digit%2 != 0) if (digit < mindigit) digit = mindigit; n = n / 10; } if (mindigit <= 9) cout << mindigit; else cout << "NO"; return 0; }
| |
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе N = 134.
2. Приведите пример числа N, при вводе которого программа выведет правильный ответ.
3. Найдите в программе все ошибки (известно, что их не более двух). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.
Достаточно указать ошибки и способ их исправления для одного языка программирования.
Обратите внимание: Вам нужно исправить приведённую программу, а не написать свою. Вы можете только заменять ошибочные строки, но не можете удалять строки или добавлять новые. Заменять следует только ошибочные строки: за исправления, внесённые в строки, не содержащие ошибок, баллы будут снижаться.
На следующей странице вам будет предложено проверить их самостоятельно.
Дан массив, содержащий 30 целых чисел, элементы массива могут принимать значения от −10 000 до 10 000 включительно. Необходимо найти минимальный элемент массива кратный 5, а затем заменить каждый элемент массива кратный 5 на найденный минимальный элемент. Гарантируется, что хотя бы один элемент кратный 5 в массиве есть.
Напишите на одном из языков программирования программу для решения этой задачи. В качестве результата программа должна вывести изменённый массив, по одному элементу в строке. Например, для исходного массива из 6 элементов 204 115 27 20 305 4 программа должна вывести числа 204 20 27 20 20 4 по одному числу в строке (все элементы кратные 5 были приравнены минимальному из них).
Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных.
| Бейсик | Python |
|---|---|
CONST N=30 DIM A(1 TO N) AS LONG DIM I, J, K AS LONG FOR I = 1 TO N INPUT A(I) NEXT I … END
| # кроме уже указанных # допускается использование # целочисленных переменных # j, k a = [] n = 30 for i in range(0, n): a.append(int(input())) …
|
| Паскаль | Алгоритмический язык |
const N=30; var a: array [1..N] of longint; i, j, k: longint; begin for i:=1 to N do readln(a[i]); … end.
| алг нач цел N=30 целтаб a[1:N] цел i, j, k нц для i от 1 до N ввод a[i] кц … кон |
| С++ | |
#include <iostream> using namespace std; const int N=30; int main(){ int a[N]; int i, j, k; for (i=0; i<N; ++i) cin >> a[i]; … return 0; }
| |
В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.6). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии.
На следующей странице вам будет предложено проверить их самостоятельно.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
добавить в кучу два камня или
увеличить количество камней в куче в два раза.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 80. Победителем считается игрок, сделавший последний ход, то есть первым получивший суммарно в обеих кучах 80 или более камней.
В начальный момент в первой куче было 7 камней, а во второй S камней, 1 ≤ S ≤ 72.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы следующего стратегии игрока, которые не являются для него безусловно выигрышными.
Выполните следующие задания.
Задание 1.
а) Назовите все значения S, при которых Петя может выиграть первым ходом, причём у Пети есть ровно один выигрывающий ход.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2.
Укажите значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
—Петя не может выиграть за один ход.
—Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для каждого указанного значения S опишите выигрышную стратегию Пети.
Задание 3.
Укажите такое значение S, при котором одновременно выполняются два условия:
—у Вани есть выигрышная стратегия, позволяющая ему выиграть своим первым или вторым ходом при любой игре Пети.
—у Вани нет стратегии, которая позволит ему гарантированно выиграть своим первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в позиции.
Дерево не должно содержать партий, невозможных при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не будет верным ответом на это задание.
На следующей странице вам будет предложено проверить их самостоятельно.
Дан набор из N ≤ 1000 натуральных чисел, каждое из которых не превышает 10000. Из них необходимо определить, сколько имеется пар чисел, разница между индексами которых не меньше 5, а произведение элементов в которых кратно 13. Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Описание входных и выходных данных.
В первой строке входных данных задаётся количество чисел N (5 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.
Пример входных данных:
7
4
14
27
39
7
2
13
Пример выходных данных для приведённого выше примера входных данных:
2
Из 7 чисел можно составить 14 пар. В данном случае условиям удовлетворяют две пары: (4, 13) и (14, 13). Произведения (52 и 182) делятся на 13, а номера элементов в паре отличаются не менее, чем на 5. У всех остальных пар как минимум одно из этих условий не выполняется. На экран выводится количество пар — 2.
На следующей странице вам будет предложено проверить их самостоятельно.