Задание 2. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Логическая функция F задаётся выражением ¬x ∨ y ∨ (¬z ∧ w).
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.

Перем. 1	Перем. 2	Перем. 3	Перем. 4	Функция
???	???	???	???	F
1	0	0	0	0
1	1	0	0	0
1	1	1	0	0

В ответе напишите буквы w , x , y , z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Задание 3. Демоверсия ЕГЭ 2018 информатика (ФИПИ):
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт Г . В ответе запишите целое число – так, как оно указано в таблице.

4 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):
Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных, у скольких детей на момент их рождения матерям было больше 22 полных лет. При вычислении ответа учитывайте только информацию из
приведённых фрагментов таблиц.

5 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Укажите кратчайшее кодовое слово для буквы Б , при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

6 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):
На вход алгоритма подаётся натуральное число N . Алгоритм строит по нему новое число R следующим образом.

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

2. К этой записи дописываются справа ещё два разряда по следующему правилу:

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

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

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

7 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):
Дан фрагмент электронной таблицы. Из ячейки B3 в ячейку A4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке A4 ?

Примечание: знак $ обозначает абсолютную адресацию.

8 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования.

1 2 3 4 5 6 7 8 9 10 11

var s, n: integer ; begin s : = 260 ; n : = 0 ; while s > 0 do begin s : = s - 15 ; n : = n + 2 end ; writeln (n) end .

var s, n: integer; begin s:= 260; n:= 0; while s > 0 do begin s:= s - 15; n:= n + 2 end; writeln(n) end.

9 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Автоматическая фотокамера производит растровые изображения размером 640 ×480 пикселей. При этом объём файла с изображением не может превышать 320 Кбайт, упаковка данных не производится. Какое максимальное количество цветов можно использовать в палитре?

10 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Все 4-буквенные слова, составленные из букв Д , Е , К , О , Р , записаны в алфавитном порядке и пронумерованы, начиная с 1 .
Ниже приведено начало списка.

1. ДДДД 2. ДДДЕ 3. ДДДК 4. ДДДО 5. ДДДР 6. ДДЕД …

Под каким номером в списке идёт первое слово, которое начинается с буквы K ?

11 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Ниже на пяти языках программирования записан рекурсивный алгоритм F .
Паскаль:

1 2 3 4 5 6 7 8 9

procedure F(n: integer ) ; begin if n > 0 then begin write (n) ; F(n - 3 ) ; F(n div 3 ) end end ;

procedure F(n: integer); begin if n > 0 then begin write(n); F(n - 3); F(n div 3) end end;

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9) . Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

12 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда – нули.
Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-адресом 57.179.208.27 адрес сети равен 57.179.192.0 . Каково наибольшее возможное количество единиц в разрядах маски?

13 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт . При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит.

Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях. В ответе запишите только целое число – количество байт.

14 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b) , где a, b – целые числа . Эта команда перемещает Чертёжника из точки с координатами (x,y) в точку с координатами (x + a, y + b).

Чертёжнику был дан для исполнения следующий алгоритм (число повторений и величины смещения в первой из повторяемых команд неизвестны):

НАЧАЛО сместиться на (4, 6) ПОВТОРИ … РАЗ сместиться на (…, …) сместиться на (4, -6) КОНЕЦ ПОВТОРИ сместиться на (-28, -22) КОНЕЦ

В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку . Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?

15 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М , проходящих через город Ж ?

16 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Значение арифметического выражения: 49 10 + 7 30 – 49 – записали в системе счисления с основанием 7 . Сколько цифр «6 » содержится в этой записи?

17 задание. Демо ЕГЭ 2018 информатика (ФИПИ):

В языке запросов поискового сервера для обозначения логической операции «ИЛИ » используется символ «| », а для обозначения логической операции «И » – символ «& ».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос	Найдено страниц (в сотнях тысяч)
Бабочка	22
Гусеница	40
Трактор	24
Трактор \| Бабочка \| Гусеница	66
Трактор & Гусеница	12
Трактор & Бабочка	0

Какое количество страниц (в сотнях тысяч) будет найдено по запросу Бабочка & Гусеница ?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

18 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Для какого наибольшего целого числа А формула

тождественно истинна , то есть принимает значение 1 при любых целых неотрицательных x и y ?

19 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

В программе используется одномерный целочисленный массив A с индексами от 0 до 9 . Значения элементов равны 3, 0, 4, 6, 5, 1, 8, 2, 9, 7 соответственно, т.е. A = 3 , A = 0 и т.д.

Определите значение переменной c после выполнения следующего фрагмента этой программы:

1 2 3 4 5 6 7 8 9

c : = 0 ; for i : = 1 to 9 do if A[ i- 1 ] > A[ i] then begin c : = c + 1 ; t : = A[ i] ; A[ i] : = A[ i- 1 ] ; A[ i- 1 ] : = t; end ;

c:= 0; for i:= 1 to 9 do if A > A[i] then begin c:= c + 1; t:= A[i]; A[i] := A; A := t; end;

20 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Ниже на пяти языках программирования записан алгоритм. Получив на вход число x , этот алгоритм печатает два числа: L и M . Укажите наименьшее число x , при вводе которого алгоритм печатает сначала 5 , а потом 7 .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

var x, L, M: integer ; begin readln (x) ; L : = 0 ; M : = 0 ; while x>0 do begin M : = M + 1 ; if x mod 2 <> 0 then L : = L + 1 ; x : = x div 2 ; end ; writeln (L) ; writeln (M) ; end .

var x, L, M: integer; begin readln(x); L:= 0; M:= 0; while x>0 do begin M:= M + 1; if x mod 2 <> 0 then L:= L + 1; x:= x div 2; end; writeln(L); writeln(M); end.

21 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

Напишите в ответе число, которое будет напечатано в результате выполнения следующего алгоритма.

Паскаль:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

var a, b, t, M, R : longint ; function F(x: longint ) : longint ; begin F: = 2 * (x* x- 1 ) * (x* x- 1 ) + 27 ; 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 .

var a, b, t, M, R:longint; function F(x: longint): longint; begin F:= 2*(x*x-1)*(x*x-1)+27; 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.

22 задание. Демо ЕГЭ 2018 информатика (ФИПИ):

Исполнитель М17 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3. Программа для исполнителя М17 – это последовательность команд.

Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10 ? Траектория должна содержать оба указанных числа.

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.

