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

Содержание книги «ЕГЭ по информатике. Решение задач по программированию»:

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