Короткий алгоритм в различных средах исполнения. ОГЭ 2022. Задание 15.1 — ОГЭ информатике

✎ Способ 1 (программный):

Важно: Поскольку используется метод полного перебора, то возможна ситуация, когда транслятор будет работать слишком медленно. Но работоспособность представленного алгоритма проверена на онлайн компиляторах.

Pascalabc.net:

✎ Способ 2 (теоретическое решение):

Рассмотрим часть 1:
• если в 1.1 имеем x > 9, то часть 1 будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия:

x<=9

(импликация 0 → 0 = 1, 0 → 1 = 1)

• теперь, для того чтобы в части 1, выражение было истинным, надо чтобы часть 1.2 была истинной:

x*x <= A

(импликация 1 → 1 = 1)

• таким образом, получаем:

x <= 9
x2 <= A
при любых x

• так как нам необходимо найти наибольшее возможное А, то, значит, надо ограничить его значения сверху, а данная часть выражения ограничивает только снизу:

возьмем наибольшее натуральное: x=9, тогда A>=81

Рассмотрим часть 2:

• если 2.2 истинно (т.е. y <= 9), то часть 2 будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия:

y > 9

• теперь, для того чтобы в части 2 выражение было истинным, надо чтобы часть 2.1 была ложной:

y * y > A

(импликация 0 → 0 = 1)

• таким образом, получаем:

y > 9
y2 > A
при любых y

• данная часть выражения ограничивает значения А сверху:

возьмем наименьшее возможное по условию натуральное: y = 10, тогда A < 100

• Получаем, что наибольшее А меньшее 100: А = 99

• Введем обозначения:

P ≡ (x ∈ {1, 3, 5, 7, 9, 11}) ;
Q ≡ (x ∈ {3, 6, 9, 12}) ;
A ≡ (x ∈ A).

• Выполним преобразования:

(P → ¬Q) ∨ A = 1
Избавимся от импликации:
¬P ∨ ¬Q ∨ A = 1

• Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть (А) была непременно истинной, необходимо, чтобы известная часть была ложна:

¬P ∨ ¬Q ∨ А = 1 01

• То есть получаем:

¬P ∨ ¬Q = 0,
или
¬P = 0 отсюда P = 1
¬Q = 0 отсюда Q = 1

• Таким образом имеем пересечение (умножение) двух множеств Q и P. То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:

A = {3,9}

• Сумма элементов:

3 9 = 12

✎ Решение 2 (программирование):
Внимание! этот способ подходит НЕ для всех заданий с отрезками!
Python:

1
2
3
4
5
6
7
8
9

def f(a1,a2,x): return((44<=x<=48)<=(23<=x<=35))and(a1<=x<=a2)maxim =0for a1 inrange(1,200): for a2 inrange(a1 1,200): ifall(f(a1,a2,x)==0for x inrange(1,200)):# если все ложныif a2-a1>maxim: maxim=a2-a1 print(a1,a2, a2-a1)# сами точки отрезка и длина

Вывод:

44 45 1
44 46 2
44 47 344 48 4

PascalABC.net:

Вывод:

Стоит заметить, что для такого типа задач, нет универсального единственного решения. Поэтому на видео, расположенном ниже, представлено два варианта решения.

Рассмотрим один из вариантов решения:

• Удалим из формулы X&, чтобы сократить ее запись:

(A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)

• Обратим внимание, что внешней операцией является конъюнкция — логическое умножение:

(A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)

• Разделим общее выражение на две части относительно внешней операции. Первая часть — неизвестная, искомая, а вторая — известная, ее можно вычислить:

(A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)12

• Выполним некоторые преобразования во второй части формулы:
• Зная свойство импликации, преобразуем формулу (избавимся от импликации в скобках):

правило импликации: a → b = ¬a ∨ b

(A = 0) ∧ ¬(35 = 0 ∨ 52 ≠ 0)
т.к. в результате получается отрицание того, что 35 ≠ 0,
то убираем знак "не равно": было 35 ≠ 0, стало 35 = 0