Решение 23 задания ЕГЭ по информатике демоверсия 2018 года ФИПИ:

Сколько существует различных наборов значений логических переменных x1 , x2 , … x7 , y1 , y2 , … y7 , которые удовлетворяют всем перечисленным ниже условиям?

(¬x1 ∨ y1) → (¬x2 ∧ y2) = 1
(¬x2 ∨ y2) → (¬x3 ∧ y3) = 1
…
(¬x6 ∨ y6) → (¬x7 ∧ y7) = 1

В качестве ответа Вам нужно указать количество таких наборов.

Решение 24 задания ЕГЭ по информатике демоверсия 2018 года ФИПИ:

На обработку поступает натуральное число, не превышающее 10 9 . Нужно написать программу, которая выводит на экран максимальную цифру числа, кратную 5 . Если в числе нет цифр, кратных 5 , требуется на экран вывести «NO» . Программист написал программу неправильно. Ниже эта программа для Вашего удобства приведена на пяти языках программирования.
Напоминание: 0 делится на любое натуральное число.
Паскаль:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

var N, digit, maxDigit: longint ; begin readln (N) ; maxDigit : = N mod 10 ; while N > 0 do begin digit : = N mod 10 ; if digit mod 5 = 0 then if digit > maxDigit then maxDigit : = digit; N : = N div 10 ; end ; if maxDigit = 0 then writeln ("NO" ) else writeln (maxDigit) end .

var N, digit, maxDigit: longint; begin readln(N); maxDigit:= N mod 10; while N > 0 do begin digit:= N mod 10; if digit mod 5 = 0 then if digit > maxDigit then maxDigit:= digit; N:= N div 10; end; if maxDigit = 0 then writeln("NO") else writeln(maxDigit) end.

Последовательно выполните следующее:
1. Напишите, что выведет эта программа при вводе числа 132 .
2. Приведите пример такого трёхзначного числа, при вводе которого
программа выдаёт верный ответ.
3. Найдите все ошибки в этой программе (их может быть одна или несколько). Известно, что каждая ошибка затрагивает только одну строку и может быть исправлена без изменения других строк. Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, т.е. приведите правильный вариант строки.
Достаточно указать ошибки и способ их исправления для одного языка программирования.

Решение 25 задания ЕГЭ по информатике Демоверсия 2018:

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10000 включительно. Опишите на одном из языков программирования алгоритм, который находит количество элементов массива, больших 100 и при этом кратных 5 , а затем заменяет каждый такой элемент на число, равное найденному количеству. Гарантируется, что хотя бы один такой элемент в массиве есть. В качестве результата необходимо вывести измененный массив, каждый элемент массива выводится с новой строчки.

Например, для массива из шести элементов: 4 115 7 195 25 106
программа должна вывести числа: 4 2 7 2 25 106

Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

Паскаль:

1 2 3 4 5 6 7 8 9 10

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 .

const N = 30; var a: array of longint; i, j, k: longint; begin for i:= 1 to N do readln(a[i]); ... end.

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.6). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии.

Разбор 26 задания демоверсии 2018 года (ФИПИ):
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза . Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 29 . Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28 .

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

Задание 1
а) Укажите такие значения числа S, при которых Петя может выиграть в один ход.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

Задание 2
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причем:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети.

Задание 3
Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах - количество камней в позиции

Дерево не должно содержать партий, невозможных при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.

Разбор 27 задания демоверсии 2018 года (ФИПИ):

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26 .

Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000) . В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000 .
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.

Пример входных данных:

4 2 6 13 39

Пример выходных данных для приведённого выше примера входных данных:

Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6 = 12 2·13 = 26 2·39 = 78 6·13 = 78 6·39 = 234 13·39 = 507

Из них на 26 делятся 4 произведения:

2·13=26; 2·39=78; 6·13=78; 6·39=234

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

-> демоверсия ЕГЭ 2018

Демонстрационные варианты ЕГЭ по информатике для 11 класса за 2004 - 2014 годы состояли из трех частей. Первая часть включала в себя задания, в которых нужно выбрать один из предложенных ответов. К заданиям из второй части требовалось дать краткий ответ. К заданиям из третьей части нужно было дать развернутый ответ.

В 2013 и 2014 годах в демонстрационные варианты ЕГЭ по информатике были внесены следующие изменения :

была во второй части работы.

В 2015 году в демонстрационном варианте по информатике была изменена и оптимизирована структура варианта в целом:

Вариант стал состоять из двух частей (часть 1 - задания с кратким ответом , часть 2 - ).

Нумерация заданий стала сквозной по всему варианту без буквенных обозначений А, В, С.

Была изменена форма записи ответа в заданиях с выбором ответа: ответ стало нужно записывать цифрой с номером правильного ответа (а не отмечать крестиком).

Было сокращено общее количество заданий (с 32 до 27) ; было уменьшено с 40 до 35 максимальное количество первичных баллов .

Уменьшение количества заданий произведено за счет укрупнения тематики заданий , сведения близких по тематике и сложности заданий в одну позицию. Такими укрупненными стали позиции: №3 (хранение информации в компьютере), №6 (формальное исполнение алгоритмов), №7 (технология вычислений и визуализации данных с помощью электронных таблиц) и №9 (скорость передачи звуковых и графических файлов) . В демонстрационном варианте 2015 года представлено несколько примеров каждого из заданий 3, 6, 7 и 9. В реальных вариантах на каждую из этих позиций было предложено только одно задание.

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

В демонстрационном варианте ЕГЭ по информатике 2016 года по сравнению с демонстрационным вариантом 2015 года по информатике существенных изменений нет: изменена лишь последовательность заданий 1-5.

В демонстрационном варианте ЕГЭ по информатике 2017 года по сравнению с демонстрационным вариантом 2016 года по информатике изменений не было .

В демонстрационный вариант ЕГЭ 2018 года по информатике по сравнению с демонстрационным вариантом 2017 года по информатике были внесены следующие изменения:

В задании 25 убрана возможность написания алгоритма на естественном языке ,

Примеры текстов программ и их фрагментов в условиях заданий 8, 11, 19, 20, 21, 24, 25 на языке Си заменены на примеры на языке С++ .

В демонстрационных вариантах ЕГЭ 2019-2020 годов по информатике по сравнению с демонстрационным вариантом 2018 года по информатике изменений не было .

Официальный сайт ФИПИ представил для ознакомления демонстрационные варианты (демоверсии) ЕГЭ 2020 года по всем предметам, в том числе и по информатике.

