Задание 15 ЕГЭ по информатике: решайте с автопроверкой

В задании 15 нужно подобрать отрезок, множество или число A так, чтобы логическая формула была истинна при любом x. Формулы бывают про принадлежность отрезкам, делимость и поразрядное И.

Решать задачи номера

Как решать программой

Программа проверяет формулу перебором x. Для целых x достаточно перебрать все значения в разумных пределах. Для вещественных x берут сетку с шагом 0,1 или 0,5: концы отрезков целые, поэтому такой сетки хватает.

Найдите все x, при которых формула без A ложна. Именно их A и должен накрыть. Для отрезка A ответ — это расстояние от самой левой такой точки до самой правой, для числа A перебирайте кандидатов и проверяйте формулу при всех x.

Импликацию a → b записывайте как (not a) or b. Скобки расставляйте явно: приоритеты операций в Python и в условии могут не совпасть.

Разбор примера

P = [10, 40], Q = [20, 25]. Нужен наименьший отрезок A, при котором формула ((x ∈ P) → (x ∈ Q)) ∨ (x ∈ A) истинна для любого x. Ищем точки, где импликация ложна.

P, Q = (10, 40), (20, 25)

def inside(seg, x):
    return seg[0] <= x <= seg[1]

bad = [x / 10 for x in range(0, 10001)
       if inside(P, x / 10) and not inside(Q, x / 10)]
print(max(bad) - min(bad) if bad else 0)

Программа печатает

30.0

Импликация ложна там, где x лежит в P и не лежит в Q: на кусках от 10 до 20 и от 25 до 40. Отрезок A должен накрыть оба куска, наименьший такой отрезок [10, 40], его длина 30.

Решить эту задачу

Задачи к заданию 15

  • Наименьший отрезок A для импликацииСредняяРешать
  • Наибольший отрезок A внутри трёх отрезковСредняяРешать
  • Наименьшая сумма элементов множества AСредняяРешать
  • Наименьшее A в формуле с поразрядной конъюнкциейСредняяРешать
  • Наибольшее A не больше границыСредняяРешать
  • Предикат ДЕЛ и общие кратныеСредняяРешать
  • Наименьшее A для формулы с двумя переменнымиСредняяРешать
  • Наибольшее A при уравнении на x и yСредняяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Какой шаг брать для вещественных x?
Достаточно шага, который меньше половины расстояния между концами отрезков. Для целых концов хватает 0,1.
Как найти наименьшее множество A?
Найдите x, при которых формула без A ложна. В A должны войти все они, поэтому наименьшая сумма — это сумма этих x.
Что такое поразрядная конъюнкция?
Операция & в Python: И над каждой парой битов. Например, 12 & 10 даёт 8.