ЕГЭ по информатике: решаем перебором на Python

Когда перебор работает

Перебор хорош, когда вариантов не слишком много. Python в простом цикле проверяет порядка миллиона вариантов за секунду. Значит, задачи, где вариантов тысячи или миллионы, перебираются мгновенно, а где миллиарды, уже нужно думать.

У перебора есть и второе достоинство: он почти не оставляет места для ошибки в рассуждении. Хитрая формула может подвести, если вы неверно поняли условие, а программа, которая буквально проверяет каждое условие задачи, ошибается только там, где ошиблись вы при записи условия. Поэтому даже задачи, которые вы умеете решать на бумаге, полезно проверять кодом.

Перед тем как писать код, стоит прикинуть количество вариантов. Слова из 5 букв из алфавита в 3 буквы: 3⁵ = 243 варианта. Числа от 1 до миллиона: миллион. Всё это перебирается без проблем.

Шаблон 1. Подсчёт слов

from itertools import product count = 0 for w in product('КОТ', repeat=5): if w.count('К') == 2: count += 1 print(count)

Проверим ответ без программы. Выбрать два места для К из пяти можно 10 способами, а на оставшиеся три места ставим О или Т: 2 · 2 · 2 = 8 вариантов. Всего 10 · 8 = 80. Сошлось.

Шаблон легко переделать: другие буквы, другая длина, другое условие. Например, «буквы не повторяются» записывается как len(set(w)) == len(w), а «слово начинается с О» как w[0] == 'О'.

Шаблон 2. Числа с условиями

count = 0 for x in range(1, 1001): if x % 7 == 0 and x % 3 != 0: count += 1 print(count)

Проверка вручную: чисел, кратных 7, до 1000 ровно 142, кратных и 7, и 3, то есть 21, ровно 47. 142 − 47 = 95. Обратите внимание на range(1, 1001): правая граница в Python не включается, поэтому пишем 1001, чтобы проверить и само 1000. Это одна из самых частых ошибок на экзамене.

Шаблон 3. Двоичная запись выражения

print(bin(pow(4, 20) + pow(2, 30) - 16).count('1'))

Проверим рассуждением. 4²⁰ = 2⁴⁰, это единица и сорок нулей. 2³⁰ − 2⁴ это двоичное число, где единицы стоят на позициях с 4-й по 29-ю: 26 единиц. Вместе с 2⁴⁰ получается 27. Как переводить числа между системами вручную, разобрали в статье о системах счисления.

Похожие задания бывают с другими основаниями: «сколько цифр 2 в троичной записи». Тогда пишут свой перевод: в цикле берут остаток от деления на 3 и делят число нацело на 3.

n = pow(9, 15) + pow(3, 20) - 5 count = 0 while n > 0: if n % 3 == 2: count += 1 n //= 3 print(count)

Шаблон 4. Таблица истинности

В заданиях по логике нужно найти, при каких значениях переменных логическое выражение истинно. Перебор всех наборов нулей и единиц делается тем же product.

from itertools import product print('x y z w') for x, y, z, w in product([0, 1], repeat=4): if ((x <= y) and not z) or w == 0: print(x, y, z, w)

Здесь x <= y на нулях и единицах работает как импликация «из x следует y»: она ложна только при x = 1 и y = 0. Программа печатает все наборы, где функция истинна, и по ним уже сопоставляют столбцы с фрагментом таблицы из условия. Подробнее о логических операциях в статье о логике.

Советы на экзамене

• Держать шаблоны в голове или в виде коротких заготовок: на экзамене их нельзя принести, но после тренировки они пишутся за минуту.
• Проверять код на маленьком примере, где ответ можно посчитать руками.
• Следить за границами range: правая граница не входит.
• Если программа работает дольше минуты, задача, скорее всего, требует оптимизации: сократить диапазон, убрать лишний вложенный цикл.
• Записывать в бланк только ответ: код проверяющие не видят.

Почему для экзамена удобнее всего Python, рассказали в статье о Python.

Частые вопросы