Подготовка к ЕГЭ по информатике включает несколько обязательных этапов. В первую очередь необходимо ознакомиться демоверсиями. Открытый банк заданий поможет вести всестороннюю подготовку по каждому заданию.

Структура КИМ ЕГЭ 2020 по информатике.

Каждый вариант экзаменационной работы состоит из двух частей и включает в себя 27 заданий, различающихся формой и уровнем сложности.

Часть 1 содержит 23 задания с кратким ответом. В экзаменационной работе предложены следующие разновидности заданий с кратким ответом:

– задания на вычисление определенной величины;

– задания на установление правильной последовательности, представленной в виде строки символов по определенному алгоритму.

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

Часть 2 содержит 4 задания с развернутым ответом.

В части 1 12 заданий относятся к базовому уровню, 10 заданий – к повышенному уровню сложности, 1 задание – к высокому уровню сложности.

Часть 2 содержит 4 задания, первое из которых повышенного уровня сложности, остальные 3 задания высокого уровня сложности. Задания этой части подразумевают запись развернутого ответа в произвольной форме.

Задания части 2 направлены на проверку сформированности важнейших умений записи и анализа алгоритмов. Эти умения проверяются на повышенном и высоком уровнях сложности. Также на высоком уровне сложности проверяются умения по теме «Технология программирования».

Изменения в КИМ ЕГЭ 2020 года по информатике сравнению с КИМ 2019 года отсутствуют.

Среднее общее образование

Информатика

Демоверсия ЕГЭ-2019 по информатике и ИКТ

Предлагаем вашему вниманию разбор демоверсии ЕГЭ 2019 года по информатике и ИКТ. Этот материал содержит пояснения и подробный алгоритм решения, а также рекомендации по использованию справочников и пособий, которые могут понадобиться при подготовке к ЕГЭ.

Скачать демоверсию ЕГЭ по информатике для выпускников 2019 года можно по ссылке ниже:

О нововведениях в экзаменационных вариантах по другим предметам читайте в .

Пособие содержит задания, максимально приближенные к реальным, используемым на ЕГЭ, но распределенные по темам в порядке их изучения в 10-11-х классах старшей школы. Работая с книгой, можно последовательно отработать каждую тему, устранить пробелы в знаниях, а также систематизировать изучаемый материал. Такая структура книги поможет эффективнее подготовиться к ЕГЭ.

Демо-КИМ ЕГЭ 2019 по информатике, не претерпел никаких изменений по своей структуре по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный (хочется на это рассчитывать) план подготовки к экзамену обучающегося.

В данной статье мы рассмотрим решение предлагаемого проекта (на момент написания статьи пока еще ПРОЕКТА) КИМ ЕГЭ по информатике.

Часть 1

Ответами к заданиям 1–23 являются число, последовательность букв или цифр, которые следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

Задание 1

Вычислите значение выражения 9E 16 – 94 16 .

В ответе запишите вычисленное значение в десятичной системе счисления.

Решение

Простая арифметика в шестнадцатеричной системе счисления:

Очевидно, что шестнадцатеричная цифра Е 16 соответствует десятеричному значению 14. Разность исходных чисел дает значение А 16 . Решение в принципе уже найдено. Следуя условию, представим найденное решение в десятеричной системе счисления. Имеем: А 16 = 10 10 .

Ответ: 10.

Задание 2

Миша заполнял таблицу истинности функции (¬x /\ ¬y) \/ (y≡z) \/ ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример . Если бы функция была задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имел бы вид

то первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать yx.

Ответ: ___________________________.

Решение

Давайте заметим, что функция (¬x /\ ¬y) \/ (y≡z) \/ ¬w, по сути, дизъюнкция трех «слагаемых»:

Вспоминаем таблицу истинности операции логического «сложения» (дизъюнкции): в сумме «истина», если хотя бы одно слагаемое «истина», и «ложь», если обе слагаемые «ложь». Значит, из условия задания делаем вывод о том, что каждое из слагаемых должно быть ложным. Третье слагаемое – (¬w) – оно должно быть ложным, что дает нам первую зацепку: четвертый столбец должен быть переменной w, поскольку, исходя из значений первого, второго и третьего столбцов, ни один из них не может быть переменной w.

Рассмотрим второе слагаемое функции – (y≡z), – оно также должно быть равно 0. Следовательно, необходимо, чтобы в наших столбцах переменных y и z были разные значения. С учетом первого слагаемого функции (¬x /\ ¬y), заметим, что переменной z соответствует первый столбец. Еще первое слагаемое указывает на то, что в пустых ячейках второго и третьего столбцов должны быть 1. Тут же, с учетом второго слагаемого, сделаем еще одно заключение о том, что пустая ячейка в первом столбце равно 1. Именно этот вывод позволяет нам сделать окончательное заключение о том, что второй столбец соответствует переменной y, и, соответственно, третий – переменной x.

Ответ: zyxw.

Задание 3

На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам B и C на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Ответ: ___________________________.

Решение

На схеме видно, что каждый из пунктов В и С соединен с тремя другими пунктами. Значит, нам необходимо в таблице найти те номера населенных пунктов, напротив которых по строкам (или по столбцам с учетом симметричности) три «звездочки». Этому условию соответствуют строки 2 и 6 (соответственно столбцы 2 и 6).

Ответ: 26.

Задание 4

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. На основании приведённых данных определите наибольшую разницу между годами рождения родных сестёр. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.

Ответ: ___________________________.

Решение

Первое, на что стоит обратить внимание и не запутаться – исключаем представителей мужского пола (точнее мы не берем их в расчет при подсчете детей-девочек): это строки 64, 67, 70, 75, 77, 86 Таблицы 1.

Проходя по полям таблиц, найдем пары детей-девочек:

Год рождения	Год рождения	Разница между годами рождения

В ответ заносим наибольшее из двух значений разницы между годами рождения.

Ответ: 6.

Задание 5

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

Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ: ___________________________.

Решение

Для решения поставленной задачи, построим граф:

Кодовое слово длины 2 – 11, или любое из кодовых слов длины 3, неизбежно станет началом одного из слов длины 4. Выбор длины 4 связан с тем, что была потребность в кодировании четырех букв. Полученные кодовые слова в совокупности дают длину 16.

Ответ: 16.

Задание 6

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

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

