Автор статьи: Андрей Роженцов
Завершаем разбор задания № 15 решением с помощью программирования. Этот способ эффективен для следующих типов задач:
- графики
- битовые операции
- арифметические операции
Решение кодом удобно тем, что позволяет избежать ошибок при подстановке значений в выражение. Шаблонное решение сводит анализ выражения к минимуму и позволяет быстро найти ответ.
При решении задач с помощью кода необходимо переписать условие задачи в Python. Для этого рассмотрим таблицу эквивалентных символов:
| Условие задачи | Python |
|---|---|
| ∧ | and |
| ∨ | or |
| ¬ | not |
| = | == |
| ≡ | == |
| → | \<= |
| & | & |
 |
|
| ≥ | >= |
| ≤ | \<= |
Очень важно помнить о правилах приоритета операций!
| Приоритет (от высшего к низшему) | Алгебра логики | Python |
|---|---|---|
| 1 | Скобки () | Скобки () |
| 2 | Отрицание (НЕ, ¬) | Арифметические операции: +, -, *, /, //, % и т. д. |
| 3 | Конъюнкция (И, ∧) | Операторы сравнения: \<, \<=, ==, != и т. д. |
| 4 | Дизъюнкция (ИЛИ, ∨) | not |
| 5 | Импликация (→), | and |
| 6 | Эквивалентность (↔) | or |
Так, например, импликация имеет низший приоритет, но при замене её в коде на сравнение ≤, которое имеет высокий приоритет, может измениться значение выражения. Поэтому необходимо правильно расставлять скобки!
Алгоритм решения задания № 15 ЕГЭ по информатике с помощью программирования
- Перебрать все возможные значения числа $A$
- Для каждого $A$ перебрать все возможные значения оставшихся переменных
- Проверить, чему равно выражение (истинно или ложно). Если условие не выполняется, значит, это значение $A$ не подходит, переходим к рассмотрению следующего
При решении разных типов заданий будет отличаться только запись условия и определение границ диапазона изменения для переменных.
Задача 1: графики
Код к задаче:
# Перебираем все возможные целые неотрицательные значения А по возрастанию
for A in range(0, 301):
# Создаём переменную flag, которая показывает, подходит ли нам число А.
# Изначально предполагаем, что подходит
flag = True
# Перебираем значения х и у
for x in range(0, 51):
for y in range(0, 101):
# Проверяем, что условие истинно, т. е. то, что нам НЕ ПОДХОДИТ
if ((3*x+y > A) and (y < x) and (x < 30)) == 1:
# Если это так, то переменную flag делаем ложью
flag = False
# Проверяем, остался ли flag = True или нет
if flag == 8True:
print(A)
break
Для поиска подходящего числа $A$ воспользуемся циклом. В нём будем создавать переменную flag, указывающую на то, подходит ли нам число $A$: flag = True — подходит, flag = False — нет.
По условию задачи выражение должно быть тождественно ложно для любых целых неотрицательных $x$ и $y$. Конечно, перебрать вообще все значения этих переменных невозможно, т. к. их бесконечное количество, но с помощью цикла мы можем рассмотреть некоторый диапазон чисел. Его границы обсудим чуть позже.
Будем проверять, что выражение, наоборот, истинно, то есть условие не выполняется. Это будет значить, что данное число $A$ нам не подходит. Тогда переменной flag присваиваем значение False.
Важно! Для фиксированного $A$ переменная flag может измениться только один раз: True → False. Если нашлась хотя бы одна пара $(x, y)$, при которой условие ломается, то $A$ нам не подходит и flag становится False.
Если после перебора всех $(x, y)$ flag остался True, значит, условие выполнилось для всех пар — это $A$ подходит. Мы перебираем $A$ по возрастанию, поэтому первое подходящее значение и есть ответ. Затем цикл можно остановить с помощью break.
Теперь поговорим о диапазонах чисел для перебора циклом.
Диапазон стоит подбирать так, чтобы каждое условие из $(x < 30), (y < x), (3 × x + y > A)$ принимало значение как $1$, так и $0$, в зависимости от значения переменной. Например, условие $x < 30$ истинно для чисел меньше $30$ и ложно для чисел, больших или равных $30$, т. е. при $х = 30$ происходит смена значения выражения. Тогда возьмём диапазон с запасом от этого числа в обе стороны.
for x in range(0, 51):
Условие $y < x$ тоже должно как выполняться, так и не выполняться. Максимальный $x$ равен $50$ (в диапазоне правая граница всегда не включается), поэтому $y$ сделаем тоже с запасом — до $100$.
for y in range(0, 101):
Выражение $3 × x + y > A$ тоже должно принимать различные значения. Рассчитаем максимальное значение выражения: $3 × x+ y = 3 × 50 + 100 = 250$. Возьмём с запасом до $300$.
for A in range(0, 301):
Запускаем программу и получаем ответ: $115$.
Задача 2: битовые операции
Код к задаче:
for A in range(0, ?):
flag = True
for x in range(0, ?):
if # условие не выполняется:
flag = False
if flag == True:
print(A)
break
Перепишем условие:
$((x \& 52 \neq 0) \land (x \& 48 = 0)) \to \lnot(x \& А = 0)$
(((x&52 != 0) and (x&48 == 0)) <= (not(x&A == 0))) == 0
По условию задачи выражение должно быть равно $1$. Мы будем, наоборот, проверять, что оно ложно.
Что такое &?
Рассмотрим пример 44 & 26. Для того чтобы выполнить поразрядное умножение (&), необходимо перевести числа в двоичную систему счисления и записать друг под другом. Т. к. у числа 26 меньше разрядов, чем у числа 46, то слева добавим незначащий ноль. По очереди перемножаем две цифры из каждого разряда и в итоге получаем 001000 в двоичной системе счисления. В десятичной это 8.
Рассмотрим диапазон для переменной х. В выражении применяется поразрядная конъюнкция x &52 и x & 48. Число 52 больше, поэтому рассмотрим случай с ним.
Если число х в двоичной системе счисления будет состоять больше чем из 6 цифр, то у числа 52 слева придётся дописывать незначащие нули, которые при умножении на цифры из числа х в итоге дадут 0, поэтому нет смысла рассматривать х, состоящий больше чем из 6 цифр в двоичной системе счисления.
Максимальное число из 6 цифр: 111111₂ = 63. Сделаем диапазон с небольшим запасом.
for x in range(0, 70):
Также в выражении есть x & 48. Под него наш диапазон тоже подходит.
Нужно найти минимальное неотрицательное целое число А. Поэтому диапазон для этой переменной можно сделать большим, ведь при нахождении первого подходящего числа А цикл останавливается с помощью оператора break.
for A in range(0, 100):
Ускорим выполнение программы с помощью ещё одного оператора break внутри цикла по х.
for x in range(0, 70):
if (((x&52 != 0) and (x&48 == 0)) <= (not(x&A == 0))) == 0:
flag = False
break
Если мы нашли такой х, который делает выражение ложным, это значит, что данное А не подходит и нет смысла дальше рассматривать значения х.
Код целиком:
for A in range(0, 100):
flag = True
for x in range(0, 70):
if (((x&52 != 0) and (x&48 == 0)) <= (not(x&A == 0))) == 0:
flag = False
break
if flag == True:
print(A)
break
Для решения задач с битовыми операциями аналитически рекомендуем методическое пособие К. Ю. Полякова.
Задача 3: арифметические операции
Логику любой арифметической операции мы можем описать с помощью функции.
Напишем функцию DEL, которая принимает два аргумента, n и m, и возвращает истину, если n делится на m без остатка.
def DEL(n, m):
if n % m == 0:
return True
else:
return False
Выберем теперь диапазон переменной х. В формуле присутствует ДЕЛ(x,72) и ДЕЛ(x,495). Необходимо, чтобы при различных х эти выражения были как ложными, так и истинными.
Существует много чисел, которые не делятся на 72 и 495, но какое делится на оба? 72 × 495 = 35 640. Если выбрать диапазон для переменной х от 0 до 35 640, то в нём будут и числа, которые делятся на 72 и 495, и не делящиеся ни на одно из этих чисел, и делящиеся только на одно число. Таким образом, мы рассмотрим все варианты. Остальная логика программы прежняя.
def DEL(n, m):
if n % m == 0:
return True
else:
return False
for A in range(1, 1000):
flag = True
for x in range(0, 72 * 495 + 1):
if ((not(DEL(x,72))) or DEL(x,495) or (not(DEL(x,A)))) == 0:
flag = False
break
if flag == True:
print(A)
break
Функция DEL, которую мы написали, дублирует логику работы функции ДЕЛ из условия задачи. Поэтому вместо ДЕЛ(x,72) пишем DEL(x,72).
Ответ: 55
Итог
Шаблон кода:
for A in range(0, ?):
flag = True
for x in range(0, ?):
if # условие не выполняется:
flag = False
break
if flag == True:
print(A)
break
Предложенный шаблон кода требует лишь незначительных изменений при конкретном условии задачи (само логическое выражение и диапазоны перебора). Это экономит время и силы. Компьютер не допустит арифметических или логических ошибок при переборе. Если условие переведено верно и диапазоны выбраны корректно, ответ будет гарантированно правильным.