ЕГЭ по информатике, Решение задач, Златопольский Д.М., 2013

ЕГЭ по информатике, Решение задач, Златопольский Д.М., 2013.
    Книга предназначена для подготовки учащихся к Единому государственному экзамену по информатике в части решения задач по программированию. Рассмотрена методика решения основных типовых задач по программированию, а также заданий из демонстрационных вариантов ЕГЭ и из пособий, написанных разработчиками контрольно-измерительных материалов по информатике. Книга предназначена также студентам ВУЗов и колледжей, преподавателям информатики и другим читателям при изучении программирования вне связи с ЕГЭ.
Запись натурального числа в позиционной системе счисления с основанием меньшим или равным 10.
Обработка и преобразование такой записи числа.
Обозначим заданное натуральное десятичное число — n, а основание системы счисления, в которую нужно перевести заданное, — основание. Идея решения первой части задачи — получить все цифры записи числа п в системе с основанием основание и записать каждую из них в массив. Конечно, нужно получить и всю новую запись числа. После этого можно решать вторую часть задачи — обрабатывать полученную запись, точнее, массив с ее цифрами. Можно будет найти сумму цифр, максимальную цифру и т. п.
Напомним методику перевода целых чисел из десятичной системы счисления в систему с другим основанием. Необходимо определять остаток от деления заданного числа и всех промежуточных целочисленных частных на основание и делать это до тех пор, пока частное не станет равно нулю. Полученные остатки и представляют собой цифры новой записи числа.
Оглавление
Предисловие 11
Глава 1. Задачи из Кодификатора для ЕГЭ 13
1.1. Поиск минимума и максимума двух, трех, четырех данных чисел без использования массивов и циклов 13
1.1.1. Поиск максимума/минимума среди двух чисел (а и Ь) 13
1.1.2. Поиск максимума/минимума среди трех чисел (а, Ъ и с) 15
1.1.3. Поиск максимума/минимума среди четырех чисел (я, b,cud) 19
1.2. Нахождение всех корней заданного квадратного уравнения 25
1.3. Нахождение наибольшего общего делителя двух натуральных чисел (алгоритм Евклида) 27
1.4. Запись натурального числа в позиционной системе счисления с основанием меньшим или равным 10. Обработка и преобразование такой записи числа 31
1.5. Нахождение сумм, произведений элементов данной конечной числовой последовательности (или массива) 33
1.5.1. Суммирование всех чисел последовательности 33
1.5.2. Нахождение произведения всех чисел последовательности 34
1.6. Использование цикла для решения простых переборных задач (поиск наименьшего простого делителя данного натурального числа, проверка числа на простоту и т. д.) 35
1.6.1. Определить количество делителей натурального числа п 35
1.6.2. Определить, является ли заданное натуральное число простым 39
1.6.3. Найти наименьший простой делитель данного натурального числа 39
1.7. Заполнение элементов одномерного и двумерного массива по заданным правилам 42
1.8. Операции с элементами массива 43
1.8.1. Линейный поиск элемента 43
1.8.1.1. Проверка факта наличия в массиве элемента с заданными свойствами 43
1.8.1.2. Поиск индекса элемента массива, равного некоторому числу 45
1.8.1.3. Поиск индекса первого элемента массива, равного некоторому числу 46
1.8.2. Вставка и удаление элементов в массиве 48
1.8.2.1. Удаление из массива k-то элемента со сдвигом всех расположенных справа от него элементов на одну позицию влево 48
1.8.2.2. Вставка в массив заданного числа на к-е место со сдвигом к-го, (к + 1)-го, (к + 2)-го ... последнего элемента на одну позицию вправо 49
1.8.3. Перестановка всех элементов массива в обратном порядке 49
1.8.4. Суммирование элементов массива 51
1.8.5. Проверка соответствия элементов массива некоторому условию 51
1.8.5.1. Проверка того факта, что все элементы массива соответствуют некоторому условию 51
1.8.5.2. Проверка массива на упорядоченность 51
1.9. Нахождение минимального (максимального) значения в данном массиве и количества элементов, равных ему, за однократный просмотр массива 52
1.9.1. Определение максимального элемента массива 52
1.9.2. Определение минимального элемента массива 54
1.9.3. Определение индекса максимального элемента массива 54
1.9.4. Нахождение индекса минимального элемента 56
1.9.5. Нахождение минимального (максимального) элемента массива и количества элементов, равных ему 56
1.10. Нахождение второго по величине (второго максимального или второго минимального) значения в данном массиве за однократный просмотр массива 57
1.11. Операции с элементами массива, отобранными по некоторому условию (например, нахождение минимального четного элемента в массиве, нахождение количества и суммы всех четных элементов в массиве) 57
1.11.1. Нахождение суммы элементов массива с заданными свойствами (удовлетворяющих некоторому условию) 57
1.11.2. Нахождение количества элементов массива с заданными свойствами 58
1.11.3. Нахождение среднего арифметического значения элементов массива с заданными свойствами 59
1.11.4. Изменение значений элементов массива с заданными свойствами 60
1.11.5. Вывод на экран элементов массива с заданными свойствами 61
1.11.6. Нахождение номеров (индексов) элементов массива с заданными свойствами 63
1.11.7. Определение минимального значения среди тех элементов массива, которые удовлетворяют некоторому условию 64
1.11.8. Определение индекса минимального элемента среди элементов массива, которые удовлетворяют некоторому условию 68
1.11.9. Нахождение максимального количества подряд идущих элементов массива, обладающих заданными свойствами 69
1.11.10. Нахождение максимальной суммы подряд идущих элементов массива, обладающих заданными свойствами 72
1.12. Сортировка массива 75
1.13. Слияние двух упорядоченных массивов в один без использования сортировки 75
1.14. Обработка отдельных символов данной строки. Подсчет частоты появления символа в строке 79
1.14.1. Определить, сколько раз в заданной строке встречается некоторый символ 79
1.14.2. Определить позицию (номер) первого вхождения некоторого символа в заданную строку (если символа в строке нет, то вывести 0) 79
1.14.3. Определить, есть ли в заданной строке некоторый символ 81
1.15. Работа с подстроками данной строки с разбиением на слова по пробельным символам. Поиск подстроки внутри данной строки, замена найденной подстроки на другую строку 82
1.15.1. Определить, сколько раз в заданной строке встречается некоторая подстрока 82
1.15.2. Определить позицию (номер) первого вхождения некоторой подстроки в заданную строку (если подстроки в строке нет, то вывести 0) 83
1.15.3. Определить, есть лив заданной строке некоторая подстрока 85
1.15.4. Удалить из заданной строки все вхождения некоторой подстроки 85
1.15.5. Заменить в заданной строке все вхождения некоторой подстроки на другую подстроку 86
1.15.6. Дана фраза, слова которой отделены друг от друга одним пробелом (начальных и конечных пробелов нет). Получить массив слов этой строки 88
Глава 2. Другие типовые задачи программирования 90
2.1. Группа задач на выделение частей строки 90
2.1.1. Выделение первого слова 90
2.1.2. Выделение второго слова 92
2.1.3. Выделение двух первых слов как единой величины 93
2.1.4. Выделение последнего слова 94
2.1.5. Выделение числа после первого слова 94
2.1.6. Выделение числа после второго слова 95
2.1.7. Выделение двух чисел после второго слова 96
2.1.8. Выделение трех чисел после второго слова 96
Задания для самостоятельной работы 97
2.2. Группа задач на подсчет количества каждого из значений 99
2.2.1. Подсчет количества каждой из цифр в заданной последовательности 99
2.2.2. Подсчет количества каждой из цифр в заданной строке. Вариант 1 101
2.2.2. Подсчет количества каждой из цифр в заданной строке. Вариант 2 103
2.2.3. Подсчет количества каждой из букв в заданной строке. Вариант 1 104
2.2.3. Подсчет количества каждой из букв в заданной строке. Вариант 2 105
2.2.4. Подсчет количества каждого из числовых значений в заданной последовательности чисел 106
2.2.5. Подсчет количества каждого из числовых значений в заданном наборе строк 106
Задания для самостоятельной работы 107
2.3. Группа задач на подсчет количества и вывод значений, удовлетворяющих некоторому условию 108
2.3.1. Подсчет количества тех чисел последовательности, которые удовлетворяют некоторому условию 108
2.3.2. Вывод на экран элементов массива, соответствующих элементам другого массива с заданными свойствами 109
Задания для самостоятельной работы 110
2.4. Группа задач на нахождение максимальных (минимальных) элементов массива, их индексов номеров, количеств и т. п 111
2.4.1. Нахождения второго по величине максимального элемента 111
2.4.1.1. Поиск элемента массива, который стоял бы на предпоследнем месте, если бы массив был отсортирован по неубыванию 111
2.4.1.2. Нахождения элемента массива, больше которого только максимальный 114
2.4.2. Нахождение второго минимума 115
2.4.3. Нахождение количества максимальных элементов 115
2.4.4. Нахождение количества минимальных элементов 118
2.4.5. Нахождение количества вторых максимумов 118
2.4.5.1. Нахождение количества значений в массиве, равных элементу, больше которого только максимальный 118
2.4.5.2. Нахождение количества значений в массиве, равных элементу, который стоял бы на предпоследнем месте, если бы массив был отсортирован по неубыванию 120
2.4.6. Нахождение количества вторых минимумов 121
2.4.7. Нахождение третьего максимума 121
2.4.8. Нахождение третьего минимума 123
Задания для самостоятельной работы 123
2.5. Разные задачи 124
2.5.1. Суммирование значений для различных категорий 124
2.5.2. Расчет среднего значения с точностью до целых 125
2.5.3. Преобразование строкового представления числа в число 125
Задания для самостоятельной работы 125
Глава 3. Задачи С2 127
3.1. Задача из [4] 128
3.2. Задача варианта 8 из [12] 129
3.3. Задача из [2] 131
3.4. Задача варианта 10 из [12] 132
3.5. Задача варианта 9 из [12] 134
3.6. Задача варианта 4 из [12] 137
3.7. Задачаварианта2 из [12] 139
3.8. Задача варианта 1 из [16] 139
3.9. Задача варианта 2 из [16] 140
3.10. Задача варианта 3 из [16] 141
3.11. Задача варианта 4 из [16] 142
3.12. Задача варианта 6 из [12] 142
3.13. Задача варианта 5 из [16] 144
3.14. Задача из [6] 146
3.15. Задача варианта 10 из [16] 146
3.16. Задача варианта 9 из [16] 148
3.17. Задача из [5] 149
3.18. Задача варианта 1 из [12] 151
3.19. Задача из [7] 151
3.20. Задача варианта 3 из [12] 151
3.21. Задача варианта 5 из [12] 155
3.22. Задача варианта 6 из [16] 157
3.23. Задача варианта 8 из [16] 159
3.24. Задача варианта 7 из [16] 159
3.25. Задача из [3] 159
3.26. Задача варианта 7 из [12] 161
Глава 4. Задачи С4 из демонстрационных вариантов ЕГЭ по информатике 166
4.1. Задача из демонстрационного варианта экзамена 2012 года 166
4.1.1. Определение того факта, что некоторая решенная задача уже имеется в списке ранее введенных задач (в массиве задачи) 168
4.1.2. Заполнение массива задачи неповторяющимися значениями 169
4.1.3. Заполнение массива задачи неповторяющимися значениями и определение "встречаемости" (количества вхождений) каждой задачи 170
4.1.4. Сортировка массива колзадач в порядке невозрастания (и соответственно ей — изменение массива задачи) 171
4.2. Задача из демонстрационного варианта экзамена 2010 года 173
4.3. Задача из демонстрационного варианта экзамена 2009 года 176
4.4. Задача из демонстрационного варианта экзамена 2008 года 178
4.5. Задача из демонстрационного варианта экзамена 2007 года 181
Глава 5. Задачи С4 из книги [16] 182
5.1. Вариант 1 182
5.2. Вариант 2 184
5.3. Вариант 3 185
5.4. Вариант 4 187
5.4.1. Первый способ 188
5.4.2. Второй способ 189
5.5. Вариант 5 190
5.6. Вариант 7 191
5.7. Вариант 10 192
Глава 6. Задачи С4 из книги [12] 196
6.1. Вариант 1 196
6.2. Вариант 2 200
6.3. Вариант 3 203
6.4. Вариант 4 206
6.5. Вариант 5 208
Дополнение 210
Вариант 7 211
Вариант 8 214
Глава 7. Задачи на обработку последовательности латинских букв 219
7.1. Задача варианта 8 из [16] 219
7.2. Задача варианта 10 из [12] 223
7.3. Задача варианта 9 из [12] 225
7.4. Задача вариантов 6 и 9 из [16] 227
7.4.1. Задача варианта 6 227
7.4.2. Задача варианта 9 228
7.4.П1. Дано предложение, заканчивающееся точкой. Слова в нем разделены одним пробелом. Найти длину самого большого слова 228
7.4.П2. Дано предложение, заканчивающееся точкой. Слова в нем разделены пробелами (одним или несколькими). Найти длину самого большого слова 230
7.4.ПЗ. Дано предложение, заканчивающееся точкой. Слова в нем разделены одним пробелом. Найти длину самого короткого слова 230
7.4.П4. Дано предложение, заканчивающееся точкой. Слова в нем разделены пробелами (одним или несколькими). Найти длину самого короткого слова 231
7.4.П5. Дано предложение на английском языке, заканчивающееся точкой. Найти длину самого короткого слова (словом будем называть непрерывную последовательность латинских букв, слова друг от друга отделены другими символами) 233
7.4.П6. Дан текст на английском языке, состоящий из прописных букв (других символов в тексте нет). Получить текст, в котором каждая буква исходного текста заменена на букву, стоящую в алфавите на к букв правее. Алфавит считается циклическим, т. е. после буквы "Z" стоит буква "А" 235
7.4.П7. Дан текст на английском языке, состоящий из строчных букв (других символов в тексте нет). Получить текст, в котором каждая буква исходного текста заменена на букву, стоящую в алфавите на к букв правее. Алфавит считается циклическим, т. е. после буквы "z" стоит буква "а" 235
7.4.П8. Дан текст на английском языке, состоящий из прописных букв (других символов в тексте нет). Заменить каждую букву текста на букву, стоящую в алфавите на к букв левее. Алфавит считается циклическим, т. е. перед буквой "А" стоит буква "Z" 236
7.4.П9. Дан текст на английском языке, состоящий из строчных букв (других символов в тексте нет). Заменить каждую букву текста на букву, стоящую в алфавите на к букв левее. Алфавит считается циклическим, т. е. перед буквой "а" стоит буква "z" 236
7.4.П10. Дан текст на английском языке, состоящий из букв (других символов в тексте нет). Заменить каждую букву текста на букву, стоящую в алфавите на к букв правее. Алфавит считается циклическим, т. е. после буквы "Z" стоит буква "А", а после буквы "z" — "а" 236
7.5. Задача варианта 6 из [12] 239
ПРИЛОЖЕНИЯ 243
Приложение 1. О задачах С1 245
Примеры задач 245
2009 — С1 245
2010 — С1 246
2011 — С1 247
2012 — С1 248
2009 — С1 254
2010 — С1 255
2012 — С1 256
Задачи для самостоятельной работы ([12]) 259
Приложение 2. Задачи на определение значений переменных величин 269
П2.1. Задачи, реализующие линейный алгоритм 269
П2.2. Задачи, реализующие разветвляющийся алгоритм 270
П2.3. Задачи, реализующие циклический алгоритм 271
П2.4. Задачи, реализующие алгоритмы различных типов 274
П2.5. Задачи на заполнение и изменение одномерного массива 275
П2.6. Задачи на обработку одномерного массива 277
П2.7. Задачи на заполнение двух массивов 278
П2.8. Задачи на заполнение и изменение двумерного массива 279
Задания для самостоятельной работы 282
Приложение 3. Методы заполнения числовых массивов 288
П3.1. Заполнение массива разными значениями, не подчиняющимися общему закону 288
П3.2. Заполнение массива одинаковыми значениями 289
П3.З. Заполнение массива последовательностью чисел, закон построения которой известен 290
П3.4. Заполнение массива случайными значениями 291
Приложение 4. Простейшие методы сортировки массивов 293
Сортировка обменом 293
Сортировка выбором 297
Список литературы 302.