ЕГЭ по информатике:
2016 и далее…
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
Структурные изменения в 2015-2016
2
Структурные изменения в 2015-2016
1) удаление части А
2) сокращение количества задач
3) объединение простых задач (4, 6, 7, 9)
Цель: оставить больше времени на решение
сложных задач.
4) язык Python
!
К.Ю. Поляков, 2015
Вариабельность!
http://kpolyakov.spb.ru
ЕГЭ по информатике: 2016 и далее…
3
Сколько единиц в двоичной записи
шестнадцатеричного числа 12F016.
1
2
12 102
F
11112
0
1+1+4=6
Укажите наименьшее число, двоичная запись которого
содержит ровно три значащих нуля и три единицы.
Ответ запишите в десятичной системе счисления
1000112 = 35
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B1: двоичная система счисления
ЕГЭ по информатике: 2016 и далее…4
B1: двоичная система счисления
числа 1025?
1) «в лоб» – переводить…
2) 1025 = 1024 + 1
1024 = 100000000002
1025 = 100000000012
Ответ: 2
511?
511 = 512 - 1
= 10000000002 - 1 = 1111111112
Ответ: 9
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B1: двоичная система счисления
ЕГЭ по информатике: 2016 и далее…5
B1: двоичная система счисления
Сколько единиц в двоичной записи десятичного
числа 999?
1) «в лоб» – переводить…
2) 999 = 1023 – 16 – 8
1023 = 1024 – 1 = 11111111112
минус две единицы: 8
519?
519 = 512 + 7
512 = 10000000002
7 = 1112
плюс три единицы: 4
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B1: системы счисления
ЕГЭ по информатике: 2016 и далее…6
B1: системы счисления
Какое из указанных ниже чисел может быть записано в
двоичной системе счисления в виде 1xxx10, где x может
означать как 0, так и 1?
1) 74
2) 38
3) 60
4) 47
1) 1000102 = 34 N 1111102 = 62
2) 1xxx10 делится на 2
3) 1xxx10 не делится на 4
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B2: логические функции
ЕГЭ по информатике: 2016 и далее…7
B2: логические функции
x1
1
!
x2
0
x3
x4
0
1
x5
x6
x7
x8
1
1
F
0
1
1
Все варианты – простые И или ИЛИ!
1) «в лоб» – подставлять в формулы…
2) если все «ИЛИ» один ноль
проверяем строку, где F = 0
x2 без инверсии, x8 с инверсией
3) если все «И» одна единица
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B2: логические функции
ЕГЭ по информатике: 2016 и далее…8
B2: логические функции
Задана таблица функции z x x
?z
0
0
0
0
1
1
1
1
?y
0
0
1
1
0
0
1
1
К.Ю. Поляков, 2015
?x
0
1
0
1
0
1
0
1
F
0
1
0
1
0
0
0
1
y.
z x x y
x (z y)
x 0 F 0
x 1
z 1
F 0
y 0
Ответ: zyx
http://kpolyakov.spb.ru
B2: логические функции
ЕГЭ по информатике: 2016 и далее…9
B2: логические функции
Задана таблица функции x y z x
Определите, в каких столбцах x, y и z.
?z
0
0
0
0
1
1
1
1
?x
0
0
1
1
0
0
1
1
К.Ю. Поляков, 2015
?y
0
1
0
1
0
1
0
1
F
0
0
1
0
1
1
1
1
y z.
x y z x y z
z 0 F x y
z 1 F x y x y
(x x) (y x) y
y x y 1
z 0
x 1 Ответ: zxy
F 1
y 0
http://kpolyakov.spb.ru
B3: весовые матрицы графов
ЕГЭ по информатике: 2016 и далее…10
B3: весовые матрицы графов
A
A
B
C
D
E
F
Z
B
4
C
6
3
D
E
F
11
4
5
7
4
Z
30
27
10
8
2
29
1) матрица несимметричная (орграф)
2) две дороги с односторонним движением
3) «сколько есть дорог проходящих через N
пунктов?»
4) «… не менее, чем через N пунктов?»
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B3: весовые матрицы графов
ЕГЭ по информатике: 2016 и далее…11
B3: весовые матрицы графов
1
1
2
2
3
45
4
5
6
6
45
55
3
15 60
2
10 40
15
20 35
4
55
2
55 60 20 55
35
45
45
Е
А
5
2
степени
вершин
К.Ю. Поляков, 2015
Д
2
40
7
Б
7
10
3
4
5
К
В
степень 4
степень 5
Г
Ответ: 20
http://kpolyakov.spb.ru
B4-1: табличные базы данных
ЕГЭ по информатике: 2016 и далее…12
B4-1: табличные базы данных
1) сколько потомков (детей, внуков, правнуков…) у X?
2) сколько предков X есть в таблице?
3) найдите дедушку по материнской линии
23
24
25
К.Ю. Поляков, 2015
34
57
35
42
http://kpolyakov.spb.ru
ЕГЭ по информатике: 2016 и далее…
13
Сообщения, содержат буквы П, О, С, Т; используется
двоичный код, допускающий однозначное
декодирование. Кодовые слова:
Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при
котором код будет допускать однозначное
декодирование. Если таких кодов несколько, укажите
код с наименьшим числовым значением.
1
0
0x 10
0xx
О
11
101
П
К.Ю. Поляков, 2015
0
0
110
1
1
1
0
1
Т
http://kpolyakov.spb.ru
B5: кодирование и декодирование
ЕГЭ по информатике: 2016 и далее…14
B5: кодирование и декодирование
Сообщения содержат три гласные буквы: А, Е, И – и пять
согласных букв: Б, В, Г, Д, К. Буквы кодируются
префиксным кодом. Известно, что все кодовые слова для
согласных имеют одну и ту же длину, и
А –1, Е – 01, И – 001.
Какова наименьшая возможная длина кодовых слов для
согласных букв?
0
5 согласных букв 3 бита 4 бита 5 бит
4: 1xx
0
1
2: 01x
0
1
А
1: 001
1
Е
свободны: 000
000x 000xx
1
2
4
И
К.Ю. Поляков, 2015
6 бит
000xxx
8
http://kpolyakov.spb.ru
B6-1: автомат
ЕГЭ по информатике: 2016 и далее…15
B6-1: автомат
чётность восстановлена!
Вход: натуральное число N.
1. В конец двоичной записи дописывается бит чётности
(сумма цифр mod 2).
2. К полученной строке дописывается ещё бит чётности.
Укажите наименьшее число, для которого в результате
выполнения этого алгоритма получится число
больше 125.
!
На шаге 2 добавляется 0 2!
Должны получить чётное = 126 или 128
После div 2 должна сохраниться чётность!
126 / 2 = 63 = 1111112: – 6 единиц, чётность
Ответ:
К.Ю. Поляков, 2015
31
http://kpolyakov.spb.ru
B10: комбинаторика
ЕГЭ по информатике: 2016 и далее…16
B10: комбинаторика
Сколько есть 5-буквенных слов, в которых есть только
буквы П, И, Р, причём буква П появляется ровно 1 раз.
П****
*П***
**П**
***П*
****П
К.Ю. Поляков, 2015
24 = 16 слов
Ответ: 16· 5 = 80.
http://kpolyakov.spb.ru
B12: адресация в сетях
ЕГЭ по информатике: 2016 и далее…17
B12: адресация в сетях
IP-адрес 224.128.112.142
Адрес сети 224.128.64.0.
Чему равен третий слева байт маски?
не забываем про
*.*.112.*
старшие единицы!
*.*.64.0
маска: 110000002 = 192
192
112 = 011100002
64 = 010000002
!
К.Ю. Поляков, 2015
Поразрядная конъюнкция!
http://kpolyakov.spb.ru
B12: адресация в сетях
ЕГЭ по информатике: 2016 и далее…18
B12: адресация в сетях
IP-адрес 111.81.208.27
Адрес сети 111.81.192.0.
Каково минимальное значение третьего слева
байта маски?
*.*.208.*
*.*.192.0
208 =
192 =
маска:
маска:
110100002
110000002
111000002
110000002
192
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B14: Чертёжник
ЕГЭ по информатике: 2016 и далее…19
B14: Чертёжник
сместиться на (–3, –3) 1)
ПОВТОРИ N РАЗ
2)
сместиться на (a, b) 3)
сместиться на (27, 12) 4)
КОНЕЦ ПОВТОРИ
сместиться на (–22, -7)
3 N x 22 0
3 N y 7 0
наименьшее N > 1
наибольшее N
все возможные N
сумма всех N
N x 25
N y 10
N = общий делитель(25,10)
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B14: Редактор
ЕГЭ по информатике: 2016 и далее…20
B14: Редактор
1) заменить(v,w)
2) нашлось(v)
ПОКА нашлось (222) ИЛИ нашлось (888)
ЕСЛИ нашлось (222)
ТО заменить (222, 8)
ИНАЧЕ заменить (888, 2)
Каков результат обработки строки 88888…8 ?
888888888…8
2 2 2
8
К.Ю. Поляков, 2015
!
За 4 шага
убрали
8 восьмёрок!
68 - 8·8 = 4
68
8888 28
http://kpolyakov.spb.ru
ЕГЭ по информатике: 2016 и далее…
21
города А в город Л, не проходящих через B?
Д
Б
Ж
В
А
Г
К.Ю. Поляков, 2015
И
Е
Л
К
http://kpolyakov.spb.ru
B15: количество путей в графах
ЕГЭ по информатике: 2016 и далее…22
B15: количество путей в графах
Сколько существует различных путей из
города А в город Л, проходящих через Д?
Д
Б
Ж
В
А
Г
К.Ю. Поляков, 2015
И
Е
Л
К
http://kpolyakov.spb.ru
B16: системы счисления
ЕГЭ по информатике: 2016 и далее…23
B16: системы счисления
Сколько единиц содержится в двоичной
(троичной, …) записи числа X?
10N = 100…0
10N-1 = 99…9
N
N
2N = 100…02
N
3N = 100…03
N
К.Ю. Поляков, 2015
2N-1 = 11…1
N
3N-1 = 22…2
N
http://kpolyakov.spb.ru
B16: системы счисления
ЕГЭ по информатике: 2016 и далее…24
B16: системы счисления
2N – 2M = 2M · (2N-M – 1)
= 100…02 · 11…12
N-M
M
= 11…100…02
N-M
К.Ю. Поляков, 2015
M
http://kpolyakov.spb.ru
B16: системы счисления
ЕГЭ по информатике: 2016 и далее…25
B16: системы счисления
числа (24400–1)·(42200+2)?
(24400–1)·(42200+2) = (24400–1)·(24400+1+1)
= (24400–1)·(24400+1) + 24400–1
= 28800 – 1 + 24400–1
= 28800 + 24400 – 21
1
4399
1 + 4399 = 4400
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B16: системы счисления
ЕГЭ по информатике: 2016 и далее…27
B16: системы счисления
Сколько единиц содержится в двоичной записи
значения числа 8148 – 4123 + 2654 – 17?
8148 = 2444
4123 = 2246
2654
17 = 16 + 1
= 24 + 2 0
2654 + 2444 – 2246 – 24 – 20
444 – 2246 – 24 – 20
2
1
444 – 2
1 + 444 – 2 = 443
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B16: системы счисления
ЕГЭ по информатике: 2016 и далее…28
B16: системы счисления
Сколько двоек содержится в троичной записи
значения числа 9118 + 3123 – 27?
9118 = 3236
27 = 33
К.Ю. Поляков, 2015
3236 + 3123 – 33
1
120 двоек
http://kpolyakov.spb.ru
B16: системы счисления
ЕГЭ по информатике: 2016 и далее…29
B17: запросы в поисковых системах
Запрос
США | Япония | Китай
Япония | Китай
(США & Япония) | (США & Китай)
США
A = США
Запрос
А|B
B
А&B
A
Страниц
450
260
50
?
B = Япония | Китай
Страниц
450
260
50
?
A
A&B
B
NА | B = NA + NB – NA & B
NA = 450 – 260 + 50 = 240
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B17: запросы в поисковых системах
ЕГЭ по информатике: 2016 и далее…30
P = и Q = . Укажите наименьшую
возможную длину такого отрезка A, что выражение
(x P) (((x Q) (x A)) (x P))
тождественно истинно, то есть равно 1 при любом
значении переменной х.
P (x P),
Q (x Q),
A (x A)
P (Q A P)
P (Q A P)
P Q A P P Q A
P Q A
P
Q
К.Ю. Поляков, 2015
P
37
40
60
77
x
20
Q
http://kpolyakov.spb.ru
B18: логические операции, множества
ЕГЭ по информатике: 2016 и далее…31
Множество А: натуральные числа. Выражение
(x {2, 4, 6, 8, 10, 12}) → (((x {4, 8, 12, 116})
¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12}))
истинно при любом значении х. Определите
наименьшее возможное значение суммы элементов
множества A.
P x {2, 4, 6, 8, 10, 12},
Q x {4, 8, 12, 116},
A x A
P (Q A P)
P Q A
Amin P Q P Q {4, 8, 12}
К.Ю. Поляков, 2015
= 24
http://kpolyakov.spb.ru
B18: логические операции, множества
ЕГЭ по информатике: 2016 и далее…32
B18: логические операции, множества
(x & 49 <> 0) ((x & 33 = 0) (x & A <> 0))
P x & 49 0,
A x & A 0
P (Q A)
Q x & 33 0,
P (Q A) P Q A
P Q A (P Q) A
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B18: логические операции, множества
ЕГЭ по информатике: 2016 и далее…33
B18: логические операции, множества
"&" – побитовая конъюнкция (И). Выражение
(x & 49 <> 0) ((x & 33 = 0) (x & A <> 0))
истинно при любом натуральном х. Определите
наименьшее возможное значение A.
x & 49
номер бита
5 4 3 2 1 0
49 = 110001
X = abcdef
X & 49 = ab000f
x & 49 = 0 все биты {5, 4, 0} нулевые
x & 49 <>
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B18: логические операции, множества
ЕГЭ по информатике: 2016 и далее…34
B18: логические операции, множества
"&" – побитовая конъюнкция (И). Выражение
(x & 49 <> 0) ((x & 33 = 0) (x & A <> 0))
истинно при любом натуральном х. Определите
наименьшее возможное значение A.
(P Q) A
P: x & 49 <> 0 среди битов {5, 4, 0} есть ненулевые
Q: x & 33 = 0 все биты {5, 0} нулевые
номер бита
5 4 3 2 1 0
33 = 100001
!
?
Бит 4 ненулевой!
К.Ю. Поляков, 2015
Что из этого следует?
Amin = 24 = 16
http://kpolyakov.spb.ru
B18: логические операции, множества
ЕГЭ по информатике: 2016 и далее…35
B18: логические операции, множества
"&" – побитовая конъюнкция (И). Выражение
(x & A <> 0) ((x & 20 = 0) (x & 5 <> 0))
истинно при любом натуральном х. Определите
P x & 20 0,
A x & A 0
A (P Q)
Q x & 5 0,
A (P Q) A P Q
P Q A (P Q) A
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B18: логические операции, множества
ЕГЭ по информатике: 2016 и далее…36
B18: логические операции, множества
"&" – побитовая конъюнкция (И). Выражение
(x & A <> 0) ((x & 20 = 0) (x & 5 <> 0))
истинно при любом натуральном х. Определите
наибольшее возможное значение A.
(P Q) A
P: x & 20 = 0 все биты {4, 2} нулевые
Q: x & 5 = 0 все биты {2, 0} нулевые
!
Биты {4, 2, 0} в x нулевые!
Amax = 24 + 22 + 20 = 21
К.Ю. Поляков, 2015
Они обнулят
биты числа
при &!
http://kpolyakov.spb.ru
B18: логические операции, множества
ЕГЭ по информатике: 2016 и далее…37
B19: обработка массивов
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;
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B19: обработка массивов
ЕГЭ по информатике: 2016 и далее…38
B19: обработка массивов
1)
2)
3)
4)
5)
6)
6
9
9
9
9
9
9
9
6
7
7
7
7
7
7
7
6
6
6
6
6
2
2
2
2
2
2
2
1
1
1
5
5
5
5
5
5
5
1
1
1
1
0
0
0
0
3
3
3
3
3
3
3
0
4
4
4
4
4
4
4
0
8
8
8
8
8
8
8
0
с=6
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B19: обработка массивов
ЕГЭ по информатике: 2016 и далее…39
B19: обработка массивов
Массив с индексами от 0 до 9.
c:= 0;
for i:= 1 to 9 do
if A[i] < A then begin
c:= c + 1;
t:= A[i];
A[i]:= A;
перестановка пары
A:= t
end;
Какое значение будет иметь переменная «c»?
4 7 3 8 5 0 1 2 9 6
4 7 3 8 5 0 1 2 9 6
4 7 3 8 5 0 1 2 9 6
К.Ю. Поляков, 2015
с=2
http://kpolyakov.spb.ru
B19: обработка массивов
ЕГЭ по информатике: 2016 и далее…40
B19: обработка массивов
s:=0;
n:=10;
for i:=0 to n-1 do begin
s:=s+A[i]-A
end;
s:=A-A+A-A+A-...
+A-A+A-A+A-A
max = 999 – 100 = 899
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B19: обработка массивов
ЕГЭ по информатике: 2016 и далее…41
B19: обработка массивов
Массив с индексами от 0 до 10.
s:=0;
n:=10;
for i:=0 to n-2 do begin
s:=s+A[i]-A
end;
В массиве находились трёхзначные натуральные числа.
Какое наибольшее значение может иметь «s»?
s:=A-A+A-A+A-...
+A-A+A-A+A-A
max = 999 + 999 – 100 – 100 = 1798
1798
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B19: обработка массивов
ЕГЭ по информатике: 2016 и далее…42
B20: циклы и условия («узнай алгоритм»)
Укажите наименьшее пятизначное число x, при котором
будет напечатано сначала 6, а потом 3.
a:= 0;
Минимум и максимум!
b:= 10;
readln(x);
while x > 0 do begin
y:= x mod 10;
x:= x div 10;
33336
if y > a then a:= y;
if y < b then b:= y;
end;
writeln(a); { максимальная цифра }
writeln(b); { минимальная цифра }
!
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B20: циклы и условия («узнай алгоритм»)
ЕГЭ по информатике: 2016 и далее…43
B20: циклы и условия
Укажите наименьшее число x, большее 100, при котором
будет напечатано 26.
var x, L, M: integer;
begin
x нечётное: НОД(x,65) = 26
readln(x);
x чётное: НОД(x,52) = 26
L:= x; M:= 65;
if L mod 2 = 0 then x делится на 26,
M:= 52;
не делится на 52!
while L <> M do
НОД(104,52) = 52
104
if L > M then
L:= L - M
Ответ: 130
else
M:= M – L;
writeln(M);
Алгоритм Евклида!
end.
!
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B20: циклы и условия
ЕГЭ по информатике: 2016 и далее…44
B21: циклы и процедуры
begin
i
f(i)
f:= n*(n-1)+10
1
10
end;
…
2
12
readln(k);
3
16
i:= 0;
4
22
while f(i) < k do
5
30
36
i:= i + 1;
writeln(i);
6
40
Останов: k <= f(i)
31 … 40
10
К.Ю. Поляков, 2015
?
Для k = 30?
23 … 30
8
http://kpolyakov.spb.ru
B21: циклы и процедуры
ЕГЭ по информатике: 2016 и далее…45
B21: циклы и процедуры
Найдите число различных значений k, при которых
программа выдаёт тот же ответ, что и при k = 36.
function f(n: longint): longint;
begin
Останов:
f:= n*(n-1)+10
f(i-1) < k <= f(i)
end;
(i-1)*(i-2)+10 < k <= i*(i-1)+10
…
i2-3i+12 < k <= i2-i+10
readln(k);
i:= 0;
i=6: 30 < k <= 40
while f(i) < k do
31 … 40
i:= i + 1;
writeln(i);
Ответ: 10
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B21: циклы и процедуры
ЕГЭ по информатике: 2016 и далее…46
B21: циклы и процедуры
Найдите наименьшее значение k, при котором
программа выдаёт тот же ответ, что и при k = 10.
def f(n):
Останов:
return n*n*n
f(i-1) < g(k) <= f(i)
def g(n):
(i-1)3 < 2k+3 <= i3
return 2*n+3
3 < 23 <= i3
k=10:
(i-1)
k = int(input())
i=3
i = 1
while f(i) < g(k):
8 < 2k+3 <= 27
i+=1
3 … 12
print (i)
Ответ: 3
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
B21: циклы и процедуры
ЕГЭ по информатике: 2016 и далее…47
B22: программы для исполнителей
1) прибавь 1
2) умножь на 2
Сколько существует программ, для которых из числа 2
получается число 29 и при этом траектория вычислений
содержит число 14 и не содержит числа 25?
N нечётное
K N 1
Рекуррентная формула: K N
K N 1 K N / 2 N чётное
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
1
1
2
2
3
3
5
5
7
7
10
10
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
13
13
13
13
13
13
13
13
13
13
13
0
0
0
13
13
новый старт
К.Ю. Поляков, 2015
сюда нельзя
http://kpolyakov.spb.ru
B22: программы для исполнителей
ЕГЭ по информатике: 2016 и далее…48
C24: исправление ошибок
Считывается натуральное число x, нужно найти
количество значащих цифр в его двоичной записи.
readln(x);
c:= 0;
while x > 0 do begin
c:= c + x mod 2;
x:= x div 10
end;
writeln(c)
1)
2)
3)
4)
?
?
Что считает?
Когда работает
верно?
Только для x=1
неверное начальное значение
неверное условие цикла
неверное изменение переменных
неверный вывод
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
C24: исправление ошибок
ЕГЭ по информатике: 2016 и далее…49
C24: исправление ошибок
Нужно написать программу, которая выводит на экран
максимальную цифру числа, кратную 3. Если в числе нет
цифр, кратных 3, требуется на экран вывести «NO».
-1
readln(N);
maxDigit:= N mod 10;
Когда работает
while N > 0 do begin
верно?
digit:= N mod 10;
if digit mod 3 1)=последняя
0 then цифра делится на 3
if digit > maxDigit
then
2) последняя
цифра меньше, чем
maxDigit:= нужный
digit;результат
N:= N div 10;
-1
end;
if maxDigit = 0 then writeln("NO")
else writeln(maxDigit);
?
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
C24: исправление ошибок
ЕГЭ по информатике: 2016 и далее…50
Для заданной последовательности неотрицательных
целых чисел необходимо найти максимальное
произведение двух её элементов, номера которых
различаются не менее чем на 8. Количество элементов
последовательности не превышает 10000.
Задача А (2 балла). O(N2) по времени, O(N) по памяти.
Задача Б (3 балла). O(N) по времени, O(N) по памяти.
Задача Б (4 балла). O(N) по времени, O(1) по памяти.
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
ЕГЭ по информатике: 2016 и далее…
51
С27: сложная задача на программирование
Задача А (2 балла). Данные хранятся в массиве.
var N: integer;
a: array of integer;
i, j, max: integer;
begin
readln(N);
for i:=1 to N do read(a[i]);
max:= -1;
for i:= 9 to N do
for j:= 1 to i-8 do
if (a[j]*a[i] > max) then
max:= a[j]*a[i];
writeln(max)
end.
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
С27: сложная задача на программирование
ЕГЭ по информатике: 2016 и далее…52
С27: сложная задача на программирование
Задача Б (3 балла). Данные в массиве, время O(N).
i-8
i
a[i]
m
накапливать!
max a[ j ] a[i] max a[ j ] a[i]
j
j
max:= 0;
m:= 0;
for i:= 9 to N do begin
if a > m then m:= a;
if m*a[i] > max then max:= m*a[i];
end;
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
С27: сложная задача на программирование
ЕГЭ по информатике: 2016 и далее…53
С27: сложная задача на программирование
i-8
i
храним в массиве
var a: array of integer;
x
Начальное заполнение массива:
for i:=1 to 8 do read(a[i]);
Продвижение:
for i:=1 to 7 do
a[i]:=a;
a:= x;
К.Ю. Поляков, 2015
!
Это очередь!
http://kpolyakov.spb.ru
С27: сложная задача на программирование
ЕГЭ по информатике: 2016 и далее…54
С27: сложная задача на программирование
Задача Б (4 балла). Память O(1), время O(N).
a
x
const d = 8; { сдвиг }
... { уже прочитали первые d штук }
max:= 0;
m:= 0;
for i:=d+1 to N do begin
read(x);
if a > m then m:= a;
if m*x > max then max:= m*x;
for j:=1 to d-1 do
a[j]:= a;
a[d]:= x;
end;
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
С27: сложная задача на программирование
ЕГЭ по информатике: 2016 и далее…55
С27: сложная задача на программирование
Задача Б (4 балла). Без сдвига (очередь-кольцо).
i 0
1
2
3
9
1
5
6
7
k
0
a
4
10
2 11
3 12
4 5
8
9
N-1
10 11 12 13 14 15 16 17 18
7
6
7
8
a:= data[i];
for i:=0 to d-1 do read(a[i]);
for i:=d to N-1 do begin
read(x);
k:= i mod d;
if a[k] > m then m:= a[k];
if m*x > max then max:= m*x;
a[k]:=x;
end;
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
С27: сложная задача на программирование
ЕГЭ по информатике: 2016 и далее…56
С27: сложная задача на программирование
Вычислить максимальное чётное произведение двух
показаний, между моментами передачи которых
прошло не менее 8 минут.
x
поддерживаем
1) максимальное из всех
2) максимальное чётное
x
чётное чётное * любое
чётное любое * чётное
К.Ю. Поляков, 2015
храним в массиве
(очередь)
http://kpolyakov.spb.ru
С27: сложная задача на программирование
ЕГЭ по информатике: 2016 и далее…57
С27: сложная задача на программирование
for i:=d to N-1 do begin
read(x);
k:= i mod d;
максимальное
чётное
if a[k] > m then m:= a[k];
if ((a[k] mod 2 = 0) and
(a[k] > mEven)) then mEven:= a[k];
if x mod 2 = 1 then begin
получено
нечётное
if mEven*x > max then
max:= mEven*x;
end
получено
чётное
else
if m*x > max then max:= m*x;
a[k]:=x;
end;
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
С27: сложная задача на программирование
ЕГЭ по информатике: 2016 и далее…58
Выводы
!
К.Ю. Поляков, 2015
Вариабельность!
http://kpolyakov.spb.ru
Выводы
ЕГЭ по информатике: 2016 и далее…59
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru
Решение ЕГЭ информатика
1. Задание. Сколько единиц в двоичной записи шеснадцатеричного числа 12F0 16 ?
Пояснение.
Переведем число 12F0 16 в двоичную систему счисления: 12F0 16 = 1001011110000 2 .
Подсчитаем количество единиц: их 6.
Ответ: 6.
2. Задание Логическая функция F задаётся выражением (¬ z ) ∧ x ∨ x ∧ y . Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
Перем. 1 | Перем. 2 | Перем. 3 | Функция |
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x → y , зависящее от двух переменных x и y , и таблица истинности:
Перем. 1 | Перем. 2 | Функция |
Тогда 1-му столбцу соответствует переменная y , а 2-му столбцу соответствует переменная x . В ответе нужно написать: yx .
Пояснение.
Данное выражение является дизъюнкцией двух конъюнкций. Можем заметить, что в обоих слагаемых есть множитель x . Т. е. при x = 0 сумма будет равна 0. Так, для переменной x подходит только третий столбец.
В восьмой строке таблицы x = 1, а значение функции равно 0. Такое возможно только при z = 1, у = 0, т. е. переменная1 − z , а переменная2 − y .
Ответ: zyx .
3. Задание На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.
Пояснение.
Пункт В − единственный пункт с пятью дорогами, значит ему соответствует П6, а пункт Е − единственный с четырьмя дорогами, значит ему соответствует П4.
Длина дороги из П6 в П4 равна 20.
Ответ: 20.
4. Задание В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите, сколько прямых потомков (т.е. детей и внуков) Павленко А.К. упомянуты в таблице 1.
|
|
ИЛИ
Для групповых операций с файлами используются маски имён файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы:
Символ «?» (вопросительный знак) означает ровно один произвольный символ.
Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.
В каталоге находится 6 файлов:
maveric.map
maveric.mp3
taverna.mp4
revolver.mp4
vera.mp3
zveri.mp3
Ниже представлено восемь масок. Сколько из них таких, которым соответствуют ровно четыре файла из данного каталога?
*ver*.mp* | *?ver?*.mp? | ?*ver*.mp?* | *v*r*?.m?p* |
???*???.mp* | ???*???.m* | *a*.*a* | *a*.*p* |
Пояснение.
Из таблицы 2 видим, что у Павленко А. К.(ID 2155) два ребенка, их ID: 2302 и 3002.
У Павленко Е. А.(ID 2302) трое детей, а у Павленко И. А.(ID 3002) двое.
Таким образом, у Павленко А. К. семеро прямых потомков: два ребенка и пять внуков.
Ответ: 7.
ИЛИ
Рассмотрим каждую маску:
1. По маске *ver*.mp* будет отобрано пять файлов:
maveric.mp3
taverna.mp4
revolver.mp4
vera.mp3
zveri.mp3
2. По маске *?ver?*.mp? будет отобрано три файла:
maveric.mp3
taverna.mp4
zveri.mp3
3. По маске?*ver*.mp?* будет отобрано четыре файла:
maveric.mp3
taverna.mp4
revolver.mp4
zveri.mp3
4. По маске *v*r*?.m?p* будет отобран один файл:
maveric.map
5. По маске???*???.mp* будет отобрано три файла:
maveric.mp3
taverna.mp4
revolver.mp4
6. По маске???*???.m* будет отобрано четыре файла:
maveric.map
maveric.mp3
taverna.mp4
revolver.mp4
7. По маске *a*.*a* будет отобран один файл:
maveric.map
8. По маске *a*.*p* будет отобрано четыре файла:
maveric.map
maveric.mp3
taverna.mp4
vera.mp3
То есть три маски, которым соответствуют ровно четыре файла из данного каталога.
Ответ: 3.
Ответ: 7|3
5. Задание По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Пояснение.
Буква С не может кодироваться как 0, так как 0 уже занят.
Буква С не может кодироваться как 1, так как кодирование буквы Т начинается с 1.
Буква С не может кодироваться как 10, так как кодирование буквы П начинается с 10.
Буква С не может кодироваться как 11, так как кодирование буквы Т начинается с 11.
Буква С может кодироваться как 101 − это наименьшее возможное значение.
Ответ: 101.
6. Задание На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
А) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
Б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше 125. В ответе это число запишите в десятичной системе счисления.
ИЛИ
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 5.
Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 5.
Например, программа 2121 – это программа
умножь на 5,
прибавь 2,
умножь на 5,
прибавь 2,
которая преобразует число 1 в число 37.
Запишите порядок команд в программе, которая преобразует число 2 в число 24 и содержит не более четырёх команд. Указывайте лишь номера команд.
Пояснение.
Данный алгоритм приписывает в конце числа или 10, если изначально в его двоичной записи было нечетное количество единиц, или 00 если четное.
126 10 = 1111110 2 может получиться в результате работы алгоритма из числа 11111 2 .
11111 2 = 31 10 .
Ответ: 31.
ИЛИ
Решим задачу от обратного, а потом запишем полученные команды справа налево.
Если число не делится на 5, тогда получено через команду 1, если делится, то через команду 2.
22 + 2 = 24(команда 1)
20 + 2 = 22(команда 1)
4 * 5 = 20(команда 2)
2 + 2 = 4(команда 1)
Ответ: 1211.
Ответ: 31|1211
7. Задание. Дан фрагмент электронной таблицы. Из ячейки E4 в ячейку D3 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке D3?
=$B2 * C$3 |
Примечание: знак $ обозначает абсолютную адресацию.
ИЛИ
Дан фрагмент электронной таблицы.
=(A1-3)/(B1-1) | =(A1-3)/(C1-5) | C1/(A1 – 3) |
Какое целое число должно быть записано в ячейке A1, чтобы диаграмма, построенная по значениям ячеек диапазона A2:С2, соответствовала рисунку? Известно, что все значения ячеек из рассматриваемого диапазона неотрицательны.
Пояснение.
Формула, при копировании в ячейку D3 изменилась на =$B1 * B$3.
B1 * B3 = 4 * 2 = 8.
Ответ: 8.
ИЛИ
Подставим значения B1 и C1 в формулы A2:C2:
A2 = (A1-3)/5
B2 = (A1-3)/5
C2 = 10/(A1-3)
Так как A2 = B2, то С2 = 2 * A2 = 2 * B2
Подставим:
10/(A1-3) = 2*(A1-3)/5
A1 - 3 = 5
A1 = 8.
Ответ: 8.
8. Задание Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования.
Бейсик | Python |
DIM S, N AS INTEGER S = 0 N = 0 WHILE S S = S + 8 N = N + 2 WEND PRINT N | s = 0 n = 0 while s s = s + 8 n = n + 2 print(n) |
Алгоритмический язык | Паскаль |
алг нач цел n, s n:= 0 s:= 0 нц пока s s:= s + 8 n:= n + 2 кц вывод n кон | var s, n: integer; begin s:= 0; n:= 0; while s begin s:= s + 8; n:= n + 2 end; writeln(n) end. |
Си |
|
#include int main() { int s = 0, n = 0; while (s printf("%d\n", n); return 0; |
|
Пояснение.
Цикл while выполняется до тех пор, пока истинно условие s
Ответ: 28.
9. Задание. Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 64×64 пикселов при условии, что в изображении могут использоваться 256 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно.
ИЛИ
Музыкальный фрагмент был записан в формате моно, оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла – 24 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате стерео (двухканальная запись) и оцифрован с разрешением в 4 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Укажите размер файла в Мбайт, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно.
Пояснение.
Один пиксель кодируется 8 битами памяти.
Всего 64 * 64 = 2 12 пикселей.
Объем памяти, занимаемый изображением 2 12 * 8 = 2 15 бит = 2 12 байт = 4 Кбайт.
Ответ: 4.
ИЛИ
При записи того же файла в стерео формате его объем увеличивается в 2 раза. 24 * 2 = 48
При увеличении его разрешения в 4 раза его объем также увеличивается в 4 раза. 48 * 4 = 192
При уменьшении частоты дискретизации в 1,5 раза его объем уменьшается в 1,5 раза. 192 / 1,5 = 128.
Ответ: 128.
Ответ: 4|128
10. Задание Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует 5-буквенные слова, в которых есть только буквы П, И, Р, причём буква П появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?
Пояснение.
Игорь может составить 2 4 слов поставив букву П на первое место. Аналогично можно поставить ее на второе, третье, четвертое и пятое место. Получим 5 * 2 4 = 80 слов.
Ответ: 80.
11. Задание Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.
Бейсик | Python |
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) IF n > 0 THEN G(n - 1) END SUB SUB G(n) PRINT "*" IF n > 1 THEN F(n - 3) END SUB | def F(n): If n > 0: G(n - 1) def G(n): Print("*") If n > 1: F(n - 3) |
Алгоритмический язык | Паскаль |
алг F(цел n) нач Если n > 0 то G(n - 1) Все кон алг G(цел n) нач Вывод "*" Если n > 1 то F(n - 3) Все кон | procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin If n > 0 then G(n - 1); end; procedure G(n: integer); begin Writeln("*"); If n > 1 then F(n - 3); end; |
Си |
|
void F(int n); void G(int n); void F(int n){ If (n > 0) G(n - 1); void G(int n){ Printf("*"); If (n > 1) F(n - 3); |
|
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?
Пояснение.
Промоделируем работу программы:
F(11)
G(10): *
F(7)
G(6): *
F(3)
G(2): *
F(-1)
Ответ: 3.
12. Задание В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда – нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.
Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.
Для узла с IP-адресом 111.81.208.27 адрес сети равен 111.81.192.0. Чему равно наименьшее возможное значение третьего слева байта маски? Ответ запишите в виде десятичного числа.
Пояснение.
Запишем третий байт IP-адреса и адреса сети в двоичной системе счисления:
208 10 = 11010000 2
192 10 = 11000000 2
Видим, что два первых слева бита маски − единицы, значит, чтобы значение было наименьшим, остальные биты должны быть нулями. Получаем, что третий слева байт маски равен 11000000 2 = 192 10
Ответ: 192.
13. Задание При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 400 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.
Пояснение.
Согласно условию, в номере могут быть использованы 12 букв. Известно, что с помощью N бит можно закодировать 2N различных вариантов. Поскольку 2 3 4 , то для записи каждого из 12 символов необходимо 4 бита.
Для хранения всех 15 символов пароля нужно 4 · 15 = 60 бит, а т. к. для записи используется целое число байт, то берём ближайшее не меньшее значение, кратное восьми, это число 64 = 8 · 8 бит (8 байт).
Пусть количество памяти, отведенное под дополнительные седения равно x , тогда:
20 * (8+ x ) = 400
x = 12
Ответ: 12.
14. Задание Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка
исполнителя при этом не изменяется.
Цикл
ПОКА условие
Последовательность команд
КОНЕЦ ПОКА
Выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
Выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже
программы к строке, состоящей из 68 идущих подряд цифр 8? В ответе
запишите полученную строку.
НАЧАЛО
ПОКА нашлось (222) ИЛИ нашлось (888)
ЕСЛИ нашлось (222)
ТО заменить (222, 8)
ИНАЧЕ заменить (888, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Пояснение.
В 68 идущих подряд цифрах 8 22 группы по три восьмерки, которые заменятся на 22 двойки и останутся две восьмерки.
68(8) = 22(2) + 2(8)
22(2) + 2(8) = 1(2) + 9(8)
1(2) + 9(8) = 4(2)
4(2) = 1(2) + 1(8) = 28
Ответ: 28.
15. Задание рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М?
Пояснение.
Начнем считать количество путей с конца маршрута - с города М. Пусть N X - количество различных путей из города А в город X, N - общее число путей. В город М можно приехать из Л или K, поэтому N = N М = N Л + N К . (*)
Аналогично:
N К = N И ;
N Л = N И ;
N И = N Е + N Ж + N З
N К = N Е = 1.
Добавим еще вершины:
N Б = N A = 1;
N В = N Б + N А + N Г = 1 + 1 + 1 = 3;
N Е = N Г = 1;
N Г = N A = 1.
Подставим в формулу (*): N = N M = 4 + 4 + 4 + 1 = 13.
Ответ: 13.
Ответ: 56
16. Задание Значение арифметического выражения: 9 8 + 3 5 – 9 – записали в систем счисления с основанием 3. Сколько цифр «2» содержится в этой записи?
Пояснение.
Преобразуем выражение:
(3 2 ) 8 + 3 5 - 3 2
3 16 + 3 5 - 3 2
3 16 + 3 5 = 100...00100000
100...00100000 - 3 2 = 100...00022200
В полученном числе три двойки.
Ответ: 3
17. Задание В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Какое количество страниц (в тысячах) будет найдено по запросу Гомер & Одиссея & Илиада? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время
выполнения запросов.
Пояснение.
Количество запросов в данной области будем обозначать Ni. Наша цель - N5.
Тогда из таблицы находим, что:
N5 + N6 = 355,
N4 + N5 = 200,
N4 + N5 + N6 = 470.
Из первого и второго уравнения: N4 + 2N5 + N6 = 555.
Из последнего уравнения: N5 = 85.
Ответ: 85
18. Задание Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14&5 = 1110 2 &0101 2 = 0100 2 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х )?
Пояснение.
Введем обозначения:
(x ∈ А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.
Преобразовав, получаем:
¬P ∨ ¬(Q ∧ ¬A) ∨ ¬P = ¬P ∨ ¬Q ∨ A.
Логическое ИЛИ истинно, если истинно хотя бы одно утверждение. Условию ¬P ∨ ¬Q = 1 удовлетворяют лучи (−∞, 40) и (60, ∞). Поскольку выражение ¬P ∨ ¬Q ∨ A должно быть тождественно истинным, выражение A должно быть истинно на отрезке . Его длина равна 20.
Ответ: 20.
Ответ: 8
19. Задание В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 4, 7, 3, 8, 5, 0, 1, 2, 9, 6 соответственно, т.е. A = 4, A = 7 и т.д.
Определите значение переменной c после выполнения следующего фрагмента этой программы (записанного ниже на пяти языках программирования) .
Бейсик | Python |
C = 0 FOR i = 1 TO 9 IF A(i) C = c + 1 T = A(i) A(i) = A(0) A(0) = t ENDIF NEXT i | C = 0 For i in range(1,10): If A[i] C = c + 1 t = A[i] A[i] = A A = t |
Алгоритмический язык | Паскаль |
c:= 0 нц для i от 1 до 9 если A[i] c:= c + 1 t:= A[i] A[i] := A A := t все кц | c:= 0; for i:= 1 to 9 do if A[i] begin c:= c + 1; t:= A[i]; A[i] := A; A := t; end; |
Си |
|
c = 0; for (i = 1;i if (A[i] { c++; t = A[i]; A[i] = A; A = t; } |
|
Пояснение.
Если A[i] элемент массива меньше A, то программа меняет их местами и увеличивает значение переменной c на 1. Программа выполнится дважды, первый раз поменяв местами A и A, так как 3 с станет равно 2.
Ответ: 2.
20. Задание Ниже на пяти языках программирования записан алгоритм. Получив на вход число x , этот алгоритм печатает число M . Известно, что x > 100. Укажите наименьшее такое (т.е. большее 100) число x , при вводе которого алгоритм печатает 26.
Бейсик | Python |
DIM X, L, M AS INTEGER INPUT X L = X M = 65 IF L MOD 2 = 0 THEN M = 52 ENDIF WHILE L M IF L > M THEN L = L – M ELSE M = M – L ENDIF WEND PRINT M | x = int(input()) L = x M = 65 if L % 2 == 0: M = 52 while L != M: if L > M: L = L - M else: M = M - L print(M) |
Алгоритмический язык | Паскаль |
алг нач цел x, L, M ввод x L:= x M:= 65 если mod(L,2)=0 то M:= 52 все нц пока L M если L > M то L:= L – M иначе M:= M – L все кц вывод M кон | var x, L, M: integer; begin readln(x); L:= x; M:= 65; if L mod 2 = 0 then M:= 52; while L M do if L > M then L:= L - M else M:= M – L; writeln(M); end. |
Си |
|
#include void main() { int x, L, M; scanf("%d", &x); L = x; M = 65; if (L % 2 == 0) M = 52; while (L != M){ if(L > M) L = L - M; else M = M - L; } printf("%d", M); } |
|
Пояснение.
В теле цикла числа M и L уменьшаются, пока не станут равными. Чтобы в итоге было напечатано 26, оба числа в какой-то момент должны быть равны 26. Пойдем от конца к началу: на предыдущем шаге одно число было 26, а другое 26 + 26 = 52. Еще на шаг раньше 52 + 26 = 78 и 52. До того 78 + 52 = 130 и 52. То есть наименьшее возможное число 130. А поскольку найденное число четное, то M будет присвоено значение 52, что и приведет к необходимому результату.
Ответ: 130.
21. Задание Напишите в ответе наименьшее значение входной переменной k , при котором программа выдаёт тот же ответ, что и при входном значении k = 10. Для Вашего удобства программа приведена на пяти языках программирования.
Бейсик | Python |
DIM K, I AS LONG INPUT K I = 1 WHILE F(I) I = I + 1 WEND PRINT I FUNCTION F(N) F = N * N * N END FUNCTION FUNCTION G(N) G = 2*N + 3 END FUNCTION | def f(n): return n*n*n def g(n): return 2*n+3 k = int(input()) i = 1 while f(i) i+=1 print (i) |
Алгоритмический язык | Паскаль |
алг нач цел i, k ввод k i:= 1 нц пока f(i) i:= i + 1 кц вывод i кон алг цел f(цел n) нач знач:= n * n * n кон алг цел g(цел n) нач знач:= 2*n + 3 кон | var k, i: longint; function f(n: longint): longint; begin f:= n * n * n; end; function g(n: longint): longint; begin g:= 2*n + 3; end; begin readln(k); i:= 1; while f(i) i:= i+1; writeln(i) end. |
Си |
|
#include long f(long n) { return n * n * n; } long g(long n) { return 2*n + 3; } int main() { long k, i; scanf("%ld", &k); i = 1; while(f(i) i++; printf("%ld", i); return 0; } |
|
Пояснение.
Данная программа сравнивает и и прибавляет к i единицу до тех пор, пока . И выводит первое значение переменной i при котором
При k = 10, программа выведет число 3.
Запишем неравенство: отсюда получим, что наименьшее значение k = 3.
Ответ: 3.
22. Задание Исполнитель Май15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
Траектория вычислений программы – это последовательность результатов
выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Пояснение.
Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения для результата.
Все команды увеличивают исходное число, поэтому количество команд не может превосходить (30 − 21) = 9. При этом минимальное количество команд - 3.
Таким образом, команд может быть 3, 4, 5, 6, 7, 8 или 9. Поэтому порядок команд не имеет значения, каждому числу команд соответствует один набор команд, которые можно расположить в любом порядке.
Рассмотрим все возможные наборы и вычислим количество вариантов рассположения команд в них. Набор 133 имеет 3 возможных вариантов расположения. Набор 1223 - 12 возможных вариантов расположения: это число перестановок с повторениями (1+2+1)!/(1! · 2! · 1!)). Набор 12222 - 5 вариантов. Набор 111222 - 20 возможных вариантов. Набор 11123 - 20 вариантов. Набор 111113 - 6 вариантов, набор 1111122 - 21 вариант, набор 11111112 - 8 вариантов, набор 111111111 - один вариант.
Всего имеем 3 + 12 + 5 + 20 + 20 + 6 + 21 + 8 + 1 = 96 программ.
Ответ: 96.
Ответ: 96.
Ответ: 13
23. Задание Сколько существует различных наборов значений логических переменных x 1 , x 2 , ... x 9 , y 1 , y 2 , ... y 9 , которые удовлетворяют всем перечисленным ниже условиям?
(¬ (x 1 ≡ y 1 )) ≡ (x 2 ≡ y 2 )
(¬ (x 2 ≡ y 2 )) ≡ (x 3 ≡ y 3 )
…
(¬ (x 8 ≡ y 8 )) ≡ (x 9 ≡ y 9 )
В ответе не нужно перечислять все различные наборы значений переменных x 1 , x 2 , ... x 9 , y 1 , y 2 , ... y 9 , при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Пояснение.
Из последнего уравнения находим, что возможны три варианта значений x8 и y8: 01, 00, 11. Построим древо вариантов для первой и второй пар значений.
Таким образом, имеем 16 наборов переменных.
Дерево вариантов для пары значений 11:
Получаем 45 вариантов. Таким образом, система будет иметь 45 + 16 = 61 различных наборов решений.
Ответ: 61.
Ответ: 1024
24. Задание На обработку поступает положительное целое число, не превышающее 10 9 . Нужно написать программу, которая выводит на экран сумму цифр этого числа, меньших 7. Если в числе нет цифр, меньших 7, требуется на экран вывести 0. Программист написал программу неправильно. Ниже эта программа для Вашего удобства приведена на пяти языках программирования.
Бейсик | Python |
DIM N, DIGIT, SUM AS LONG INPUT N SUM = 0 WHILE N > 0 DIGIT = N MOD 10 IF DIGIT SUM = SUM + 1 END IF N = N \ 10 WEND PRINT DIGIT | N = int(input()) sum = 0 while N > 0: digit = N % 10 if digit sum = sum + 1 N = N // 10 print(digit) |
Алгоритмический язык | Паскаль |
алг нач цел N, digit, sum ввод N sum:= 0 нц пока N > 0 digit:= mod(N,10) если digit sum:= sum + 1 все N:= div(N,10) кц вывод digit кон | var N, digit, sum: longint; begin readln(N); sum:= 0; while N > 0 do begin digit:= N mod 10; if digit sum:= sum + 1; N:= N div 10; end; writeln(digit) end. |
Си |
|
#include int main() { int N, digit, sum; scanf("%d", &N); sum = 0; while (N > 0) { digit = N % 10; if (digit sum = sum + 1; N = N / 10; } printf("%d",digit); return0; } |
|
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе числа 456.
2. Приведите пример такого трёхзначного числа, при вводе которого программа выдаёт верный ответ.
3. Найдите все ошибки в этой программе (их может быть одна или несколько). Известно, что каждая ошибка затрагивает только одну строку и может быть исправлена без изменения других строк. Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, т.е. приведите правильный вариант строки.
Достаточно указать ошибки и способ их исправления для одного языка программирования. Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.
Пояснение.
Решение использует запись программы на Паскале. Допускается использование программы на любом из четырёх других языков.
1. Программа выведет число 4.
2. Пример числа, при вводе которого программа выдаёт верный ответ: 835.
Замечание для проверяющего. Программа работает неправильно из-за неверной выводимой на экран переменной и неверного увеличения суммы. Соответственно, программа будет работать верно, если в числе старшая цифра (крайняя левая) равна сумме цифр, меньших 7.
3. В программе есть две ошибки.
Первая ошибка. Неверное увеличение суммы.
Строка с ошибкой:
sum:= sum + 1;
Верное исправление:
sum:= sum + digit;
Вторая ошибка. Неверный вывод ответа на экран.
Строка с ошибкой:
writeln(digit)
Верное исправление:
writeln(sum)
25. Задание Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от –10 000 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, в которых хотя бы одно число делится на 3. В данной задаче под парой подразумевается два подряд идущих элемента массива. Например, для массива из пяти элементов: 6; 2; 9; –3; 6 – ответ: 4.
Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.
Бейсик | Python |
CONST N AS INTEGER = 20 DIM A (1 TO N) AS INTEGER DIM I AS INTEGER, J AS INTEGER, K AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I ... END | # допускается также # использовать две # целочисленные переменные j и k a = n = 20 for i in range(0, n): a.append(int(input())) ... |
Алгоритмический язык | Паскаль |
алг нач цел N = 20 целтаб a цел i, j, k нц для i от 1 до N ввод a[i] кц ... кон | const N = 20; var a: array of integer; i, j, k: integer; begin for i:= 1 to N do readln(a[i]); ... end. |
Си | Естественный язык |
#include #define N 20 int main() { int a[N]; int i, j, k; for (i = 0; i scanf("%d", &a[i]); ... return 0; } | Объявляем массив A из 20 элементов. Объявляем целочисленные переменные I, J, K. В цикле от 1 до 20 вводим элементы массива A с 1-го по 20-й. … |
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.6) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
k:= k+1
все
кц
вывод k
Паскаль
k:= 0;
for i:= 1 to N-1 do
if (a[i] mod 3=0) or (a mod 3=0) then
inc(k);
writeln(k);
Си
k = 0;
for (i = 0; i
if (a[i]%3 == 0 || a%3 == 0)
k++;
printf("%d", k);
Естественный язык
Записываем в переменную K начальное значение, равное 0. В цикле от первого элемента до предпоследнего находим остаток от деления текущего и следующего элемента массива на 3. Если первый или второй из полученных остатков равен 0, увеличиваем переменную K на единицу. После завершения цикла выводим значение переменной K
26. Задание Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.
Задание 1. Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
(7,31)
Всего 38
(7,31+1)=(7,32)
Всего 39
(7+1,32)=(8,32)
Всего 40
(8+1,32)=(9,32)
Всего 41
(9,32*2)=(9,64)
Всего 73
(8,32+1)=(8,33)
Всего 41
(8,33*2)=(8,66)
Всего 74
(8*2,32)=(16,32)
Всего 48
(16,32*2)=(16,64)
Всего80
(8,32*2)=(8,64)
Всего 72
(8,64*2)=(8,128)
Всего 136
(7+1,31)=(8,31)
Всего 39
(8,31+1)=(8,32)
Всего 40
(8+1,32)=(9,32)
Всего 41
(9,32*2)=(9,64)
Всего 73
(8,32+1)=(8,33)
Всего41
(8,33*2)=(8,66)
Всего 74
(8*2,32)=(16,32)
Всего 48
(16,32*2)=(16,64)
Всего 80
(8,32*2)=(8,64)
Всего 72
(8,64*2)=(8,128)
Всего 136
(7*2,31)=(14,31)
Всего 45
(14,31*2)=(14,62)
Всего 76
(7,31*2)=(7,62)
Всего 69
(7,62*2)=(7,124)
Всего 131
Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани. При начальной позиции (6, 33) после первого хода Пети может получиться одна из следующих четырёх позиций: (7, 33), (12, 33), (6, 34), (6, 66). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Для позиции (8, 32) после первого хода Пети может получиться одна из следующих четырёх позиций: (9, 32), (16, 32), (8, 33), (8, 64). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Таким образом, Ваня при любом ходе Пети
выигрывает своим первым ходом.
Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети. При начальной позиции (6, 32) он должен первым ходом получить позицию (6, 33), из начальных позиций (7, 32) и (8, 31). Петя после первого хода должен получить позицию (8, 32). Позиции (6, 33) и (8, 32) рассмотрены при разборе задания 1. В этих позициях выигрышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стратегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигрывает своим вторым ходом.
Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани. После первого хода Пети может возникнуть одна из четырёх позиций: (8, 31), (7, 32), (14, 31) и (7, 62). В позициях (14, 31) и (7, 62) Ваня может выиграть одним ходом, удвоив количество камней во второй куче. Позиции (8, 31) и (7, 32) были рассмотрены при разборе задания 2. В этих позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стратегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры Пети Ваня выигрывает на первом или втором ходу.
27. Задание В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 10 000. Все числа не превышают 1000. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным –1.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание – 0 баллов. Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А.
Максимальная оценка за выполнение задания А – 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы
программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла. НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.
Пример входных данных:
11
12
45
5
3
17
23
21
20
19
18
17
Программа должна вывести одно число – описанное в условии произведение либо –1, если получить такое произведение не удаётся.
Пример выходных данных для приведённого выше примера входных данных:
54
Пояснение.
Задание Б (решение для задания А приведено ниже, см. программу 4). Чтобы произведение было чётным, хотя бы один сомножитель должен быть чётным, поэтому при поиске подходящих произведений чётные показания прибора можно рассматривать в паре с любыми другими, а нечётные – только с чётными.
Для каждого показания с номером k, начиная с k = 7, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k – 6. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное – только чётным.
Для получения эффективного по времени решения нужно по мере ввода данных помнить абсолютное минимальное и минимальное чётное показание на каждый момент времени, каждое вновь полученное показание умножать на соответствующий ему минимум, имевшийся на 6 элементов ранее, и выбрать минимальное из всех таких произведений.
Поскольку каждое текущее минимальное показание используется после ввода ещё 6 элементов и после этого становится ненужным, достаточно хранить только 6 последних минимумов. Для этого можно использовать массив из 6 элементов и циклически заполнять его по мере ввода данных. Размер этого массива не зависит от общего количества введённых показаний, поэтому такое решение будет эффективным не только по времени, но и по памяти. Чтобы хранить абсолютный и чётный минимумы, нужно использовать два таких массива. Ниже приводится пример такой программы, написанной на алгоритмическом языке.
Пример 1. Пример правильной программы на алгоритмическом языке. Программа эффективна и по времени, и по памяти.
алг
нач
цел s = 6 | требуемое расстояние между показаниями
цел amax = 1001 | больше максимально возможного показания
цел N
ввод N
цел a | очередное показание прибора
целтаб мини | текущие минимумы последних s элементов
целтаб миничет | чётные минимумы последних s элементов
цел i
| вводим первые s показаний, фиксируем минимумы
цел ма; ма:= amax | минимальное показание
цел мчет; мчет:= amax | минимальное чётное показание
нц для i от 1 до s
ввод а
ма:= imin(ма, a)
мини := ма
миничет := мчет
кц
цел мп = amax*amax | минимальное значение произведения
цел п
нц для i от s+1 до N
ввод а
если mod(a,2)=0
то п:= a * мини
иначе если мчет
то п:= a * миничет
иначе п:= amax*amax;
все
все
мп:= imin(мп, п)
ма:= imin(ма, a)
если mod(a,2) = 0 то мчет:= imin(мчет,a) все
мини := ма
миничет := мчет
кц
если мп = amax*amax то мп:=-1 все
вывод мп
кон
Возможны и другие реализации. Например, вместо циклического заполнения массива можно каждый раз сдвигать его элементы. В приведённом ниже примере хранятся и сдвигаются не минимумы, а исходные значения. Это требует чуть меньше памяти (достаточно одного массива вместо двух), но по времени решение со сдвигами менее эффективно, чем с циклическим заполнением. Однако время работы остаётся пропорциональным N, поэтому максимальная оценка за такое решение тоже составляет 4 балла.
Программа 2. Пример правильной программы на языке Паскаль.
Программа использует сдвиги, но эффективна по времени и по памяти
var
N: integer;
a: array of integer; {хранение s показаний прибора}
a_: integer; {ввод очередного показания}
p: integer;
i, j: integer;
begin
readln(N);
{Ввод первых s чисел}
for i:=1 to s do readln(a[i]);
{Ввод остальных значений, поиск минимального произведения}
ma:= amax; me:= amax;
mp:=amax*amax;
for i:= s + 1 to N do begin
readln(a_);
if a
if (a mod 2 = 0) and (a
if a_ mod 2 = 0 then p:= a_ * ma
else if me
else p:= amax* amax;
if (p
{сдвигаем элементы вспомогательного массива влево}
for j:= 1 to s - 1 do
a[j] := a;
a[s] := a_
end;
if mp = amax*amax then mp:=-1;
writeln(mp)
end.
Если вместо небольшого массива фиксированного размера (циклического или со сдвигами) хранятся все исходные данные (или все текущие минимумы), программа сохраняет эффективность по времени, но становится неэффективной по памяти, так как требуемая память растёт пропорционально N. Ниже приводится пример такой программы на языке Паскаль. Подобные (и аналогичные по сути) программы оцениваются не выше 3 баллов.
Программа 3. Пример правильной программы на языке Паскаль. Программа эффективна по времени, но неэффективна по памяти
const s = 6; {требуемое расстояние между показаниями}
amax = 1001; {больше максимально возможного показания}
var
N, p, i: integer;
ma: integer; {минимальное число без s последних}
me: integer; {минимальное чётное число без s последних}
mp: integer; {минимальное значение произведения}
begin
readln(N);
{Ввод всех показаний прибора}
for i:=1 to N do readln(a[i]);
ma:= amax;
me:= amax;
mp:= amax*amax;
for i:= s + 1 to N do
begin
if a
if (a mod 2 = 0) and (a
me:= a;
if a[i] mod 2 = 0 then p:= a[i] * ma
else if me
else p:= amax * amax;
if (p
end;
if mp = amax*amax then mp:= -1;
writeln(mp)
end.
Возможно также переборное решение, в котором находятся произведения всех возможных пар и из них выбирается минимальное. Ниже (см. программу 4) приведён пример подобного решения. Это (и аналогичные ему) решение неэффективно ни по времени, ни по памяти. Оно является решением задания А, но не является решением задания Б. Оценка за такое решение – 2 балла.
Программа 4. Пример правильной программы на языке Паскаль. Программа неэффективна ни по времени, ни по памяти
const s = 6; {требуемое расстояние между показаниями}
var
N: integer;
a: array of integer; {все показания прибора}
mp: integer; {минимальное значение произведения}
i, j: integer;
begin
readln(N);
{Ввод значений прибора}
for i:=1 to N do
readln(a[i]);
mp:= 1000 * 1000 + 1;
for i:= 1 to N-s do begin
for j:= i+s to N do begin
if (a[i]*a[j] mod 2 = 0) and (a[i]*a[j]
then mp:= a[i]*a[j]
end;
end;
if mp = 1000 * 1000 + 1 then mp:= -1;
writeln(mp)
СПЕЦИФИКАЦИЯ
контрольных измерительных материалов
единого государственного экзамена 2016 года
по информатике и ИКТ
1. Назначение КИМ ЕГЭ
Единый государственный экзамен (далее - ЕГЭ) представляет собой форму объективной оценки качества подготовки лиц, освоивших образовательные программы среднего общего образования, с использованием заданий стандартизированной формы (контрольных измерительных материалов).
ЕГЭ проводится в соответствии с Федеральным законом от 29.12.2012 № 273-ФЗ «Об образовании в Российской Федерации».
Контрольные измерительные материалы позволяют установить уровень освоения выпускниками Федерального компонента государственного стандарта среднего (полного) общего образования по информатике и ИКТ, базовый и профильный уровни.
Результаты единого государственного экзамена по информатике и ИКТ признаются образовательными организациями среднего профессионального образования и образовательными организациями высшего профессионального образования как результаты вступительных испытаний по информатике и ИКТ.
2. Документы, определяющие содержание КИМ ЕГЭ
3. Подходы к отбору содержания, разработке структуры КИМ ЕГЭ
Содержание заданий разработано по основным темам курса информатики и ИКТ, объединенных в следующие тематические блоки: «Информация и ее кодирование», «Моделирование и компьютерный эксперимент», «Системы счисления», «Логика и алгоритмы», «Элементы теории алгоритмов», «Программирование», «Архитектура компьютеров и компьютерных сетей», «Обработка числовой информации», «Технологии поиска и хранения информации».
Содержанием экзаменационной работы охватывается основное содержание курса информатики и ИКТ, важнейшие его темы, наиболее значимый в них материал, однозначно трактуемый в большинстве преподаваемых в школе вариантов курса информатики и ИКТ.
Работа содержит как задания базового уровня сложности, проверяющие знания и умения, предусмотренные стандартом базового уровня, так
и задания повышенного и высокого уровней сложности, проверяющие знания и умения, предусмотренные стандартом профильного уровня. Количество заданий в варианте КИМ должно, с одной стороны, обеспечить всестороннюю проверку знаний и умений выпускников, приобретенных за весь период обучения по предмету, и, с другой стороны, соответствовать критериям сложности, устойчивости результатов, надежности измерения. С этой целью в КИМ используются задания двух типов: с кратким ответом и развернутым ответом. Структура экзаменационной работы обеспечивает оптимальный баланс заданий разных типов и разновидностей, трех уровней сложности, проверяющих знания и умения на трех различных уровнях: воспроизведения, применения в стандартной ситуации, применения в новой ситуации. Содержание экзаменационной работы отражает значительную часть содержания предмета. Все это обеспечивает валидность результатов тестирования и надежность измерения.
4. Структура КИМ ЕГЭ
Каждый вариант экзаменационной работы состоит из двух частей и включает в себя 27 заданий, различающихся формой и уровнем сложности.
Часть 1 содержит 23 задания с кратким ответом.
В экзаменационной работе предложены следующие разновидности заданий с кратким ответом:
- задания на выбор и запись одного или нескольких правильных ответов из предложенного перечня ответов;
- задания на вычисление определенной величины;
- задания на установление правильной последовательности, представленной в виде строки символов по определенному алгоритму.
Ответ на задания части 1 дается соответствующей записью в виде натурального числа или последовательности символов (букв и цифр), записанных без пробелов и других разделителей.
Часть 2 содержит 4 задания с развернутым ответом.
Часть 1 содержит 23 задания базового, повышенного и высокого уровней сложности. В этой части собраны задания с кратким ответом, подразумевающие самостоятельное формулирование и запись ответа в виде числа или последовательности символов. Задания проверяют материал всех тематических блоков. В части 1 12 заданий относится к базовому уровню, 10 заданий к повышенному уровню сложности, 1 задание - к высокому уровню сложности.
Часть 2 содержит 4 задания, первое из которых повышенного уровня сложности, остальные 3 задания высокого уровня сложности. Задания этой части подразумевают запись развернутого ответа в произвольной форме.