Например, двоичная запись 100 числа 4 будет преобразована в 10001, а двоичная запись 111 числа 7 будет преобразована в 11110.

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

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

Ответ: ___________________________.

Решение

Представим число 102 в двоичной форме: 1100110 2 . Нас интересует число, которое будет больше. Будем двигаться «вверх» добавляя по единичке:

1100111 2 – 103 10 – двоичное представление не соответствует алгоритму;

1101000 2 – 104 10 – двоичное представление не соответствует алгоритму;

1101001 2 – 105 10 – двоичное представление соответствует алгоритму.

Ответ: 105.

Задание 7

Дан фрагмент электронной таблицы. Из ячейки C3 в ячейку D4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке D4?

Примечание . Знак $ обозначает абсолютную адресацию.

Ответ: ___________________________.

Решение

При копировании формулы в ячейке D4 мы получаем: =$B$3+E3. Подставив значения получаем искомый результат:

400+700, т.е. 1100.

Ответ: 1100.

Задание 8

Ответ: ___________________________.

Решение

Проследим за изменениями значений переменных:

s = 0, n = 75 – значения до цикла;

s + n (75) < 150, s = s + 15 = 15, n = n – 5 = 70 – значения после первой итерации;

s + n (85) < 150, s = s + 15 = 30, n = n – 5 = 65 – значения после 2 итерации;

s + n (95) < 150, s = s + 15 = 45, n = n – 5 = 60 – значения после 3 итерации;

s + n (105) < 150, s = s + 15 = 60, n = n – 5 = 55 – значения после 4 итерации;

s + n (115) < 150, s = s + 15 = 75, n = n – 5 = 50 – значения после 5 итерации;

s + n (125) < 150, s = s + 15 = 90, n = n – 5 = 45 – значения после 6 итерации;

s + n (135) < 150, s = s + 15 = 105, n = n – 5 = 40 – значения после 7 итерации;

s + n (145) < 150, s = s + 15 = 120, n = n – 5 = 35 – значения после 8 итерации;

цикл на следующем шаге прерывается, программа выводит искомое значение.

Ответ: 35.

Задание 9

Автоматическая камера производит растровые изображения размером 200×256 пикселей. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Объём файла с изображением не может превышать 65 Кбайт без учёта размера заголовка файла. Какое максимальное количество цветов можно использовать в палитре?

Ответ: ___________________________.

Решение

Для начала немного простых вычислений:

200 × 256 – число пикселей растрового изображения;

65 Кбайт = 65 × 2 10 × 2 3 бит – верхний порог объема файла.

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

И, наконец, искомое значение, которое определим по классической формуле :

2 i = n , 2 10 .

Ответ: 1024.

Задание 10

Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А, причём в каждом слове есть ровно одна гласная буква и она встречается ровно 1 раз. Каждая из допустимых согласных букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Ответ: ___________________________.

Решение

Если бы не условие «есть ровно одна гласная буква и она встречается ровно 1 раз», задача бы решалась совсем просто. Но есть это условие, и есть две разные гласные.

Эта гласная может находится на одной из 5 позиций. Предположим, что она находится на первой позиции. Возможных вариантов гласных в этом случае на этой позиции ровно 2. На остальных четырех позициях у нас по два варианта согласных. Итого всего вариантов для первого случая:

2 × 2 × 2 × 2 × 2 = 2 5 = 32

Всего вариантов расположения гласной буквы в нашем слове, повторюсь, ровно 5. Итого:

Ответ: 160.

Задание 11

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(4). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Ответ: ___________________________.

Решение

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

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

Ответ: 1231412.

Задание 12

В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда – нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-адресом 117.191.37.84 адрес сети равен 117.191.37.80. Чему равно наименьшее возможное значение последнего (самого правого) байта маски? Ответ запишите в виде десятичного числа.

Ответ: ___________________________.

Решение

Запишем друг под другом двоичное представление последнего правого байта IP-адреса, адреса сети и маски в соответствии с определением (в верхней строке для удобства при дальнейшем обращении биты пронумерованы):



Маска – ?
Адрес сети

Будем двигаться справа налево, подставляя значения битов в маске. При этом учтем, что у нас в маске «сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда – нули».

Начиная с 0-го бита (справа налево), будем подбирать значения маске сети с учетом поразрядной конъюнкции:



Маска – ?
Адрес сети

В 4-м бите очевидно, что нулевое значение уже не подходит и там должна быть 1 (единица). Начиная с этой позиции и далее двигаясь влево, у нас будут стоять все единицы:



Маска – ?
Адрес сети

Искомое значение крайнего правого байта равно 111100002, что соответствует значению 24010 в десятеричной системе счисления.

Ответ: 240.

Задание 13

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 7 символов и содержащий только символы из 26-символьного набора прописных латинских букв. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.

Для хранения сведений о 30 пользователях потребовалось 600 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Ответ: ___________________________.

Решение

На хранение сведений каждого пользователя отведено

600 ÷ 30 = 20 байт.

На кодирование 26 символов требуется минимум 5 бит памяти. Следовательно на пароль из 7 символов требуется

5 × 7 = 35 бит.

35 бит требует минимум целых 5 байт памяти.

Искомое число байт для хранения дополнительных сведений об одном пользователе составляет:

20 байт – 5 байт = 15 байт.

Ответ: 15.

Задание 14

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

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

заменить (111, 27)

преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкции

ЕСЛИ условие

ТО команда1

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно).

В конструкции

ЕСЛИ условие

ТО команда1

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 82 идущих подряд цифр 1? В ответе запишите полученную строку.

ПОКА нашлось (11111) ИЛИ нашлось (888)

ЕСЛИ нашлось (11111)

ТО заменить (11111, 88)

ЕСЛИ нашлось (888)

ТО заменить (888, 8)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

Ответ: ___________________________.

Решение

«Визуализируем» ситуацию:

82 единицы условно можно представить как 16 групп по 5 единиц, а также одну группу из двух единиц. Первый вызов оператора условия дает нам 16 групп пар из восьмерок – это 32 восьмерки или 10 групп по три восьмерки, а также еще одна свободная пара восьмерок. Очевидно, что последние две единички так и останутся не затронутые исполнителем. А 12 оставшиеся восьмерки, сгруппированные по три – это уже 4 восьмерки. Еще одна итерация – остается 2 восьмерки и 2 единички.

Ответ: 8811.

Задание 15

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город М, проходящих через город Л?

