Делимость, поразрядная конъюнкция и координатная плоскость

135.28K

Category:

programming

https___school.mos.ru_ej_attachments_files_226_293_380_original_%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B%20%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D1%8F%20%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D1%8F%2015

1. Алгоритмы решения задания 15

Подготовка к ЕГЭ по информатике
10-11 классы

2. Источники

Примеры задач взяты на странице генератора
заданий ЕГЭ сайта К.Полякова:
https://kpolyakov.spb.ru/school/ege/generate.htm
Каждое задание снабжено номером из
каталога заданий указанного источника

3. Виды заданий

5 видов заданий:
• задачи с отрезками;
• задачи на множества чисел;
• задачи с делителями;
• задачи с битовыми логическими операциями;
• анализ неравенств на плоскости.

4. Задание с отрезками: особенности

2 подхода к решению:
– аналитический – на основе применения
законов логики для минимизации критерия
истинности;
– компьютерный перебор при помощи
программы.
2 типа заданий:
– найти отрезок наибольшей длины;
– найти отрезок наименьшей длины

5. Задание с отрезками

Пример задачи № 1:
(№ 4869) На числовой прямой даны два отрезка:
P=[25;37] и Q=[32;47]. Укажите наибольшую
возможную длину такого отрезка A, что формула
( (x ∈ A) ∧ ¬(x ∈ P)) → (¬(x ∈ P) ∧ (x ∈ Q))
тождественно истинна, то есть принимает
значение 1 при любых x.

6. Шаблон №1 программы решения

P = range(); Q = range()
md = 0
for a2 in range(1,???):
for a1 in range(0,a2):
A=range(a1,a2)
f= all( ( ) for x in range(1,???))
if f: #md=max(md,a2-a1)
if md < a2-a1: md=a2-a1; a11=a1; a22=a2
print(md, '<-',a11,a22)

7. Программа решения примера №1

P = range(25, 37); Q = range(32, 47); md = 0
for a2 in range(1,100):
for a1 in range(0,a2):
A=range(a1,a2)
f= all( ( ) for x in range(1,100))
if f:
if md < a2-a1: md=a2-a1; a11=a1; a22=a2
print(md, '<-',a11,a22)

8. Программа решения примера №1

9. Программа решения примера №1

P = range(25, 37); Q = range(32, 47); md = 0
for a2 in range(1,100):
for a1 in range(0,a2):
A=range(a1,a2)
f= all( ( ((x ∈ A) ∧ ¬(x ∈ P)) \
→ (¬(x ∈ P) ∧ (x ∈ Q)) )\
for x in range(1,100))
if f:
if md < a2-a1: md=a2-a1; a11=a1; a22=a2
print(md, '<-',a11,a22)

10. Программа решения примера №1

P = range(25, 37); Q = range(32, 47); md = 0
for a2 in range(1,100):
for a1 in range(0,a2):
A=range(a1,a2)
f= all( ( ( (x in A) and (x not in P)) \
<= ((x not in P) and (x in Q)) )\
for x in range(1,100))
if f:
if md < a2-a1: md=a2-a1; a11=a1; a22=a2
print(md, '<-',a11,a22)

11. Программа решения примера №1

12. Задание с отрезками

Пример задачи № 2:
(№ 4654) На числовой прямой даны два отрезка:
P = [20, 50] и Q = [30, 40]. Найдите наименьшую
возможную длину отрезка A, при котором формула
¬(x ∈ A) → ¬((x ∈ P) ∨ (x ∈ Q))
тождественно истинна, то есть принимает значение
1 при любых x.

13. Шаблон №2 программа решения

P = range(); Q = range()
md = 100000
for a2 in range(1,???):
for a1 in range(0,a2):
A=range(a1,a2)
f= all( ( ) for x in range(1,???))
if f:
if md > a2-a1: md=a2-a1; a11=a1; a22=a2
print(md, '<-',a11,a22)

14. Программа решения примера №2

