Подготовка к ЕГЭ по информатике в 2020 году. Решение задач по программированию
Покупка
Тематика:
Педагогика общего среднего образования
Издательство:
ДМК Пресс
Год издания: 2020
Кол-во страниц: 266
Дополнительно
Вид издания:
Учебно-методическая литература
Уровень образования:
Среднее общее образование
ISBN: 978-5-97060-829-6
Артикул: 748331.01.99
Книга предназначена для подготовки учащихся к Единому государственному экзамену по информатике в части решения задач по программированию. Рассмотрена методика решения основных типовых задач по программированию, а также заданий из демонстрационных вариантов ЕГЭ и из пособий, написанных разработчиками контрольно-измерительных материалов по информатике.
Издание также будет полезно студентам вузов и колледжей, преподавателям информатики и другим читателям при изучении программирования вне связи с ЕГЭ.
Тематика:
ББК:
УДК:
- 004: Информационные технологии. Вычислительная техника...
- 373: Дошкольное воспитание и образование. Общее школьное образование. Общеобразовательная школа
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
Дмитрий Златопольский Подготовка к ЕГЭ по информатике в 2020 году Решение задач по программированию Москва, 2020
УДК 373.167.1:004+004(075.3) ББК 32.97я72 З67 Златопольский Д. М. З67 Подготовка к ЕГЭ по информатике в 2020 году. Решение задач по программированию. – М.: ДМК Пресс, 2020. – 266 с.: ил. ISBN 978-5-97060-829-6 Книга предназначена для подготовки учащихся к Единому государственному экзамену по информатике в части решения задач по программированию. Рассмотрена методика решения основных типовых задач по программированию, а также заданий из демонстрационных вариантов ЕГЭ и из пособий, написанных разработчиками контрольно-измерительных материалов по информатике. Издание также будет полезно студентам вузов и колледжей, преподавателям информатики и другим читателям при изучении программирования вне связи с ЕГЭ. УДК 373.167.1:004+004(075.3) ББК 32.97я72 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. © Златопольский Д., 2020 ISBN 978-5-97060-829-6 © Издание, оформление, ДМК Пресс, 2020
Содержание Содержание Предисловие ..................................................................................... 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.10. Нахождение второго минимума ................................... 49 1.5. Разные задачи .......................................................................... 50 1.5.1. Обмен значениями переменных величин ..................... 50 1.5.2. Обмен значениями двух элементов массива ................ 51 1.5.3. Перестановка всех элементов массива в обратном порядке .................................................................... 51 1.5.4. Рассмотрение всех вариантов сочетания по одному элементу из нескольких наборов ............................ 53 1.5.5. Вставка значения в массив со сдвигом элементов влево ............................................................................................ 54 Глава 2. Задания 11 ........................................................................56 2.1. Задание из [9]* ........................................................................... 61 2.2. Задание из [7] ............................................................................ 62 2.3. Задание из [3] ............................................................................ 64 2.3. Задание из [5] ............................................................................ 64
Содержание 5 Глава 3. Задания 20 ........................................................................67 3.1. Задание из [3] ........................................................................... 68 3.2. Задание из [6] ........................................................................... 69 3.3. Задание из [3] ........................................................................... 71 3.4. Задание из [7] ........................................................................... 72 3.5. Задание из [9]* ........................................................................... 74 3.6. Задание из [8] ............................................................................ 76 Глава 4. Задания 21 ........................................................................81 4.1. Задание из [15] .......................................................................... 82 4.2. Задание из [5] ........................................................................... 84 4.3. Задание из [6] ........................................................................... 86 4.4. Задание из [1] ........................................................................... 89 4.5. Задание из [2] ........................................................................... 91 4.6. Задание из [3] ........................................................................... 93 4.7. Задание из [7] ............................................................................ 94 4.8. Задание из [8] ........................................................................... 95 4.9. Задание из [9]* ........................................................................... 97 4.10. Задание из [13] ........................................................................ 99 4.11. Задание из [4] ....................................................................... 101 4.12. Задание из [12] ...................................................................... 105 Глава 5. Задания 24 ......................................................................110 5.1. Задание из [3] ......................................................................... 111 5.2. Задание из [5] ......................................................................... 114 5.3. Задание из [4] ......................................................................... 117 5.4. Задание из [12] ........................................................................ 121 5.5. Задание из [9]* ........................................................................ 125 5.6. Задание из [7] ......................................................................... 129 5.7. Задание из [6] .......................................................................... 132 Глава 6. Задания 25 ......................................................................142 6.1. Задание варианта 3 из [14] .................................................... 143 6.2. Задание варианта 4 из [14] .................................................... 145 6.3. Задание варианта 1 из [13] .................................................... 145 6.4. Задание варианта 1 из [14] .................................................... 146
Содержание 6.5. Задание варианта 9 из [14] .................................................... 147 6.6. Задание варианта 10 из [14] .................................................. 149 6.7. Задание из [2] .......................................................................... 149 6.8. Задание варианта 8 из [15] .................................................... 150 6.9. Задание из [7] ......................................................................... 151 6.10. Задание варианта 5 из [14] .................................................. 152 6.11. Задание из [1] ........................................................................ 154 6.12. Задание из [6] ....................................................................... 154 6.13. Задание варианта 10 из [15] ................................................. 155 6.14. Задание варианта 2 из [14] .................................................. 157 6.15. Задание из [9]* ...................................................................... 158 6.16. Задание варианта 7 из [14] .................................................. 160 6.17. Задание из [3] ....................................................................... 162 6.18. Задание варианта 2 из [15] .................................................. 164 6.19. Задание варианта 6 из [15] .................................................. 167 6.20. Задание варианта 7 из [15] .................................................. 169 6.21. Задание варианта 5 из [15] .................................................. 171 6.22. Задание варианта 3 из [15] .................................................. 175 6.23. Задание варианта 6 из [14] .................................................. 177 6.24. Задание варианта 8 из [14] .................................................. 179 6.25. Задание варианта 4 из [15] .................................................. 179 Глава 7. Задания 27 .......................................................................182 7.1. Задание из [2] .......................................................................... 183 7.2. Задание из [3] .......................................................................... 187 7.3. Задание из [4] .......................................................................... 194 7.4. Задание из [5] .......................................................................... 207 7.5. Задание из [6] .......................................................................... 208 7.6. Задание из [7] .......................................................................... 213 7.7. Задание из [8] .......................................................................... 217 7.8. Задание из [9]* ......................................................................... 223 Приложение 1. Задания на определение значений переменных величин ...................................................................232 П1.1. Задания, связанные с линейным алгоритмом .................. 233 П1.2. Задания, связанные с разветвляющимся алгоритмом ..... 233
Содержание 7 П1.3. Задания, связанные с циклическим алгоритмом ............. 235 П1.4. Задания на заполнение и изменение одномерного массива ........................................................................................... 239 П1.5. Задания на обработку одномерного массива .................... 243 П1.6. Задания на заполнение двух массивов .............................. 245 П1.7. Задания на заполнение и изменение двумерного массива ........................................................................................... 246 Приложение 2. Сортировка массива методом обмена ............255 Приложение 3. Исследование функции с абсолютной величиной ......................................................................................260 Список литературы .......................................................................264
Предисловие Предисловие На Едином государственном экзамене по информатике и ИКТ задания, связанные с программированием, занимают важное место. Так, в демонстрационном варианте экзамена 2020 года их 8 при общем числе заданий 27. При этом высока весомость заданий (максимальный балл за выполнение заданий части 2 равен 3–4). Это говорит о том, что от умения решать задачи по программированию в значительной степени зависит успешность сдачи ЕГЭ в целом. В то же время, как показывает опыт, такие задачи часто вызывают у школьников заметные трудности, особенно задачи части 2 экзамена. В большой степени это связано с недостаточным числом часов, отводимых на изучение программирования в школе. Данная книга должна восполнить этот недостаток – помочь учащимся подготовиться к экзамену самостоятельно. В ней системно, подробно и доступно описана методика выполнения заданий по программированию, встречающихся на ЕГЭ. Сначала в главе 1 рассмотрены все частные, вспомогательные задачи, умение решать которые позволит успешно выполнить задания экзамена по программированию, после чего в главах 2–7 описана методика выполнения заданий из ЕГЭ. В приложениях приведены другие материалы, связанные с заданиями по программированию на ЕГЭ. При разработке программ (частных и из заданий ЕГЭ) использован школьный алгоритмический язык. Русский синтаксис этого языка и большое число комментариев сделают программы максимально понятными и легко переносимыми на любой другой язык программирования. Это означает, что книга может быть использована читателями, владеющими любым языком программирования. В большинстве случаев после разбора методики решения и программы на школьном алгоритмическом языке приводятся также соответствующие программы на популярном среди школьников языке Паскаль. Предлагаются задания для самостоятельной работы. Обратим внимание на широкое использование в книге задач от разработчиков контрольно-измерительных материалов для ЕГЭ [13–15] – существует большая вероятность того, что подобные задачи будут включены в экзамен в будущем. Кроме учащихся, готовящихся к сдаче экзамена самостоятельно, книгу могут использовать учителя и преподаватели информатики, а также студенты и учащиеся, изучающие программирование вне связи с ЕГЭ.
Глава 1 Глава 1 Вспомогательные Вспомогательные задачи задачи
Вспомогательные задачи В данной главе рассмотрена методика решения задач, предусмотренных Кодификатором элементов содержания и требований к уровню подготовки выпускников общеобразовательных учреждений для проведения в 2020 году единого государственного экзамена по информатике и ИКТ [9], которые используются в демонстрационных вариантах ЕГЭ по информатике последних лет, а также в книгах от разработчиков ЕГЭ [13–15]. 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 Такая формулировка приведена в Кодификаторе элементов содержания и требований к уровню подготовки выпускников общеобразовательных учреждений для проведения в 2020 году единого государственного экзамена по информатике и ИКТ [9].