Ответ: ___________________________.

Решение

Рассмотрим нашу схему еще раз. На этот раз на схеме мы видим метки, расположенные в определенном порядке.

Для начала отметим, что пути из точки И в точку М – прямая и через точку К – выделены цветом. Это сделано потому, что по условию задачи необходимо определить число путей только через точку Л.

Начнем со стартовой точки А – это особая точка, туда не ведет ни одна дорога, формально туда можно попасть только из нее самой. Положим, что число путей в нее равно 1.

Вторая точка Б – очевидно, что в нее можно попасть только из одной точки и только одним путем. Третьей точкой не может быть ни В ни Г – число путей в точку В нельзя определить, не определив число путей в Г, а в Г – не определив число путей в Д. Д – третий пункт на нашем пути. Число путей, которые ведут к нему, равно 1. Продолжим эту цепочку умозаключений, определяя число путей, ведущих в данную точку, как сумму числа путей в предыдущих точках, ведущих непосредственно к текущей. Точка И – критическая точка – число путей, ведущих к ней равно сумме 5(Е)+16(Ж)+7(З) и равно 28. Следующая точка – Л, к ней ведет дорога только через И, другого пути нет, а следовательно число путей также остается равным 28. И, наконец, точка-финиш – М – к ней ведет по условию задачи только одна дорога, значит искомое значение также останется равным 28.

Ответ: 28.

Задание 16

Значение арифметического выражения 9 7 + 3 21 – 9 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Ответ: ___________________________.

Для решения задачи перепишем исходное выражение, а также выполним перестановки слагаемых:

3 21 + 3 14 – 3 2 .

Напомним, что в троичной системе счисления само число 3 10 записывается 10 3 . K -я степень числа 10n суть 1 и K нулей. И также очевидно, что первое слагаемое 3 21 никак на число двоек не влияет. А вот разность влиять может.

Ответ: 12.

Задание 17

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» – символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в сотнях тысяч) будет найдено по запросу Горло | Корабль | Нос ? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Ответ: ___________________________.

Решение

Конечно, операция ИЛИ указывает на операцию сложения значений найденных страниц по каждому слову отдельно: 35+35+40. Но по некоторым запросам были страницы, общие для каждой из пар слов – их необходимо исключить, т.е. необходимо вычесть 33 из найденной ранее суммы.

Ответ: 77.

Задание 18

Для какого наибольшего целого неотрицательного числа А выражение

(48 ≠ y + 2x) \/ (A < x) \/ (A < y)

тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?

Ответ: ___________________________.

Решение

Задача чисто математическая…

Данное в условии задания выражение суть дизъюнкция трех слагаемых. Второе и третье слагаемое зависимы от искомого параметра:

Представим первое слагаемое иначе:

y = –2x + 48

Точки прямой (графика функции ) с целочисленными координатами являются теми значениями переменных x и y, в которых перестает быть истинным. Следовательно, нам нужно найти такое А, которое в этих точках обеспечило бы истинность или .

Или при разных x и y, принадлежащих прямой , будут попеременно (иногда и одновременно) принимать истинное значение при любом А в диапазоне . в этой связи важно понимать, каким должен быть параметр А для случая, когда y = x .

Т.е. получаем систему:

Решение найти несложно: y=x=16. И наибольшее целое, которое нам подходит для параметра А=15.

Ответ: 15.

Задание 19

В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 2, 4, 3, 6, 3, 7, 8, 2, 9, 1 соответственно, т.е. A = 2, A = 4 и т.д. Определите значение переменной c после выполнения следующего фрагмента этой программы, записанного ниже на пяти языках программирования.

Ответ: ___________________________.

Решение

Фрагмент программы исполняет цикл повторения. Число итераций равно 9. Каждый раз при выполнении условия переменная с увеличивает свое значение на 1, а также меняет значения двух элементов массива местами.

Исходная последовательность: 2, 4, 3, 6, 3, 7, 8, 2, 9, 1. В записи можно построить следующую схему итераций:

Шаг итерации:	Проверка условия	После замены	Переменная с






	2<2 – НЕТ

	2<1 – НЕТ

Ответ: 7.

Задание 20

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 21, а потом 3.

Ответ: ___________________________.

Решение

Немного анализа кода:

Мы должны вывести значения переменных L и M. Переменная M, это видно немного изучив код, указывает на число итераций цикла, т.е. тело цикла должно выполниться три раза ровно.
Значение числа L, которое должно быть выведено первым, произведение, равное 21. Получить в произведении 21 можно из 7 и 3. Заметим также, что произведение возможно только при нечетном значении переменной x в текущей итерации.
Оператор условия указывает на то, что один раз из трех значение переменной будет четным. В оставшиеся два раза при нечетном значении переменной x , мы получаем остаток от деления x на 8 будет равным один раз 3, а другой раз 7.
Значение переменной x уменьшается три раза в 8 раз операцией целочисленного деления.

Соединив все сказанное ранее, получаем два варианта:

x 1 = (7 × 8 + ?) × 8 + 3 и x 2 = (3 × 8 + ?) × 8 + 7

Вместо знака вопроса нам необходимо подобрать значение, которое будет не больше 8 и будет четным. Не забудем еще про условие в задании – «наибольшее x». Большее четное, не превосходящее 8 – 6. А из x1 и x2, очевидно, что первое больше. Вычислив, получим x=499.

Ответ: 499.

Задание 21

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

Примечание. Функции abs и iabs возвращают абсолютное значение своего входного параметра.

Ответ: ___________________________.

Решение

Запишем нашу функцию в привычной форме:

Для наглядности картины, также построим график этой функции:

Присмотревшись к коду, отметим следующие очевидные факты: до момента исполнения цикла переменная M=-20 и R=26.

Теперь сам цикл: двадцать одна итерация, каждая зависит от выполнения (или невыполнения) условия. Проверять все значения нет необходимости – график нам здесь очень поможет. Двигаясь слева направо значения будут переменных M и R будут меняться пока не будет достигнута первая точка минимума: x=-8. Далее и до точки x=8 проверка условия дает ложные значения и значения переменных не меняется. В точке x=8 произойдет изменение значений уже в последний раз. Получаем искомый результат M=8, R=2, M+R=10.

Ответ: 10.

Задание 22

Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

Прибавить 2
Умножить на 2
Прибавить 3

Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.

Программа для Вычислителя – это последовательность команд.

