Подготовка к ЕГЭ по информатике. Решение задач по программированию

Дмитрий Златопольский

Подготовка к ЕГЭ  
по информатике

Решение задач по программированию

Москва, 2018

УДК 373.167.1:004+004(075.3)
ББК 32.97я72

З67

Златопольский Д. М.

З67 
Подготовка к ЕГЭ по информатике. Решение задач по программированию. – М.: ДМК Пресс, 2017. – 252 с.: ил.

ISBN 978-5-97060-598-1

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

Издание также будет полезно студентам вузов и колледжей, пре
подавателям информатики и другим читателям при изучении программирования вне связи с ЕГЭ.

УДК 373.167.1:004+004(075.3)
ББК 32.97я72

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

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

 
© Златопольский Д.М., 2017

ISBN 978-5-97060-598-1 
© Издание, оформление, ДМК Пресс, 2018

Содержание

Предисловие ..................................................................................... 8

Глава 1. Вспомогательные задачи .................................................. 9

1.1. Обработка натурального числа ............................................... 10

1.1.1. Выделение цифр ............................................................... 10
1.1.2. Определение суммы цифр числа .................................... 11
1.1.3. Определение произведения цифр числа ........................ 12
1.1.4. Определение количества цифр числа ............................. 13
1.1.5. Определение максимальной цифры числа .................... 13
1.1.6. Определение минимальной цифры числа ..................... 15

1.2. Операции с элементами массива, отобранными  
по некоторому условию .................................................................. 15

1.2.1. Изменение элементов массива с заданными  
свойствами (удовлетворяющих некоторому условию) ............ 15
1.2.2. Нахождение суммы элементов массива с заданными свойствами (удовлетворяющих некоторому условию) ...... 16
1.2.3. Нахождение количества элементов массива  
с заданными свойствами ........................................................... 18
1.2.4. Нахождение среднего арифметического значения  
элементов массива с заданными свойствами .......................... 19
1.2.5. Нахождение максимального количества подряд  
идущих элементов массива, обладающих заданными  
свойствами .................................................................................. 20
1.2.6. Нахождение максимальной суммы подряд идущих  
элементов массива, обладающих заданными свойствами...... 23

1.3. Линейный поиск элемента ...................................................... 26

1.3.1. Проверка факта наличия в массиве элемента  
с заданным значением ............................................................... 26
1.3.2. Проверка факта наличия в массиве элемента  
с заданными свойствами ........................................................... 29
1.3.3. Поиск индекса элемента массива, равного  
некоторому числу ....................................................................... 30
1.3.4. Поиск индекса элемента массива с заданными  
свойствами .................................................................................. 31

Содержание

1.3.5. Поиск индекса первого элемента массива, равного  
некоторому числу ....................................................................... 31
1.3.6. Поиск индекса первого элемента массива  
с заданными свойствами ........................................................... 33

1.4. Задачи на нахождение максимальных (минимальных)  
элементов массива, их индексов, количеств и т. п. ....................... 33

1.4.1. Определение максимального элемента массива ........... 33
1.4.2. Определение минимального элемента массива ............ 35
1.4.3. Определение индекса максимального элемента  
массива ........................................................................................ 35
1.4.4. Нахождение индекса минимального элемента ............. 37
1.4.5. Нахождение минимального (максимального)  
элемента массива и количества элементов, равных ему ......... 38
1.4.6. Нахождение количества минимальных элементов ....... 40
1.4.7. Определение минимального значения среди тех  
элементов массива, которые удовлетворяют некоторому  
условию ....................................................................................... 40
1.4.8. Определение индекса минимального элемента  
среди элементов массива, которые удовлетворяют  
некоторому условию .................................................................. 44
1.4.9. Нахождение второго по величине максимального  
элемента ...................................................................................... 45
1.4.9.1. Поиск элемента массива, который стоял бы  
на предпоследнем месте, если бы массив был  
отсортирован по неубыванию ................................................... 45
1.4.10. Нахождение второго минимума ................................... 49

1.5. Разные задачи .......................................................................... 50

1.5.1. Обмен значениями переменных величин ..................... 50
1.5.2. Обмен значениями двух элементов массива  ................ 51
1.5.3. Перестановка всех элементов массива в обратном  
порядке ........................................................................................ 51
1.5.4. Рассмотрение всех вариантов сочетания  
по одному элементу из нескольких наборов ............................ 53

Глава 2. Задания 11 ........................................................................ 55

2.1. Задание из [2] ........................................................................... 58
2.2. Задание из [3] ........................................................................... 59

Содержание
5

2.3. Задание из [6] ........................................................................... 62
2.4. Задание из [4] ........................................................................... 64
2.5. Задание из [10] .......................................................................... 67
2.6. Задание из [5] ........................................................................... 70
2.7. Задание из [7]* .......................................................................... 73

