Учёные утверждают, что наш мозг потребляет более 20% нашей энергии (интересно, как это посчитали). Немудрено, что мы избегаем умственной рутины и всякой неинтересной деятельности.
Человек склонен изобретать всякие эффективные способы и алгоритмы, чтобы избежать однообразия, и это, как ни странно, мешает порой увидеть простое решение “в лоб” - метод полного перебора. В отличие от человека, компьютер не испытывает лени, к тому же способен считать очень быстро и этим следует воспользоваться.
При всей красоте математических теорий, метод простого перебора, при наличии компьютера, и, скажем прямо, небольших знаний в Python, чудесно справляется со многими задачами на ЕГЭ. И глубоко в теорию можно особо не погружаться. Думаю, поэтому ЕГЭ по информатике, некоторые, взглянув на простенький код полного перебора, считают лёгким.
Суть метода перебора в программировании заключается в том, что в программе задаётся диапазон возможных значений, из которых выбираются те, что соответствуют условиям задачи.
Смотрим, в каких заданиях необходимо пройтись по всем значениям диапазона (используя цикл для перебора, а иногда рекурсию):
2, 5, 8, 9 (если решать в Python, а не в Excel), 12, 13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 25, 26, 27.
Получается 18 заданий из 27.
Остальные 9 заданий:
1,4,22 -решаются на бумаге.
6 - решается либо на бумаге, либо с помощью библиотеки Черепаха
7,11 - с помощью калькулятора
3,18 - Excel
10 - Word
Из этих 9 заданий, только 6 и 18 (судя по статистике) вызывают затруднения, остальные 7 решаемы даже теми, кто набрал мало баллов ЕГЭ.
Итак, ваши высокие баллы на ЕГЭ по информатике, зависят от того, как хорошо вы усвоили метод перебора и способны ли вы его преобразовывать под нужды задачи.
Конструкция for
Перебор значений задается простым циклом for, внутри которого проверяется, соответствует ли текущий элемент заданным условиям. На Питон программа будет выглядеть так:
Это действительно простой прием. И более половины заданий ЕГЭ решаются с его использованием. На мой взгляд — это хорошая новость.
В информатике циклический процесс называется итерацией, диапазон поиска — итерируемым объектом, а элемент, на который указывает переменная i - итератором.
Чтобы решить задачу нужно ответить на вопросы:
- Каков диапазон значений? Диапазон определяет сам программист из общих соображений и условия задачи.
- Какие значения — "интересные"? Это надо вычитать из задания, отбор происходит, как правило, с использованием оператора if.
- Что нужно сделать при "встрече"? Вывести на экран (print(i)), подсчитать (counter+=1), просуммировать значение (sum+=i) или добавить его в список a (a.append(i)) для дальнейших вычислений.
Перебор значений можно осуществить не только с помощью for. Иногда удобнее пользоваться while или библиотекой itertools.
Конструкция while
Перебор через функции библиотеки itertools
Иногда требуется не последовательный перебор элементов, а перебор различных сочетаний и комбинаций . Чтобы каждый раз не писать код комбинаторных перестановок и сочетаний в Python есть модуль itertools. В некоторых заданиях ЕГЭ, благодаря ему можно получить ответ очень компактным кодом.
Библиотека itertools входит в установочный комплект модулей библиотек Python. Т.е. специально ее устанавливать не надо, на экзамене она будет. При использовании ее функций нужно указать директиву import itertools в начале программы.