Сколько существует таких программ, которые преобразуют исходное число 2 в число 22 и при этом траектория вычислений программы содержит число 11?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.

Ответ: ___________________________.

Решение

Для начала решим задачу просто, без учета дополнительного условия «содержит число 11»:

Программа короткая, а также она не дает в своей траектории вычисления значения 11. И тут стоит разбить задачу на две небольшие задачи: определить число путей от 2 до 11 и от 11 до 22. Итоговый результат, очевидно, будет соответствовать произведению этих двух значений. Построение сложных схем с деревьями – не рациональная трата времени на экзамене. Чисел в нашем диапазоне не так много, поэтому предлагаю рассмотреть следующий алгоритм:

Выпишем все числа от стартового и до последнего включительно. Под первым напишем 1. Двигаясь слева направо, рассмотрим число способов попадания в текущую позицию, используя данные нам команды.

Сразу можно убрать очевидные позиции, не влияющие на решение: 3 можно зачеркнуть – понятно, что в нее нельзя попасть из стартовой позиции используя одну из доступных нам команд; 10 – через нее мы не можем никак попасть в нашу промежуточную, а главное, обязательную позицию 11.

В 4 мы можем попасть двумя путями-командами: х2 и +2, т.е. через 4 проходят 2 пути. Напишем это значение под 4. В 5 можно попасть единственным способом: +3. Напишем под 5 значение 1. В 6 можно попасть единственным путем – через 4. А под ней у нас указано значение 2. Соответственно именно по этим двум путям, проходя 4 мы попадем из 2 в 6. Пишем под 6 значение 2. В 7 можно попасть из двух предыдущих позиций, используя имеющиеся у нас команды, и для получения числа путей, которые нам доступны для попадания в 7, мы сложим числа, которые указывали под этими предыдущими позициями. Т.е. в 7 мы попадаем 2 (из-под 4) + 1 (из-под 5) = 3 путями. Действуя по этой схеме и далее получаем:

Перейдем в правую половину от условного центра – 11. Только теперь при расчете будем учитывать только те пути, которые проходят через этот центр.

Ответ: 100.

Задание 23

Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?

(y1 → (y2 /\ x1)) /\ (x1 → x2) = 1

(y2 → (y3 /\ x2)) /\ (x2 → x3) = 1

(y6 → (y7 /\ x6)) /\ (x6 → x7) = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x7, y1, y2, … y7, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Ответ: ___________________________.

Решение

Довольно детальный разбор данной категории задач был опубликован в свое время в статье «Системы логических уравнений: решение с помощью битовых цепочек» .

И для дальнейших рассуждений мы вспомним (для наглядности выпишем) некоторые определения и свойства:

Посмотрим теперь на нашу систему еще раз. Обратим внимание, что ее можно переписать немного иначе. Для этого прежде всего заметим, что каждый из выделенных множителей в первых шести уравнениях, а также их взаимное произведение равны 1.

Немного поработаем над первыми множителями уравнений в системе:

С учетом высказанных выше соображений, получим еще два уравнения, и исходная система уравнений примет вид:

В такой форме исходная система сводится к типовым заданиям, рассмотренным в указанной ранее статье.

Если рассмотреть отдельно первое и второе уравнения новой системы, то им соответствуют наборы (позвольте предоставить подробный разбор этого вывода оставить для читателя):

Эти рассуждения привели БЫ нас к возможным 8 × 8 = 64 вариантам решений, если бы не третье уравнение. В третьем уравнении мы сразу можем ограничиться рассмотрением только тех вариантов наборов, которые подходят для первых двух уравнений. Если подставить в третье уравнение первый набор y 1…y 7, состоящий только из 1, то очевидно, что ему будет соответствовать только один набор x 1…x 7, который также состоит только из 1. Любой другой набор, в котором есть хоть один 0, нам не подходит. Рассмотрим второй набор y1…y7 – 0111111. Для x 1 допустимы оба возможных варианта значений – 0 и 1. Остальные значения, как и в предыдущем случае не могут быть равны 0. Наборов, соответствующих данному условию у нас два. Третьему набору y1…y7 – 011111 будут подходить первые три набора x 1…x 7. И т.д. рассуждая аналогично, мы получим, что искомое число наборов равно

1 + 2 + … + 7 + 8 = 36.

Ответ: 36.

Часть 2

Для записи ответов на задания этой части (24–27) используйте БЛАНК ОТВЕТОВ № 2. Запишите сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво.

Далее не видим необходимости придумывать что-то отличное от официального содержания КИМа демоверсии. Данный документ уже несет в себе «содержание верного ответа и указания по оцениванию», а также «указания для оценивания» и некоторые «примечания для эксперта». Данный материал и приведен далее.

Задание 24

На обработку поступает натуральное число, не превышающее 109. Нужно написать программу, которая выводит на экран минимальную чётную цифру этого числа. Если в числе нет чётных цифр, требуется на экран вывести «NO». Программист написал программу неправильно. Ниже эта программа для Вашего удобства приведена на пяти языках программирования.

Последовательно выполните следующее.

1. Напишите, что выведет эта программа при вводе числа 231.

2. Приведите пример такого трёхзначного числа, при вводе которого приведённая программа, несмотря на ошибки, выдаёт верный ответ.

3. Найдите допущенные программистом ошибки и исправьте их. Исправление ошибки должно затрагивать только строку, в которой находится ошибка. Для каждой ошибки:

выпишите строку, в которой сделана ошибка;
укажите, как исправить ошибку, т.е. приведите правильный вариант строки.

Известно, что в тексте программы можно исправить ровно две строки так, чтобы она стала работать правильно.

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

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

Решение использует запись программы на Паскале. Допускается использование программы на любом из четырёх других языков программирования.

1. Программа выведет число 1.

2. Программа выдаёт правильный ответ, например, для числа 132.

Замечание для проверяющего. Программа работает неправильно из-за неверной начальной инициализации и неверной проверки отсутствия чётных цифр. Соответственно, программа будет выдавать верный ответ, если вводимое число не содержит 0, содержит хотя бы одну чётную цифру и наименьшая чётная цифра числа не больше младшей (крайней правой) цифры числа (или просто стоит последней).

3. В программе есть две ошибки.

Первая ошибка: неверная инициализация ответа (переменная minDigit).

Строка с ошибкой:

minDigit:= N mod 10;

Верное исправление:

Вместо 10 может быть использовано любое целое число, большее 8.