Глава 3. Задания 20 ........................................................................ 78

3.1. Задание из [3] ........................................................................... 79
3.2. Задание из [2] ........................................................................... 80
3.3. Задание из [6] ........................................................................... 81
3.4. Задание из [3] ........................................................................... 83
3.5. Задание из [7]* .......................................................................... 84

Глава 4. Задания 21 ........................................................................ 89

4.1. Задание из [13] .......................................................................... 90
4.2. Задание из [5] ........................................................................... 92
4.3. Задание из [6] ........................................................................... 94
4.4. Задание из [1] ........................................................................... 97
4.5. Задание из [2] ......................................................................... 100
4.6. Задание из [3] ......................................................................... 101
4.7. Задание из [7]* ........................................................................ 102
4.8. Задание из [11] ........................................................................ 104
4.9. Задание из [4] ......................................................................... 106
4.10. Задание из [10] ...................................................................... 110

Глава 5. Задания 24 ...................................................................... 115

5.1. Задание из [3] ......................................................................... 116
5.2. Задание из [5] ......................................................................... 119
5.3. Задание из [4] ......................................................................... 122
5.4. Задание из [10] ........................................................................ 126
5.5. Задание из [7]* ........................................................................ 130
5.6. Задание из [6] ......................................................................... 133

Глава 6. Задания 25 ...................................................................... 143

6.1. Задание варианта 3 из [12] .................................................... 144
6.2. Задание варианта 4 из [12] .................................................... 146

Содержание

6.3. Задание варианта 1 из [11] .................................................... 146
6.4. Задание варианта 1 из [12] .................................................... 147
6.5. Задание варианта 9 из [12] .................................................... 148
6.6. Задание варианта 10 из [12]  .................................................. 150
6.7. Задание из [2] .......................................................................... 150
6.8. Задание варианта 8 [13] ......................................................... 151
6.9. Задание из [7]* ........................................................................ 153
6.10. Задание варианта 5 из [12] .................................................. 154
6.11. Задание из [1] ........................................................................ 155
6.12. Задание из [11] ...................................................................... 156
6.13. Задание из [6]  ....................................................................... 156
6.14. Задание из [5] ........................................................................ 157
6.15. Задание из [4] ........................................................................ 157
6.16. Задание варианта 10 из [13] ................................................. 158
6.17. Задание варианта 2 из [12] ................................................... 159
6.18. Задание варианта 7 из [12] .................................................. 161
6.19. Задание из [3]  ....................................................................... 162
6.20. Задание варианта 2 из [13]  .................................................. 164
6.21. Задание варианта 6 из [13]  .................................................. 167
6.22. Задание варианта 7 из [13]  .................................................. 169
6.23. Задание варианта 5 из [13]  .................................................. 171
6.24. Задание варианта 3 из [13]  .................................................. 175
6.25. Задание варианта 6 из [12]  .................................................. 177
6.26. Задание варианта 8 из [12]  .................................................. 179
6.27. Задание варианта 4 из [13]  .................................................. 179

Глава 7. Задания 27 ....................................................................... 182

7.1. Задание из [1] .......................................................................... 183

7.1.1. Определение того факта, что некоторая  
решенная задача уже имеется в списке ранее введенных  
задач (в массиве задачи) .......................................................... 185
7.1.2. Заполнение массива задачи неповторяющимися  
значениями ............................................................................... 186
7.1.3. Заполнение массива задачи неповторяющимися  
значениями и определение «встречаемости» (количества 
вхождений) каждой задачи ...................................................... 187

Содержание
7

7.1.4. Сортировка массива кол_задач в порядке  
невозрастания (и соответственно ей – изменение  
массива задачи) ........................................................................ 188

7.2. Задание из [2] .......................................................................... 190
7.3. Задание из [3] .......................................................................... 195
7.4. Задание из [4] .......................................................................... 202
7.5. Задание из [5] .......................................................................... 214
7.6. Задание из [6] .......................................................................... 215
7.7. Задание из [7]* ......................................................................... 221

Приложение 1. Задания на определение значений  
переменных величин ................................................................... 225

П1.1. Задания, связанные с линейным алгоритмом .................. 226
П1.2. Задания, связанные с разветвляющимся алгоритмом ..... 226
П1.3. Задания, связанные с циклическим алгоритмом ............. 228
П1.4. Задания на заполнение и изменение одномерного  
массива ........................................................................................... 231
П1.5. Задания на обработку одномерного массива .................... 233
П1.6. Задания на заполнение двух массивов .............................. 234
П1.7. Задания на заполнение и изменение двумерного  
массива ........................................................................................... 235

Приложение 2. Сортировка массива методом обмена ............ 245

Список литературы ....................................................................... 250

Предисловие