P = range(20, 50); Q = range(30, 40);
md = 10000
for a2 in range(1,100):
for a1 in range(0,a2):
A=range(a1,a2)
f= all( ( ) for x in range(1,100))
if f:
if md > a2-a1: md=a2-a1; a11=a1; a22=a2
print(md, '<-',a11,a22)

15. Программа решения примера №2

P = range(20, 50); Q = range(30, 40);
md = 10000
for a2 in range(1,100):
for a1 in range(0,a2):
A=range(a1,a2)
f= all( (¬(x ∈ A) → ¬((x ∈ P) ∨ (x ∈ Q)) )\
for x in range(1,100))
if f:
if md > a2-a1: md=a2-a1; a11=a1; a22=a2
print(md, '<-', a11, a22)

16. Программа решения примера №2

P = range(20, 50); Q = range(30, 40);
md = 10000
for a2 in range(1,100):
for a1 in range(0,a2):
A=range(a1,a2)
# ! Добавлены () вокруг not() - синтаксис
f=all( ( (x not in A)<=(not((x in P)or(x in Q))) )\
for x in range(1,100))
if f:
if md > a2-a1: md=a2-a1; a11=a1; a22=a2
print(md, '<-', a11, a22)

17. Программа решения примера №2

18. Задание на множества: особенности

2 подхода к решению:
– аналитический – на основе применения законов
логики для минимизации критерия истинности;
– компьютерный перебор при помощи
программы.
2 типа заданий:
– найти множество наибольшей мощности (длины);
– найти множество наименьшей мощности (длины)

19. Задание на множества: алгоритм

Алгоритм программного решения сводится к
перебору интервала числовой оси, вдвое или более
максимального элемента заданных множеств и
проверке ложности критерия задачи.
Ложность критерия означает, что нужно удалить
"лишний" элемент в множестве максимальной
мощности или добавить рассматриваемое значение в
множество минимальной мощности.
Искомое множество изначально задано интервалом
рассмотрения (для множества max длины) или пусто
(для множества min длины).
В ответе полезно дополнительно вывести найденное
множество.

20. Задание на множества

Пример задачи № 3:
(№ 4872) Элементами множеств А, P и Q являются
натуральные числа, причём
P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20} и
Q = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50}.
Известно, что выражение
((x ∈ A) → (x ∈ P)) ∧ ((x ∈ Q) → ¬(x ∈ A))
истинно (т. е. принимает значение 1) при любом
значении переменной х. Определите наибольшее
возможное количество элементов множества A.

21. Шаблон №3 программы решения

P = {…}; Q = {…}
A = {x for x in range(1,…)}
for x in range(1,…):
if ( )==False:
A = A – {x}
print(len(A), '<-',A)

22. Программа решения примера №3

P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
Q = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50}
A={x for x in range(1,100)}
for x in range(1,100):
if ()==False:
A=A-{x}
print(len(A),'# <-', A)

23. Программа решения примера №3

P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
Q = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50}
A={x for x in range(1,100)}
for x in range(1,100):
if ( ((x ∈ A) → (x ∈ P)) ∧ \
((x ∈ Q) → ¬(x ∈ A)) )==False:
A=A-{x}
print(len(A),'# <-', A)

24. Программа решения примера №3