Вторая ошибка: неверная проверка отсутствия чётных цифр.

Строка с ошибкой:

if minDigit = 0 then

Верное исправление:

if minDigit = 10 then

Вместо 10 может быть другое число, большее 8, которое было положено в minDigit при исправлении первой ошибки, или проверка, что minDigit > 8

Указания по оцениванию	Баллы
Обратите внимание! В задаче требовалось выполнить четыре действия: 1) указать, что выведет программа при конкретном входном числе; 2) указать пример входного числа, при котором программа выдаёт верный ответ; 3) исправить первую ошибку; 4) исправить вторую ошибку. Для проверки правильности выполнения п. 2) нужно формально выполнить исходную (ошибочную) программу с входными данными, которые указал экзаменуемый, и убедиться в том, что результат, выданный программой, будет таким же, как и для правильной программы. Для действий 3) и 4) ошибка считается исправленной, если выполнены оба следующих условия: а) правильно указана строка с ошибкой; б) указан такой новый вариант строки, что при исправлении другой ошибки получается правильная программа
Выполнены все четыре необходимых действия, и ни одна верная строка не указана в качестве ошибочной
Не выполнены условия, позволяющие поставить 3 балла. Имеет место одна из следующих ситуаций: а) выполнены три из четырёх необходимых действий. Ни одна верная строка не указана в качестве ошибочной; б) выполнены все четыре необходимых действия. Указано в качестве ошибочной не более одной верной строки
Не выполнены условия, позволяющие поставить 2 или 3 балла. Выполнены два из четырёх необходимых действия
Не выполнены условия, позволяющие поставить 1, 2 или 3 балла

Задание 25

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит минимум среди элементов массива, не делящихся нацело на 6, а затем заменяет каждый элемент, не делящийся нацело на 6, на число, равное найденному минимуму. Гарантируется, что хотя бы один такой элемент в массиве есть. В качестве результата необходимо вывести изменённый массив, каждый элемент выводится с новой строчки.

Например, для исходного массива из шести элементов:

программа должна вывести следующий массив

На языке Паскаль

На языке Python

На языке Бейсик

На языке С++

На Алгоритмическом языке

Указания по оцениванию	Баллы
Общие указания. 1. В алгоритме, записанном на языке программирования, допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора программы. 2. Эффективность алгоритма не имеет значения и не оценивается. 3. Допускается запись алгоритма на языке программирования, отличном от языков, приведённых в условии. В этом случае должны использоваться переменные, аналогичные описанным в условии. Если язык программирования использует типизированные переменные, описания переменных должны быть аналогичны описаниям переменных на Алгоритмическом языке. Использование нетипизированных или необъявленных переменных возможно только в случае, если это допускается языком программирования; при этом количество переменных и их идентификаторы должны соответствовать условию задачи. 4. Допускается формат вывода массива, отличный от указанного, например в строчку
Предложен правильный алгоритм, который изменяет исходный массив и выводит в качестве результата изменённый массив
выполнены условия, позволяющие поставить 2 балла. При этом предложено в целом верное решение, содержащее не более одной ошибки из числа следующих: 1) в цикле происходит выход за границу массива; 2) не инициализируется или неверно инициализируется минимум; 3) неверно осуществляется проверка делимости на 6; 4) проверяется делимость на 6 не элемента массива, а его индекса; 5) в сравнении с минимумом перепутаны знаки «больше» и «меньше»; 6) сравнение с минимумом производится для индекса элемента массива, а не для его значения; 7) неверно составлено логическое условие (например, используется or вместо and); 8) исходный массив не изменяется; 9) изменяются не все требуемые элементы (например, только первый или последний из них); 10) отсутствует вывод ответа, или ответ выводится не полностью (например, только один элемент массива ввиду пропущенного цикла вывода элементов или операторных скобок); 11) используется переменная, не объявленная в разделе описания переменных; 12) не указано или неверно указано условие завершения цикла;
Ошибок, перечисленных в п. 1–13, две или больше, или алгоритм сформулирован неверно (в том числе при отсутствии в явном или неявном виде цикла поиска нужного элемента)
Максимальный балл

Задание 26

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций:

(11, 7), (30, 7), (10, 8), (10, 21).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было шесть камней, во второй куче – S камней; 1 ≤ S ≤ 61.

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

Выполните следующие задания.

Задание 1

в) Укажите все такие значения числа S, при которых Петя может выиграть за один ход.

г) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Задание 2

Укажите такое значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

Петя не может выиграть за один ход;
Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Для указанного значения S опишите выигрышную стратегию Пети.

Задание 3

Укажите значение S, при котором одновременно выполняются два условия:

у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).

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

Задание 1

а) Петя может выиграть при 21 ≤ S ≤ 61.

Задание 2

Возможное значение S: 20. В этом случае Петя, очевидно, не может выиграть первым ходом. Однако он может получить позицию (7, 20). После хода Вани может возникнуть одна из четырёх позиций: (8, 20), (21, 20), (7, 21), (7, 60). В каждой из этих позиций Петя может выиграть одним ходом, утроив количество камней во второй куче.

Замечание для проверяющего. Ещё одно возможное значение S для этого задания – число 13. В этом случае Петя первым ходом должен утроить количество камней в меньшей куче и получить позицию (6 * 3, 13) = (18, 13). При такой позиции Ваня не может выиграть первым ходом, а после любого хода Вани Петя может выиграть, утроив количество камней в большей куче. Достаточно указать одно значение S и описать для него выигрышную стратегию.

Задание 3

Возможное значение S: 19. После первого хода Пети возможны позиции:
(7, 19), (18, 19), (6, 20), (6, 57). В позициях (18, 19) и (6, 57) Ваня может выиграть первым ходом, утроив количество камней во второй куче. Из позиций (7, 19) и (6, 20) Ваня может получить позицию (7, 20). Эта позиция разобрана в п. 2. Игрок, который её получил (теперь это Ваня), выигрывает своим вторым ходом.

В таблице изображено дерево возможных партий (и только их) при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) выделены жирным шрифтом. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).

Примечание для эксперта. Дерево всех партий может быть также изображено в виде ориентированного графа – так, как показано на рисунке, или другим способом. Важно, чтобы множество полных путей в графе находилось во взаимно однозначном соответствии со множеством партий, возможных при описанной в решении стратегии.