На Едином государственном экзамене по информатике и ИКТ задания, 
связанные с программированием, занимают важное место. Так, в демонстрационном варианте экзамена 2018 года их 8 при общем числе 
заданий 27. При этом высока весомость заданий (максимальный балл 
за выполнение заданий части 2 равен 3–4). Это говорит о том, что от 
умения решать задачи по программированию в значительной степени 
зависит успешность сдачи ЕГЭ в целом.
В то же время, как показывает опыт, такие задачи часто вызывают 
у школьников заметные трудности, особенно задачи части 2 экзамена. 
В большой степени это связано с недостаточным числом часов, отводимых на изучение программирования в школе.
Данная книга должна восполнить этот недостаток – помочь учащимся подготовиться к экзамену самостоятельно. В ней системно, подробно 
и доступно описана методика выполнения заданий по программированию, встречающихся на ЕГЭ.
Сначала в главе 1 рассмотрены все частные, вспомогательные задачи, 
умение решать которые позволит успешно выполнить задания экзамена 
по программированию, после чего в главах 2–7 описана методика выполнения заданий из ЕГЭ. В приложениях приведены другие материалы, 
связанные с заданиями по программированию на ЕГЭ.
При разработке программ (частных и из заданий ЕГЭ) использован школьный алгоритмический язык. Русский синтаксис этого языка 
и большое число комментариев сделают программы максимально понятными и легко переносимыми на любой другой язык программирования. Это означает, что книга может быть использована читателями, 
владеющими любым языком программирования. В большинстве случаев 
после разбора методики решения и программы на школьном алгоритмическом языке приводятся также соответствующие программы на популярном среди школьников языке Паскаль. Предлагаются задания для 
самостоятельной работы. 
Обратим внимание на широкое использование в книге задач от разработчиков контрольно-измерительных материалов для ЕГЭ [11–13] – существует большая вероятность того, что подобные задачи будут включены в экзамен в будущем.
Кроме учащихся, готовящихся к сдаче экзамена самостоятельно, книгу могут использовать учителя и преподаватели информатики, а также 
студенты и учащиеся, изучающие программирование вне связи с ЕГЭ.

Глава 1 
Вспомогательные 
задачи

Вспомогательные задачи

В данной главе рассмотрена методика решения задач, предусмотренных Кодификатором элементов содержания и требований 
к уровню подготовки выпускников общеобразовательных учреждений для проведения в 2018 году единого государственного 
экзамена по информатике и ИКТ [7], которые используются в демонстрационных вариантах ЕГЭ по информатике последних лет, 
а также в книгах от разработчиков ЕГЭ [11–13].

1.1. Обработка натурального числа

1.1.1. Выделение цифр

Задача формулируется так: «Дано натуральное число n. Вывести его цифры в “столбик”».
Решение
Когда количество цифр в заданном числе известно, можно выделить любую его цифру. Но в данном случае это количество неизвестно. Поэтому подумаем над вопросом – какую цифру целого 
числа (см. схему ниже) определить можно?

первая
вторая
…
предпоследняя
последняя
цифры числа

Ответ – последнюю (последняя цифра любого натурального числа равна остатку от деления этого числа на 10 – убедитесь в этом!):

посл = mod(n, 10) |посл - последняя цифра числа n 

где mod – функция школьного алгоритмического языка, возвращающая остаток от деления своего первого аргумента на второй 
(в других языках программирования для этого используется не 
функция, а специальная операция).
А остальные цифры? Как, например, определить предпоследнюю цифру? Ее можно найти только так: получить число без последней цифры исходного числа (разделив исходное нацело на 
10) и для него определить последнюю цифру.
Аналогично можно получить и предпредпоследнюю, и остальные цифры. 
Следовательно, для решения задачи в программе надо многократно выполнить следующие действия:
1)  определить последнюю цифру числа;
2) вывести ее на экран; 
3) получить число без последней цифры. 

Обработка натурального числа
11

Соответствующий фрагмент программы:

нц пока n > 0:
    посл := mod(n, 10)
    вывод нс, посл
    n := div(n, 10)
кц

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

Язык Паскаль

while n > 0 do
  begin:
    posl := n mod 10;
    writeln(posl);
    n := n div 10
  end;

1.1.2. Определение суммы цифр числа

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

вывод нс, "Введите натуральное число "
ввод n
сум := 0 |Начальное значение суммы цифр
нц пока n > 0
  посл := mod(n, 10)
  сум := сум + посл
  n := div(n, 10)
кц
вывод нс, "Сумма цифр этого числа равна ", сум

Язык Паскаль

write('Введите натуральное число ');
readln(n);
sum := 0; 

Вспомогательные задачи

while n > 0 do
  begin
    posl := n mod 10;
    sum := sum + posl;
    n := n div 10
  end;
writeln('Сумма цифр этого числа равна ', sum);

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