P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
Q = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50}
A={x for x in range(1,100)}
for x in range(1,100):
if ( ((x in A) <= (x in P)) and \
((x in Q) <= (x not in A)) )==False:
A=A-{x}
print(len(A),'
# -> ', A)

25. Программа решения примера №3

26. Задание на множества

Пример задачи № 4:
(№ 4882) Элементами множеств А, P и Q являются
натуральные числа, причём P = { 1, 2, 3, 4 } и
Q = { 1, 2, 3, 4, 5, 6 }. Известно, что выражение
¬(x ∈ A) → ¬(x ∈ P) ∨ ¬(x ∈ Q)
истинно (т. е. принимает значение 1) при любом
значении переменной х.
Определите наименьшее возможное количество
элементов множества A.

27. Шаблон №4 программы решения

P = {…}; Q = {…}
A = set()
for x in range(1,…):
if ( )==False:
A = A | {x}
#или A.add(x)
print(len(A), '<-',A)

28. Программа решения примера №4

P = { 1, 2, 3, 4 }
Q = { 1, 2, 3, 4, 5, 6 }
A = set()
for x in range(1,20):
if ()==False:
A=A|{x}
print(len(A),'# <-', A)

29. Программа решения примера №4

P = { 1, 2, 3, 4 }
Q = { 1, 2, 3, 4, 5, 6 }
A = set()
for x in range(1,20):
if ( ¬(x ∈ A) → \
¬(x ∈ P) ∨ ¬(x ∈ Q) ) == False:
A = A|{x}
print(len(A), '# <-', A)

30. Программа решения примера №4

P = { 1, 2, 3, 4 }
Q = { 1, 2, 3, 4, 5, 6 }
A = set()
for x in range(1,20):
if ( ¬(x ∈ A) → \
(¬(x ∈ P) ∨ ¬(x ∈ Q)) ) == False:
A = A|{x}
# ОБЯЗАТЕЛЬНО добавить скобки!
print(len(A), '# <-', A)

31. Программа решения примера №4

P = { 1, 2, 3, 4 }
Q = { 1, 2, 3, 4, 5, 6 }
A = set()
for x in range(1,20):
if ( (x not in A) <= \
((x not in P) or (x not in Q)) ) == False:
A = A|{x}
# ОБЯЗАТЕЛЬНО добавить скобки!
print(len(A), '# <-', A)

32. Программа решения примера №4

P = { 1, 2, 3, 4 }
Q = { 1, 2, 3, 4, 5, 6 }
A = set()
for x in range(1,20):
if ( (x not in A) <= \
((x not in P) or (x not in Q)) ) == False:
A = A|{x}
print(len(A), '# <-', A)
Ответ: 4 # <- {1, 2, 3, 4}

33. Делимость, поразрядная конъюнкция и координатная плоскость

2 подхода к решению:
– аналитический – на основе применения законов
логики для минимизации критерия истинности;
– компьютерный перебор при помощи
программы.
2 типа заданий:
– найти наибольшее значение параметра;
– найти наименьшее значение параметра.

34. Обобщенный алгоритм

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

35. Задание на делимость

Пример задачи № 5:
(№ 2251) Обозначим через ДЕЛ(n, m) утверждение
«натуральное число n делится без остатка на
натуральное число m».
Для какого наименьшего натурального числа А формула
ДЕЛ(x, A) → ДЕЛ(x, 14) ∧ ДЕЛ(x, 21)
тождественно истинна (то есть принимает значение 1
при любом натуральном значении переменной х)?

36. Шаблон №5 программы решения

for A in range(…,…):
f = all( ( … ) for x in range(…,…))
if f: print(A); break

37. Программа решения примера №5

for A in range(1,50):
f = all( ( ДЕЛ(x, A) → \
(ДЕЛ(x, 14) ∧ ДЕЛ(x, 21)) ) \
for x in range(1,50))
if f: print(A); break
# Важно!
# Интервалы рассмотрения значений возрастающие!

38. Программа решения примера №5

for A in range(1,50):
f = all( ( ДЕЛ(x, A) → \
(ДЕЛ(x, 14) ∧ ДЕЛ(x, 21)) ) \
for x in range(1,50))
# ОБЯЗАТЕЛЬНО добавить скобки!
if f: print(A); break
Заменим
ДЕЛ(x, A) ----> (x%A == 0)
¬ДЕЛ(x, A) ----> (x%A != 0)

39. Программа решения примера №5

for A in range(1,50):
f = all( ( (x%A == 0) → \
( (x%14 == 0) ∧ (x%21 == 0)) ) \
for x in range(1,50))
# ОБЯЗАТЕЛЬНО добавить скобки!
if f: print(A); break

40. Программа решения примера №5

for A in range(1,50):
f = all( ( (x%A == 0) <= \
( (x%14 == 0) and (x%21 == 0)) ) \
for x in range(1,50))
# ОБЯЗАТЕЛЬНО добавить скобки!
if f: print(A); break

41. Программа решения примера №5

for A in range(1,50):
f = all( ( (x%A == 0) <= \
( (x%14 == 0) and (x%21 == 0)) ) \
for x in range(1,50))
if f: print(A); break
Ответ: 42

42. Задание на поразрядную конъюнкцию

Пример задачи № 6:
(№ 13602 РешуЕГЭ) Обозначим через m&n поразрядную
конъюнкцию неотрицательных целых чисел m и n.
Например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого
числа А формула
x&49 ≠ 0 → (x&41 = 0 → x&А ≠ 0)
тождественно истинна (то есть принимает значение 1
при любом неотрицательном целом значении
переменной х)?

43. Шаблон №5 программы решения

for A in range(…,…):
f = all( ( … ) for x in range(…,…)):
if f: print(A); break

44. Программа решения примера №6

for A in range(0,100):
f = all( ( x&49 ≠ 0 → \
(x&41 = 0 → x&А ≠ 0) ) \
for x in range(0,100))
if f: print(A); break
# Важно!
# Интервалы рассмотрения значений возрастающие!

45. Программа решения примера №6

for A in range(1,100):
f = all( ( (x&49 ≠ 0) → \
((x&41 = 0) → (x&А ≠ 0)) ) \
for x in range(1,100))
# ОБЯЗАТЕЛЬНО добавить скобки!
if f: print(A); break

46. Программа решения примера №6

for A in range(1,100):
f = all( ( (x&49 != 0) <= \
((x&41 == 0) <= (x&А != 0)) ) \
for x in range(1,100))
# ОБЯЗАТЕЛЬНО добавить скобки!
if f: print(A); break

47. Программа решения примера №6

for A in range(1,100):
f = all( ( (x%A == 0) <= \
( (x%14 == 0) and (x%21 == 0)) ) \
for x in range(1,100))
if f: print(A); break
Ответ: 16

48. Задание на координатную плоскость

Пример задачи № 7:
(№ 1073) Укажите наибольшее целое значение А, при
котором выражение
(5y + 7x ≠ 129) ∨ (3x > A) ∨ (4y > A)
истинно для любых целых положительных значений
x и y.

49. Шаблон №6 программы решения

for A in range(…,…):
f = all( ( … ) for x in range(…,…) \
for y in range(…,…)):
if f: print(A); break

50. Программа решения примера №7

for A in range(300,0,-1):
f = all( ( (5y+7x ≠ 129) ∨ (3x>A) ∨ (4y>A) )\
for x in range(300,0,-1) \
for y in range(300,0,-1))
if f: print(A); break
# Важно!
# Интервалы рассмотрения значений убывающие!

51. Программа решения примера №7

for A in range(300,0,-1):
f = all( ( (5y+7x ≠ 129) ∨ (3x>A) ∨ (4y>A) )\
for x in range(300,0,-1) \
for y in range(300,0,-1))
if f: print(A); break

52. Программа решения примера №7

for A in range(300,0,-1):
f = all( ( (5*y+7*x!=129)or(3*x>A)or(4*y>A) )\
for x in range(300,0,-1) \
for y in range(300,0,-1))
if f: print(A); break

53. Программа решения примера №7

for A in range(300,0,-1):
f = all( ( (5*y+7*x!=129)or(3*x>A)or(4*y>A) )\
for x in range(300,0,-1) \
for y in range(300,0,-1))
if f: print(A); break
Ответ: 35

54. Спасибо за внимание!

Мы рассмотрели в этой презентации все
варианты заданий №15 экзамена ЕГЭ
Успехов в решениях!

English Русский Rules