Рис. 1. Дерево всех партий, возможных при Ваниной стратегии. Ходы Пети показаны пунктиром; ходы Вани – сплошными линиями. Прямоугольником обозначены позиции, в которых партия заканчивается.

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

Указания по оцениванию	Баллы
В задаче требуется выполнить три задания. Их трудность возрастает. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже). Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу, например арифметическая ошибка при вычислении количества камней в заключительной позиции, при оценке решения не учитывается. Задание 1 выполнено, если выполнены оба пункта: а) и б), т.е. для п. а) перечислены все значения S, удовлетворяющие условию (и только они), для п. б) указано верное значение S (и только оно). Задание 2 выполнено, если правильно указана позиция, выигрышная для Пети, и описана соответствующая стратегия Пети – так, как это сделано в примере решения, или другим способом, например с помощью дерева всех возможных при выбранной стратегии Пети партий (и только их). Задание 3 выполнено, если правильно указана позиция, выигрышная для Вани, и построено дерево всех возможных при Ваниной стратегии партий (и только их). Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом
Выполнены задания 1, 2 и 3
Не выполнены условия, позволяющие поставить 3 балла, и выполнено одно из следующих условий. 1. Выполнено задание 3. 2. Выполнены задания 1 и 2
Не выполнены условия, позволяющие поставить 3 или 2 балла, и выполнено одно из следующих условий. 1. Выполнено задание 1. 2. Выполнено задание 2
Не выполнено ни одно из условий, позволяющих поставить 3, 2 или 1 балл

Задание 27

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 29.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.

В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.

Пример входных данных:

Пример выходных данных для приведённого выше примера входных данных:

Пояснение. Из 7 заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 58·4, 58·1, 58·29, 2·1, 2·29, 3·29. Из них на 29 делятся 5 произведений.

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

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла.

Максимальная оценка за правильную программу, эффективную только по времени, – 3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.

Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.

Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Произведение двух чисел делится на 29, если хотя бы один из сомножителей делится на 29.

При вводе чисел можно подсчитывать количество чисел, кратных 29, не считая четырёх последних. Обозначим их n29.

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

Очередное считанное число будем рассматривать как возможный правый элемент искомой пары.

Если очередное считанное число делится на 29, то к ответу следует прибавить количество чисел до него, не считая четырёх последних (включая считанное).

Если очередное считанное число на 29 не делится, то к ответу следует прибавить n29.

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

Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)

Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти

const s = 4; {требуемое расстояние между элементами}

a: array of longint; {хранение последних s значений}

a_: longint; {очередное значение}

n29: longint; {количество делящихся на 29 элементов, не считая s последних}

cnt: longint; {количество искомых пар}

{Ввод первых s чисел}

for i:=1 to s do readln(a[i]);

{Ввод остальных значений, подсчет искомых пар}

for i:= s + 1 to n do

if a mod 29 = 0 then n29:= n29 + 1;

if a_ mod 29 = 0 then cnt:= cnt + i - s

cnt:= cnt + n29;

{сдвигаем элементы вспомогательного массива влево}

for j:= 1 to s - 1 do a[j] := a;

a[s] := a_ {записываем текущий элемент в конец массива}

СПЕЦИФИКАЦИЯ
контрольных измерительных материалов
единого государственного экзамена 2019 года
по информатике и ИКТ

1. Назначение КИМ ЕГЭ

Единый государственный экзамен (далее - ЕГЭ) представляет собой форму объективной оценки качества подготовки лиц, освоивших образовательные программы среднего общего образования, с использованием заданий стандартизированной формы (контрольных измерительных материалов).

ЕГЭ проводится в соответствии с Федеральным законом от 29.12.2012 № 273-ФЗ «Об образовании в Российской Федерации».

Контрольные измерительные материалы позволяют установить уровень освоения выпускниками Федерального компонента государственного стандарта среднего (полного) общего образования по информатике и ИКТ, базовый и профильный уровни.

Результаты единого государственного экзамена по информатике и ИКТ признаются образовательными организациями среднего профессионального образования и образовательными организациями высшего профессионального образования как результаты вступительных испытаний по информатике и ИКТ.

2. Документы, определяющие содержание КИМ ЕГЭ

3. Подходы к отбору содержания, разработке структуры КИМ ЕГЭ

Содержание заданий разработано по основным темам курса информатики и ИКТ, объединенных в следующие тематические блоки: «Информация и ее кодирование», «Моделирование и компьютерный эксперимент», «Системы счисления», «Логика и алгоритмы», «Элементы теории алгоритмов», «Программирование», «Архитектура компьютеров и компьютерных сетей», «Обработка числовой информации», «Технологии поиска и хранения информации».
Содержанием экзаменационной работы охватывается основное содержание курса информатики и ИКТ, важнейшие его темы, наиболее значимый в них материал, однозначно трактуемый в большинстве преподаваемых в школе вариантов курса информатики и ИКТ.

Работа содержит как задания базового уровня сложности, проверяющие знания и умения, предусмотренные стандартом базового уровня, так
и задания повышенного и высокого уровней сложности, проверяющие знания и умения, предусмотренные стандартом профильного уровня. Количество заданий в варианте КИМ должно, с одной стороны, обеспечить всестороннюю проверку знаний и умений выпускников, приобретенных за весь период обучения по предмету, и, с другой стороны, соответствовать критериям сложности, устойчивости результатов, надежности измерения. С этой целью в КИМ используются задания двух типов: с кратким ответом и развернутым ответом. Структура экзаменационной работы обеспечивает оптимальный баланс заданий разных типов и разновидностей, трех уровней сложности, проверяющих знания и умения на трех различных уровнях: воспроизведения, применения в стандартной ситуации, применения в новой ситуации. Содержание экзаменационной работы отражает значительную часть содержания предмета. Все это обеспечивает валидность результатов тестирования и надежность измерения.

4. Структура КИМ ЕГЭ

Часть 1 содержит 23 задания с кратким ответом.

В экзаменационной работе предложены следующие разновидности заданий с кратким ответом:

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

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

Часть 2 содержит 4 задания с развернутым ответом.

Часть 1 содержит 23 задания базового, повышенного и высокого уровней сложности. В этой части собраны задания с кратким ответом, подразумевающие самостоятельное формулирование и запись ответа в виде числа или последовательности символов. Задания проверяют материал всех тематических блоков. В части 1 12 заданий относится к базовому уровню, 10 заданий к повышенному уровню сложности, 1 задание - к высокому уровню сложности.