• Избавимся от отрицания перед скобками по закону Де Моргана:

закон де Моргана: ¬ (A ∨ B) = ¬ A ∧ ¬ B

A = 0 ∧ 35 ≠ 0 ∧ 52 = 0 = 0

• По условию формула должна быть ложной. Вспомним таблицу истинности для конъюнкции (внешняя операция в нашей общей формуле):

0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1

• Вторая часть формулы — вычислима, поэтому начнем с нее. В ней находится операция конъюнкция, которая имеет один единственный вариант решения, когда ¬ A ∧ ¬ B = 1. То есть примем вторую часть за истину (=1). В таком случае, для того чтобы общее выражение стало ложным (так требуется по заданию), необходимо, чтобы утверждение, что A = 0 было ложным (т.к. в обратном случае получим: 1 ∧ 1 = 1):

(A = 0) ∧ 35 ≠ 0 ∧ 52 = 0 = 0 0∧1= 0

• Вторая часть будет истинной только в том случае, если оба утверждения будут истинными:

35 ≠ 0 ∧ 52 = истинно (=1) если:
35 ≠ 0 = истинно (=1)
и
52 = 0 = истинно (=1)
так как стоит логическое умножение ∧ -
смотрим выше таблицу истинности для конъюнкции

• Из двух последних пунктов получаем три утверждения:

35 ≠ 0 = 1 (истина)
и
52 = 0 = 1 (истина)
и
A = 0 = 0 (ложь)

• Переведем числа в двоичную систему счисления:

35: 100011 (≠ 0)
52: 110100 (= 0)

• Найдем такой X, который при поразрядной конъюнкции даст истинное значение для обеих частей.
• Для начала рассмотрим ситуацию с числом 52 — это проще, т.к. для получения в результате нуля (52 = 0 => истина), достаточно во всех разрядах «перекрыть» единицы нулями:
• Мы «перекрыли» все единицы нулями, чтобы в результате получить 0.
• Теперь рассмотрим 35 ≠ 0 = истина:
• Объединим обе маски в одну:

0 0 ? 0 ? ?&1 ? ? ? 1 1
0 0 ? 0 1 1

• Так как выражение X & A = 0 должно быть ложным, то найдем такое наименьшее А, при котором X & A ≠ 0. Для этого в тех разрядах Х, в которых находится единица, необходимо сохранить эту единицу и в соответствующих разрядах А:
• Переведем результат в десятичную систему счисления:

0000112 = 310

• Введем обозначения:

A = ДЕЛ(x,A); D40 = ДЕЛ(x, 40); D64 = ДЕЛ(x, 64)

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

(D40 ∨ D64) → A = 1

• Избавимся от импликации:

¬(D40 ∨ D64) ∨ A = 1
или
(¬D40 ∧ ¬D64) ∨ A = 1

• Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:

(¬D40 ∧ ¬D64) ∨ A = 1 12

• В полученной формуле необходимо, чтобы искомая часть с A в конечном счете было истинно.

  Т.е. (¬D40 ∧ ¬D64) должно быть = 0. Это нам ничего не дает, т.к. конъюнкция ложна в трех случаях (1*0, 0*1 и 0*0), т.е. D40 и D64 могут быть равны как 0, так и 1 (исключение составляет лишь вариант, когда оба D истинны, тогда логическое умножение 1 * 1 ≠ 0).

• Преобразуем выражение первой части формулы по закону Де Моргана (чтобы оно равнялось 1):

¬D40 ∧ ¬D64 = 0
или
¬(¬D40 ∧ ¬D64) = 1
Преобразуем по закону Де Моргана и получим:
D40 ∨ D64 = 1

  
Далее можно решать задание либо с помощью кругов Эйлера, либо с помощью логических рассуждений.

Решение с помощью логических рассуждений:

