Тренировочные ким егэ по информатике. B21: циклы и процедуры
Подписаться
В России полным ходом идет процесс подачи заявлений на ЕГЭ. О всех особенностях процесса и крайней дате подачи, а также кто имеет право подать заявления после крайней даты в данной публикации.
По всей стране стартовал прием заявлений на участие в ЕГЭ 2018-го года. Заявление должны подать выпускники 2018, а также другие категории людей, которые хотят сдать его по каким-либо причинам. После ознакомления со статьей рекомендуем посмотреть расписание ЕГЭ 2018, ответы на самые популярные вопросы о Едином государственном экзамене, минимальные баллы. А также подобрать специальность и ВУЗ по ЕГЭ.
Заявление на участие в ЕГЭ должно быть подано не позже, чем 1 февраля 2018-го года. После этой даты вы можете подать заявление лишь в том случае, если у вас была уважительная причина, которая не позволила подать его в установленный срок. Решение о принятии заявлений после 1-го февраля выносит специально государственная комиссия.
СПЕЦИФИКАЦИЯ
контрольных измерительных материалов
единого государственного экзамена 2016 года
по информатике и ИКТ
1. Назначение КИМ ЕГЭ
Единый государственный экзамен (далее - ЕГЭ) представляет собой форму объективной оценки качества подготовки лиц, освоивших образовательные программы среднего общего образования, с использованием заданий стандартизированной формы (контрольных измерительных материалов).
ЕГЭ проводится в соответствии с Федеральным законом от 29.12.2012 № 273-ФЗ «Об образовании в Российской Федерации».
Контрольные измерительные материалы позволяют установить уровень освоения выпускниками Федерального компонента государственного стандарта среднего (полного) общего образования по информатике и ИКТ, базовый и профильный уровни.
Результаты единого государственного экзамена по информатике и ИКТ признаются образовательными организациями среднего профессионального образования и образовательными организациями высшего профессионального образования как результаты вступительных испытаний по информатике и ИКТ.
2. Документы, определяющие содержание КИМ ЕГЭ
3. Подходы к отбору содержания, разработке структуры КИМ ЕГЭ
Содержание заданий разработано по основным темам курса информатики и ИКТ, объединенных в следующие тематические блоки: «Информация и ее кодирование», «Моделирование и компьютерный эксперимент», «Системы счисления», «Логика и алгоритмы», «Элементы теории алгоритмов», «Программирование», «Архитектура компьютеров и компьютерных сетей», «Обработка числовой информации», «Технологии поиска и хранения информации».
Содержанием экзаменационной работы охватывается основное содержание курса информатики и ИКТ, важнейшие его темы, наиболее значимый в них материал, однозначно трактуемый в большинстве преподаваемых в школе вариантов курса информатики и ИКТ.
Работа содержит как задания базового уровня сложности, проверяющие знания и умения, предусмотренные стандартом базового уровня, так
и задания повышенного и высокого уровней сложности, проверяющие знания и умения, предусмотренные стандартом профильного уровня. Количество заданий в варианте КИМ должно, с одной стороны, обеспечить всестороннюю проверку знаний и умений выпускников, приобретенных за весь период обучения по предмету, и, с другой стороны, соответствовать критериям сложности, устойчивости результатов, надежности измерения. С этой целью в КИМ используются задания двух типов: с кратким ответом и развернутым ответом. Структура экзаменационной работы обеспечивает оптимальный баланс заданий разных типов и разновидностей, трех уровней сложности, проверяющих знания и умения на трех различных уровнях: воспроизведения, применения в стандартной ситуации, применения в новой ситуации. Содержание экзаменационной работы отражает значительную часть содержания предмета. Все это обеспечивает валидность результатов тестирования и надежность измерения.
4. Структура КИМ ЕГЭ
Каждый вариант экзаменационной работы состоит из двух частей и включает в себя 27 заданий, различающихся формой и уровнем сложности.
Часть 1 содержит 23 задания с кратким ответом.
В экзаменационной работе предложены следующие разновидности заданий с кратким ответом:
- задания на выбор и запись одного или нескольких правильных ответов из предложенного перечня ответов;
- задания на вычисление определенной величины;
- задания на установление правильной последовательности, представленной в виде строки символов по определенному алгоритму.
Ответ на задания части 1 дается соответствующей записью в виде натурального числа или последовательности символов (букв и цифр), записанных без пробелов и других разделителей.
Часть 2 содержит 4 задания с развернутым ответом.
Часть 1 содержит 23 задания базового, повышенного и высокого уровней сложности. В этой части собраны задания с кратким ответом, подразумевающие самостоятельное формулирование и запись ответа в виде числа или последовательности символов. Задания проверяют материал всех тематических блоков. В части 1 12 заданий относится к базовому уровню, 10 заданий к повышенному уровню сложности, 1 задание - к высокому уровню сложности.
Часть 2 содержит 4 задания, первое из которых повышенного уровня сложности, остальные 3 задания высокого уровня сложности. Задания этой части подразумевают запись развернутого ответа в произвольной форме.
К.Ю. ПоляковЕГЭ по информатике:
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