sum := 0; 

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

1.1.3. Определение произведения цифр числа

Задача решается аналогично предыдущей. Отличия:
1)  рассчитывается не сумма, а произведение цифр;
2)  начальное значение искомой величины произв должно быть 
принято равным 1.
Программа:

вывод нс, "Введите натуральное число "
ввод n
произв := 1 |Начальное значение 
нц пока n > 0
  посл := mod(n, 10)
  произв := произв * посл
  n := div(n, 10)
кц
вывод нс, "Произведение цифр этого числа равно ", произв

Язык Паскаль

write('Введите натуральное число ');
readln(n);
proizv := 1; 
while n > 0 do
  begin
    posl := n mod 10;
    proizv := proizv * posl;
    n := n div 10
  end;
writeln('Произведение цифр этого числа равно ', proizv);

Обработка натурального числа
13

1.1.4. Определение количества цифр числа

Здесь следует использовать переменную-«счетчик» количества 
уже «обработанных» цифр:

вывод нс, "Введите натуральное число "
ввод n
кол := 0 |Начальное значение количества цифр
нц пока n > 0
  посл := mod(n, 10)
  кол := кол + 1
  n := div(n, 10)
кц
вывод нс, "Количество цифр этого числа равно ", кол

Обратим внимание на то, что последнюю цифру посл можно 
не определять.

Язык Паскаль

write('Введите натуральное число ');
readln(n);
kol := 0; 
while n > 0 do
  begin
    kol := kol + 1;
    n := n div 10
  end;
writeln('Количество цифр этого числа равно ', kol);

Здесь также присваивание начального значения, равного нулю, 
является обязательным (см. п. 1.1.2).

1.1.5. Определение максимальной цифры числа

Алгоритм решения этой задачи аналогичен алгоритму действий человека, который определяет максимальную цифру в некотором числе:

324086312

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

Вспомогательные задачи

В приведенной далее программе искомое максимальное значение хранит переменная макс.

вывод нс, "Введите натуральное число "
ввод n
посл := mod(n, 10) |Выделяем последнюю цифру
макс := посл       |Принимаем ее в качестве максимальной
n := div(n, 10)    |Отбрасываем последнюю цифру
|Рассматриваем остальные цифры
нц пока n > 0
  посл := mod(n, 10) |Выделяем 
  если посл > макс   |Сравниваем
   то                |и при необходимости
     макс := посл    |меняем значение макс
  все
  n := div(n, 10)
кц
вывод нс, "Максимальная цифра заданного числа равна ", макс

В данном случае (см. п. 1.4.1) отдельно последнюю цифру можно не выделять, так как можно в качестве начального значения 
переменной макс принять 0: 

вывод нс, "Введите натуральное число "
ввод n
макс := 0
|Рассматриваем все цифры
нц пока n > 0
  посл := mod(n, 10) 
  если посл > макс 
    то 
      макс := посл 
  все
  n := div(n, 10)
кц
вывод нс, "Максимальная цифра заданного числа равна ", макс

Язык Паскаль

write('Введите натуральное число ');
readln(n);
max := 0; 
while n > 0 do
  begin
    posl := n mod 10;
    if posl > max then
      max := posl;
    n := n div 10
  end;
writeln('Максимальная цифра заданного числа равна ', max);

Операции с элементами массива, отобранными по некоторому условию
15

1.1.6. Определение минимальной цифры числа

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

1.2.  Операции с элементами массива, 
отобранными по некоторому условию1

Для каждой рассмотренной задачи в данном разделе приведен 
фрагмент программы ее решения на школьном алгоритмическом 
языке и на языке Паскаль. Использованы следующие основные 
величины:

 
z а – имя массива; 

 
z n – общее количество элементов массива (условно принято, 
что нумерация элементов массива начинается с 1).
Смысл остальных величин можно легко определить по их именам.
Принято, что элементы массива имеют целые значения.

1.2.1.  Изменение элементов массива 
с заданными свойствами (удовлетворяющих 
некоторому условию)

Общая формулировка задач рассматриваемого типа: «Все элементы массива с заданными свойствами заменить на …», где 
вместо многоточия указывается конкретное значение, на которое 
следует заменить указанные элементы, или правило, по которому 
надо провести замену.

Примеры задач
1.  Дан массив целых чисел. Все четные элементы заменить 
числом 666.
2.  Дан массив чисел, среди которых есть отрицательные. Все 
отрицательные элементы уменьшить на 10.
3.  Дан массив целых чисел. Все элементы с нечетным индексом, оканчивающиеся цифрой 5, увеличить на 1.

1 Такая формулировка приведена в Кодификаторе элементов содержания 
и требований к уровню подготовки выпускников общеобразовательных учреждений для проведения в 2018 году единого государственного экзамена по 
информатике и ИКТ [7].