• Найдем все такие x, которые делятся на А и при этом делятся на 40 ИЛИ делятся на 64:

x/A : x/40 ∨ x/64

x = 40, 64, 80, 120, 128, 160, 192, 200, ...

• Теперь найдем такие A, начиная с самого наименьшего (единицы), на которые делятся все x без исключения:

А = 1, 2, 4, 8

• Наибольшее А равно 8.
• Или то же самое можно найти поиском наибольшего общего делителя чисел 40 и 64 (используем формулу Евклида):

НОД (40,64) = 8
40,64 (64 - 40 = 24)
40,24 (40 - 24 = 16)
24,16 (24 - 16 = 8)
16,8 (16 - 8 = 8)
8,8

Решение с помощью кругов Эйлера:

• В этом случае логическое сложение тоже дает истину в трех случаях (1 1, 1 0, 0 1). Т.е. мы не сможем найти А с помощью функции ДЕЛ. Необходимо прибегнуть к решению с помощью кругов Эйлера.
• В множество A должны входить все числа, которые попадают в объединение D40 D64. Таким образом, нужно найти множество, в которое входят оба этих множества.
• Найдем наибольший общий делитель чисел 40 и 64; это число 8:

64 / 40 = 1 (24 остаток)
40 / 24 = 1 (16 остаток)
24 / 16 = 1 (8 остаток)
16 / 8 = 2 (0 остаток) - НОД = 8
40 / 8 = 5
64 / 8 = 8

• Т.е. можно сказать, что A = D40 D64 = D8*D5 D8*D8 = D8*(D5 D8). D8 входит в каждое из множеств D40 и D64. Объединение D40 D64 тоже входит в D8:



• 8 — наибольший общий делитель числе 40 и 64, значит, оно соответствует максимальному значению A.

Результат: 8

✎ Решение 2 (программирование):
Python:

Вывод:

1
2
48

PascalABC.net:

Вывод:

1
2
48

Результат: 8

Имеем:

ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42)) = 1 

• Введем обозначения:

A = ДЕЛ(x,A); D28 = ДЕЛ(x, 28); D42 = ДЕЛ(x, 42)

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

A → (¬D28 ∨ D42) = 1

Избавимся от импликации:

¬A ∨ (¬D28 ∨ D42) = 1

• Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:

¬A ∨ (¬D28 ∨ D42) = 1 12

• В части 2 полученной формулы находится операция дизъюнкция, которую проще найти, когда логическое выражение равно 0 (только один случай: 0 ∨ 0 = 0):

(¬D28 ∨ D42) = 0 один случай: когда ¬D28 = 0 и D42 = 0

• Т.е. имеем:

x/¬A : x/28 ∧ x/¬42

• Иными словами найдем все такие x, которые НЕ делятся на А и при этом делятся на 28 И НЕ делятся на 42:

x = 28, 56, 84, 112, 140, 168, 196, 224, ...

• Теперь найдем такие A, начиная с самого наименьшего (единицы), на которые НЕ делятся все x без исключения:

А = 1, 2, 3

• Наименьшее А равно 3.

✎ Решение 2 (программирование). Язык Python, Pascal:

Из общего выражения:

ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42)) = 1 

• Можно сделать вывод, что для некоторого диапазона натуральных значений А, необходимо рассмотреть диапазон натуральных значений x. Если выражение будет истинным для диапазона всех рассматриваемых х, то такое А необходимо вывести на экран.
• То есть следует рассмотреть вложенный цикл: для внешнего цикла, перебирающего значения А (ограничим их числом 50, т.к. необходимо найти наименьшее А), будем запускать внутренний цикл, перебирающий значения х (х ограничим числом 1000, будем рассматривать данный диапазон, как «любое натуральное значение переменной х»).
• Во внутреннем цикле расположим формулу:

Python:

PascalABC.net:

• После запуска программы выдается наименьшее значение А, т.к. используется оператор break для выхода из цикла после первого найденного значения:

3

Результат: 3