Задача на делители егэ информатика - Помощь в подготовке к экзаменам и поступлению

На уроке рассматривается разбор 15 задания ЕГЭ по информатике, дается подробное объяснение того, как решать подобные задачи

Содержание:

Объяснение задания 15 ЕГЭ по информатике
- Элементы математической логики
- Математическая логика и теория множеств
- Задания с отрезками и ДЕЛ
- Задания с поразрядной конъюнкцией
Решение заданий 15 ЕГЭ по информатике
- Задания с множествами
- Задания с отрезками на числовой прямой
- Задания с ДЕЛ
- Задания с поразрядной конъюнкцией
- Задания на поиск наибольшего или наименьшего числа А

15-е задание: «Основные законы алгебры логики»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 5 минут.

Проверяемые элементы содержания: Знание основных понятий и законов математической логики

До ЕГЭ 2021 года — это было задание № 18 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«Важно понимать, что выражение должно быть тождественно истинно, т.е. истинно при любых допустимых значениях переменных x и у, а не только при некоторых наборах значений»

ФГБНУ «Федеральный институт педагогических измерений»

Элементы математической логики

Для выполнения задания рекомендуется повторить следующие темы:

Преобразование логических операций:

операцию импликация можно преобразовать в операции ИЛИ и НЕ:

A → B = ¬ A ∨ B
или
A → B = A + B

операцию эквивалентность можно преобразовать:

A ↔ B = A ⊕ B = A ∧ B ∨ A ∧ B
или
A ↔ B = A ⊕ B = A · B + A · B

операцию XOR (сложение по модулю 2) можно преобразовать так:

A ⊕ B = (¬A ∧ B) ∨ (A ∧ ¬B)
или
A ⊕ B = (A · B) + (A · B)

Законы алгебры логики:

кроме того, могут пригодиться базовые аксиомы и формулы:

Закон двойного отрицания:	¬¬ A = A
Закон исключения третьего:	A ∧ ¬ A = 0 или A · A = 0 A ∨ ¬ A = 1 или A + A = 1
Закон повторения (идемпотентности):	A ∧ A = A или A · A = A A ∨ A = A или A + A = A
Законы исключения логических констант:	A ∧ 0 = 0 A ∧ 1 = A A ∨ 0 = A A ∨ 1 = 1
Переместительный (коммутативный) закон:	A ∧ B = B ∧ A A ∨ B = B ∨ A
Сочетательный (ассоциативный) закон:	(A ∧ B) ∧ C = A ∧ (B ∧ C) (A ∨ B) ∨ С = A ∨ (B ∨ С)
Распределительный (дистрибутивный) закон:	(A ∧ B) ∨ C = (A ∨ C) ∧ (B ∨ C) (A ∨ B) ∧ С = (A ∧ С) ∨ (B ∧ С) и наоборот: (A ∨ B) ∧ (A ∨ C) = A ∨ (B ∧ C) (A ∧ B) ∨ (A ∧ C) = A ∧ (B ∨ C)
Закон общей инверсии (Законы де Моргана):	¬ (A ∧ B) = ¬ A ∨ ¬ B ¬ (A ∨ B) = ¬ A ∧ ¬ B
Закон исключения (склеивания):	(A ∧ B) ∨(¬A ∧ B) = B (A ∨ B) ∧(¬A ∨ B) = B
Упрощать выражения можно с помощью формул:
Закон поглощения:	A ∨ A ∧ B = A A ∧ (A ∨ B) = A A ∨ ¬A ∧ B = A ∨ B ¬A ∨ A ∧ B = ¬A ∨ B A ∧ (¬A ∨ B) = A ∧ B ¬A ∧ (A ∨ B) = ¬A ∧ B

Порядок выполнения логических операций:

выражения в скобках,
операции «НЕ»,
операции «И»,
операции «ИЛИ»,
операции «импликация»
операции «эквиваленция»

последовательность из операций импликации выполняется слева направо (при этом соблюдается принцип «операции с одинаковым приоритетом выполняются слева направо»):

A → B → C → D = ((A → B) → C) → D

Математическая логика и теория множеств

пересечение множеств соответствует логическому умножению, а объединение – логическому сложению;
пересечением двух множеств называется новое множество, состоящее из элементов, принадлежащих одновременно обеим множествам:

Пример:

объединением двух множеств называется новое множество, состоящее из элементов, принадлежащих отдельно каждому из множеств (без повторений);

Пример:

пустое множество ∅ – это множество, в котором не содержится ни одного элемента; пустому множеству в теории множеств соответствует 0;
универсальное множество U (на кругах Эйлера обозначается в виде прямоугольника) – это множество, содержащее все возможные элементы определенного типа (например, все вещественные числа):

универсальное множество соответствует логической единице: для любого множества целых чисел X справедливы равенства:

X ∨ U = U и X ∧ U = X

разностью двух множеств A и B называется новое множество, элементы которого принадлежат A, но не принадлежат B:

Пример разности множеств:

дополнение множества X – это разность между универсальным множеством U и множеством X (например, для целых чисел ¬ X – все целые числа, не входящие в X)

пусть требуется выбрать множество A так, чтобы выполнялось равенство A ∨ X = I; в этом случае множество A должно включать дополнение ¬ X, то есть A ≥¬ X (или A ⊇¬ X), то есть A_min = ¬ X
пусть требуется выбрать множество A так, чтобы выполнялось равенство ¬ A ∨ X = I, в этом случае множество ¬ A должно включать дополнение ¬ X, то есть ¬ A ⊇ ¬ X; отсюда A ⊆ X, то есть A_max = X

Для большей определенности стоит рассмотреть тему круги Эйлера

Задания с отрезками и ДЕЛ

Для решения заданий необходимо знать рассмотренную тему о множествах.

Для упрощения решений можно пользоваться следующими законами.

1. Если в задании формула тождественно истинна (равна 1), и
2. после упрощения A без отрицания
то используется закон:

A_min = ¬B

где B — известная часть выражения.

1. Если в задании формула тождественно истинна (равна 1), и
2. после упрощения A с отрицанием
то используется закон:

A_max = B

где B — известная часть выражения.

1. Если в задании формула тождественно ложна (равна 0), и
2. после упрощения A без отрицания
то используется закон:

A_max = ¬B

где B — известная часть выражения.

1. Если в задании формула тождественно ложна (равна 0), и
2. после упрощения A с отрицанием
то используется закон:

A_min = B

где B — известная часть выражения.

Задания с поразрядной конъюнкцией

В задании 15 ЕГЭ встречаются задачи, связанные с поразрядной конъюнкцией.
Например:

5 & 26

означает поразрядную конъюнкцию (логическое «И») между двоичными значениями двух чисел — 5 и 26. Выполняется так:

5  =   101₂ 
26 = 11010₂
0  = 00000₂

Задания, связанные с поразрядной конъюнкцией, решаются несколькими способами. Рассмотрим один из них.

Обозначим:

(x & K = 0) как Z_k

Для решения методом, предложенным А.В. Здвижковой, пригодится использование следующих свойств:

Z_k * Z_m = Z_{k or m}

Так, например, если в задании имеем:

(X & 5 = 0) ∧ (X & 26 = 0)

то сначала введем замену:

Z₅ ∧ Z₂₆

а затем, используя свойство 1, вычислим поразрядную дизъюнкцию двоичного значения чисел 26 и 5:

Z₅ ∧ Z₂₆ = Z_{26 or 5}
помним, что дизъюнкция - это операция логическое "ИЛИ" (сложение)
5  =   101₂ 
26 = 11010₂
31 = 11111₂

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

Z₅ ∧ Z₂₆ = Z₃₁

Z_k + Z_m = Z_{k and m}

Так, например, если в задании имеем:

(X & 28 = 0) ∨ (X & 22 = 0)

то сначала введем замену:

Z₂₈ ∨ Z₂₂

а затем, используя свойство 2, вычислим поразрядную конъюнкцию двоичного значения чисел 28 и 22:

Z₂₈ ∨ Z₂₂ = Z_{28 and 22}
помним, что конъюнкция - это операция логическое "И" (умножение)
28 = 11100₂ 
22 = 10110₂
     10100₂ = 20₁₀

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

Z₂₈ ∨ Z₂₂ = Z₂₀

Условие Z_k → Z_m истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

На деле, это означает, что если имеем:

X & 29 = 0 → X & 5 = 0  Истинно или Ложно?

то сначала введем замену:

Z₂₉ → Z₅

а затем, используя свойство 3, определим истинность высказывания Z₂₉ → Z₅:

Z₂₉ → Z₅ = 1 (истине), тогда, когда:
29 = 11101₂
5  =   101₂  
единичные биты двоичного числа 5 входят в единичные биты двоичного числа 29 
(совпадают с ними)

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

Z₂₉ → Z₅ = 1 (истинно)

(x & 125 = 5) то же самое, что и
Z₁₂₀ * ¬Z₄ * ¬Z₁ = 1 (истине)

Так, например, если в задании имеем:

X & 130 = 3

то сначала введем замену и, используя свойство 4, получим:

X & 130 = 3 то же самое, что и
Z₁₂₇ * ¬Z₂ * ¬Z₁

т.е. 3 = 2 + 1 :	

2 = 10
1 = 01
3 = 11

Решение заданий 15 ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube:

Задание демонстрационного варианта 2022 года ФИПИ

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

Множества:

15_16:

Элементами множества А являются натуральные числа. Известно, что выражение

((x ∈ {1, 3, 5, 7, 9, 11}) → ¬(x ∈ {3, 6, 9, 12})) ∨ (x ∈ A)

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное значение суммы элементов множества A.

✍ Решение:

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

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
    ⁰      ¹

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

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

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

A = {3,9}

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

3 + 9 = 12

Ответ: 12

Аналитическое решение:
📹 YouTube здесь

📹 Видеорешение на RuTube здесь

Множества:

15_17:

Элементами множества А являются натуральные числа. Известно, что выражение

(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {3, 6, 9, 12, 15}) ∧ ¬(x ∈ A)) → 
→ ¬(x ∈ {2, 4, 6, 8, 10, 12}))

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное значение суммы элементов множества A.

Типовые задания для тренировки

✍ Решение:

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

P≡(x ∈ {2, 4, 6, 8, 10, 12}) ; 
Q ≡ (x ∈ {3, 6, 9, 12, 15}) ; 
A ≡ (x ∈ A).

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

P → ((Q ∧ ¬A) → ¬P) = 
P → (¬(Q ∧ ¬А) ∨ ¬P) = 
¬P ∨ (¬(Q ∧ ¬А) ∨ ¬P) = 
¬P ∨ ¬Q ∨ А.

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

¬P ∨ ¬Q ∨ А = 1
    ⁰      ¹

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

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

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

A = {6,12}

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

6 + 12 = 18

Ответ: 18

Множества:

15_18: Закон распределения

Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}. Известно, что выражение

( (x ∈ A) → (x ∈ P) ) ∧ ( (x ∈ Q) → ¬(x ∈ A) )

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наибольшее возможное количество элементов в множестве A.

Типовые задания для тренировки

✍ Решение:

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

P ≡ (x ∈ P); 
Q ≡ (x ∈ Q); 
A ≡ (x ∈ A).

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

Избавимся от импликации:
(¬A ∨ P) ∧ (¬Q ∨ ¬A) = 1
Применим распределительный закон (но можно вывести самостоятельно):
¬A ∨ (P ∧ ¬Q) = 1

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

¬A ∨ (P ∧ ¬Q) = 1
 ⁰      ¹

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

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

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

A = {2, 4, 8, 10, 14, 16, 20}

Количество элементов = 7

Ответ: 7

Множества:

15_20:

Элементами множества А являются натуральные числа. Известно, что выражение

¬(x ∈ A) →¬(x ∈ {1, 3, 7}) ∨ (¬(x  ∈ {1, 2, 4, 5, 6}) ∧ (x ∈ {1, 3, 7}))

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное количество элементов множества A.

✍ Решение:

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

P ≡ (x ∈ {1, 3, 7}); 
Q ≡ (x  ∈ {1, 2, 4, 5, 6}); 
A ≡ (x ∈ A).

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

Избавимся от импликации:
A ∨ ¬P ∨ (¬Q ∧ P) = 1
Применим закон поглощения (но можно вывести самостоятельно):
A ∨ ¬P ∨ ¬Q = 1

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

A ∨ ¬P ∨ ¬Q = 1
 ¹      ⁰

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

¬P ∨ ¬Q = 0,
или 
P = 1 и Q = 1

Таким образом имеем пересечение двух множеств Q и P:

A = {1}

Количество элементов = 1

Ответ: 1

Задания с отрезками на числовой прямой

Отрезки на числовой прямой:

15_3:

На числовой прямой даны два отрезка: P=[44,48] и Q=[23,35].

Укажите наибольшую возможную длину отрезка А, для которого формула

((x ϵ P) → (x ϵ Q)) ∧ (x ϵ A)

тождественно ложна, то есть принимает значение 0 при любом значении переменной x.

✍ Решение:

Упростим формулу, избавившись от ‘x ϵ‘:

(P → Q) ∧ A

Теперь преобразуем импликацию в скобках:

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

(¬P ∨ Q) ∧ A

Указанные в задании отрезки отобразим на числовой прямой. Разделим отрезки на части по точкам, соответствующим их границам.

Вернемся к преобразованному выражению. В нем есть известная часть (выделим ее) и неизвестная. По условию выражение должно быть ложно:

(¬P ∨ Q) ∧ A = 0

Внешняя операция выражения — конъюнкция — ложна в трех случаях и только в одном — истинна:

(¬P ∨ Q) ∧ A
    ⁰     ^∧ ⁰ ⁼ ⁰
    ⁰     ^∧ ¹ ⁼ ⁰
    ¹     ^∧ ⁰ ⁼ ⁰
    ¹     ^∧ ¹ ⁼ ¹

Теперь рассмотрим это выражение относительно наших отрезков на числовой прямой: если известная часть выражения (¬P ∨ Q) на каком-либо отрезке прямой дает истину, то неизвестная часть (A) должна возвращать ложь (по условию формула должна быть тождественно ложна).
Рассмотрим все отрезки числовой прямой для известной части выражения:

1. (¬P ∨ Q) = 1 ∨ 0 = 1  - на данном отрезке А должно равняться 0
2. (¬P ∨ Q) = 1 ∨ 1 = 1  - на данном отрезке А должно равняться 0
3. (¬P ∨ Q) = 1 ∨ 0 = 1  - на данном отрезке А должно равняться 0
4. (¬P ∨ Q) = 0 ∨ 0 = 0  - на данном отрезке А может! равняться 1
5. (¬P ∨ Q) = 1 ∨ 0 = 1  - на данном отрезке А должно равняться 0

Получаем, что на всех отрезках кроме 4-го выражение ¬P ∨ Q истинно, т.е. на отрезках 1, 2, 3 и 5 неизвестная часть A должна быть ложной (чтобы формула вернула ложь). Отсюда следует, что А может быть истинно только на отрезке 4.
Длина отрезка 4 составляет:

48 - 44 = 4

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

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

Вывод:

PascalABC.net:

Вывод:

С подробным аналитическим решением задания 15 ЕГЭ по информатике можно ознакомиться по видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Отрезки на числовой прямой:

15_9:

На числовой прямой даны два отрезка: P = [10,20] и Q = [30,40].

Укажите наибольшую возможную длину отрезка A, для которого формула

((x ∈ P) → (x ∈ Q))  → ¬(x ∈ A)

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

Типовые задания для тренировки

✍ Решение:

Упростим выражение, введя обозначения:

A: x ∈ A
P: x ∈ P
Q: x ∈ Q

Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:

(P → Q) → ¬A = 1

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

(P → Q) → ¬A = 1        =>
¬(P → Q) ∨ ¬A = 1       =>
¬(¬P ∨ Q) ∨ ¬A = 1

Используем закон Де Моргана для последующего преобразования:

¬(¬P ∨ Q) ∨ ¬A = 1    =>
P ∧ ¬Q ∨ ¬A = 1

А — наше неизвестное, а выделенную часть формулы можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда P ∧ ¬Q = 1 (если P ∧ ¬Q = 0, то ¬А может равняться и 0 и 1, так как имеет место операция логического сложения ∨)
Значит, имеем P ∧ ¬Q = 1. Кроме того, в данном случае имеет место операция конъюнкция, которую проще вычислить, если выражение равно 1 (так как для конъюнкции существует один единственный случай истинности: 1 & 1 = 1). Таким образом имеем утверждения:

А = 1
P = 1
¬Q = 1 или Q = 0

Т.е. A истинно (=1) на промежутке пересечения отрезков P и ¬Q.
Отобразим отрезки на числовой прямой, чтобы найти искомое значение:

Очевидно, что А будет истинно, только в части 2 (на рис. желтым цветом), то есть соответствовать отрезку [10,20], имеющему длину 10.

Результат: 10

Отрезки на числовой прямой:

15_10:

На числовой прямой даны два отрезка: P = [3, 20] и Q = [6, 12].

Укажите наибольшую возможную длину отрезка A, для которого формула

((x ∈ P) ~ (x ∈ Q))  → ¬(x ∈ A)

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

✍ Решение:

Упростим выражение, введя обозначения:

A: x ∈ A
P: x ∈ P
Q: x ∈ Q

Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:

(P ~ Q) → ¬A = 1

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

(P ~ Q) → ¬A = 1      =>
¬(P ~ Q) ∨ ¬A = 1

Далее возможно 2 способа решения.

✎ 1 способ:

Избавимся от эквивалентности по правилу преобразования эквивалентности:

(a ~ b) = a * b + ¬a * ¬b

¬(P ~ Q) = ¬((P ∧ Q) ∨ (¬P ∧ ¬Q)) =
= ¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q)

Преобразуем часть данного выражения по закону Де Моргана:

¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q) =
= ¬(P ∧ Q) ∧ (P ∨ Q)

В итоге получим:

¬(P ∧ Q) ∧ (P ∨ Q) ∨ ¬A = 1

А — наше неизвестное, а выделенную часть выражения можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда, чтобы общее выражение было истинным (по условию), нужно чтобы ¬(P ∧ Q) ∧ (P ∨ Q) = 1.
Имеем:

¬(P ∧ Q) ∧ (P ∨ Q) = 1
А = 1

Отобразим отрезки на числовой прямой, чтобы найти искомое значение:

Очевидно, что А будет истинно в двух отмеченных на рисунке частях: 2 и 4 (на рис. желтым цветом). Но по условию нам необходимо найти А наибольшей длины, соответственно, выбираем отрезок [12,20], имеющий длину 8.

✎ 2 способ:
После того, как мы избавились от импликации, имеем:

¬(P ~ Q) ∨ ¬A = 1

А — наше неизвестное, а выделенную часть выражения можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда ¬(P ~ Q) = 1 (чтобы общее выражение было истинным, как указанно в условии).
Иными словами ¬(P ~ Q) истинно для всех значений x, при которых P не равно Q (т.е. либо P = 1 и Q = 0, либо P = 0 и Q = 1).
Это соответствует двум отрезкам (см. рисунок выше, желтым цветом): [3,6] и [12,20]. Но по условию нам необходимо найти А наибольшей длины, соответственно выбираем отрезок [12,20], имеющий длину 8.

Результат: 8

С решением задания 15 вы также можете ознакомиться, посмотрев видео (аналитическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Отрезки на числовой прямой:

15_11:

На числовой прямой даны два отрезка: P = [11, 21] и Q = [15, 40].

Укажите наибольшую возможную длину отрезка A, для которого формула

(x ∈ A) → ¬((x ∈ P)  ~ (x ∈ Q))

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

Типовые задания для тренировки

✍ Решение:

Упростим выражение, введя обозначения:

A: x ∈ A
P: x ∈ P
Q: x ∈ Q

Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:

A → ¬(P ~ Q) = 1

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

A → ¬(P ~ Q) = 1    =>
¬A ∨ ¬(P ~ Q) = 1

А — наше неизвестное, тогда как выделенную часть формулы можно найти. Введем предположение, что А = 1. Значит, ¬А = 0 (т.е. А = 1), тогда ¬(P ~ Q) = 1 (так как общая формула должна быть истинной по условию).
Иными словами ¬(P ~ Q) истинно для всех значений x, при которых P не равно Q (т.е. либо P = 1 и Q = 0, либо P = 0 и Q = 1).
Отобразим отрезки на числовой прямой, чтобы найти искомое значение:

Получаем, что А соответствует двум отрезкам (см. рисунок, желтым цветом): [11,15] и [21,40]. Но по условию нам необходимо найти А наибольшей длины, соответственно выбираем отрезок [21,40], имеющий длину 19.

Результат: 19

Задания с ДЕЛ

Поиск наибольшего А, известная часть Дел ∨ Дел = 1

15_7:

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

Для какого наибольшего натурального числа А формула

  (ДЕЛ(x, 40) ∨ ДЕЛ(x, 64))  → ДЕЛ(x, A)

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Типовые задания для тренировки

✍ Решение:

✎ Решение 1 (теоретическое):

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

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
      ¹          ²

В полученной формуле необходимо, чтобы искомая часть с 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:

for A in range(1,500):
    OK = 1
    for x in range(1,1000):
        OK *= ((x % 40 == 0) or (x % 64 == 0))<=(x % A== 0)
    if OK:
        print( A )

Вывод:

PascalABC.net:

begin
  for var A := 1 to 500 do
  begin
    var ok := 1;
    for var x := 1 to 1000 do
    begin
      if (((x mod 40 = 0) or (x mod 64 = 0)) <= (x mod A = 0)) = false then
      begin
        ok := 0; 
        break;
      end;
    end;
    if (ok = 1) then print(A)
  end;
end.

Вывод:

Результат: 8

Поиск наименьшего А, известная часть Дел ∧ ¬Дел = 1

15_5:

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

Для какого наименьшего натурального числа А формула

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

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Типовые задания для тренировки

✍ Решение:

✎ Решение 1 (теоретическое):

Имеем:

ДЕЛ(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
 ¹        ²

В части 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:

for A in range(1,50):
    OK = 1
    for x in range(1,1000):
        OK *= (x % A == 0) <= ((x % 28 != 0) or (x % 42== 0))
    if OK:
        print( A )
        break

PascalABC.net:

begin
  for var A := 1 to 50 do
  begin
    var ok := 1;
    for var x := 1 to 1000 do
    begin
      if (x mod A = 0) <= ((x mod 28 <> 0)or (x mod 42 = 0)) = false then
      begin
        ok := 0; 
        break;
      end;
    end;
    if (ok = 1) then begin
      print(A);
      break;
      end
  end;
end.

OK — переменная-индикатор: если находится такое А при котором, диапазон всех значений x, подставленных в выражение, возвращает истинное значение выражения, то ОК остается равным 1, т.к. используется операция умножения (до цикла ОК необходимо присвоить единице).
Следует иметь в виду, что в программировании вместо операции импликация (->) можно использовать нестрогое неравенство: <=. Т.к. таблица истинности для операции импликация соответствует операции <=:

a b   F(a<=b)
0 0      1
0 1      1
1 0      0
1 1      1

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

Результат: 3

15_6:

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

Для какого наименьшего натурального числа А формула

 (¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A)

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

✍ Решение:

✎ Решение 1 (Путём рассуждений):

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

A = ДЕЛ(x,A); 
D19 = ДЕЛ(x, 19); 
D15 = ДЕЛ(x, 15)

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

(¬D19 ∨ ¬D15) → ¬A = 1

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

D19 ∧ D15 ∨ ¬A = 1

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

¬A ∨ D19 ∧ D15 = 1
 ¹       ²

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

¬A ∨ D19 ∧ D15 = 1
 ⁰  ^∨     ¹^{= 1}

Т.е. получаем:

¬A = 0 при D19 ∧ D15 = 1
или
A = 1 при D19 = 1 и D15 = 1

Таким образом, имеем:

A = 1
D19 = 1
D15 = 1

Очевидно, что наименьшим x можем взять число 285 (15 * 19 = 285): ДЕЛ(285, 19) и ДЕЛ(285, 15)
Поскольку мы ищем наименьшее A, такое что: ДЕЛ(x, A) и при этом ДЕЛ(x, 19) и ДЕЛ(x, 15), то нам необходимо найти наименьшее делимое чисел 19 и 15:

19 * 2 = 38 (38 не делится на 15)
19 * 3 = 57 (57 не делится на 15)
19 * 4 = 76 (76 не делится на 15)
19 * 5 = 95 (95 не делится на 15)
...
19 * 10 = 190 (190 не делится на 15)
19 * 15 = 285 (285 делится на 15)

A должно быть таким числом, при котором x принимает единственно возможное (наименьшее) значение 285.
Таким наименьшим A является само число 285.

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

 (¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A)  = 1

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

for A in range(1,500):
    OK = 1
    for x in range(1,1000):
        OK *= ((x % 19 != 0) or (x % 15 != 0))<= (x % A!= 0)
    if OK:
            print( A )

a b   F(a<=b)
0 0      1
0 1      1
1 0      0
1 1      1

После запуска программы выдается одно значение А:

Результат: 285

Задания с поразрядной конъюнкцией

Поразрядная конъюнкция:

15_1:

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 1100₂&0110₂ = 0100₂ = 4

Для какого наименьшего неотрицательного целого числа A формула

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

тождественно ложна (то есть принимает значение 0 при любом неотрицательном значении переменной X)?

✍ Решение:

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

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

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

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

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

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

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

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

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

правило импликации: 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}

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

35 ≠ 0 ∧ 52 = 0 = истинно (=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 => истина), достаточно во всех разрядах «перекрыть» единицы нулями:

52	1	1	0	1	0	0
X	0	0	?	0	?	?

Мы «перекрыли» все единицы нулями, чтобы в результате получить 0.
Теперь рассмотрим 35 ≠ 0 = истина (1):

35	1	0	0	0	1	1
X	1	?	?	?	1	1

Объединим обе маски в одну:

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

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

X	0	0	?	0	1	1
A	0	0	0	0	1	1

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

000011₂ = 3₁₀

Ответ: 3

✎ Способ 2*:

Выполним последовательно следующие пункты:

Произвести замену (x & K = 0) на Zk
Выполнить преобразования по свойству импликации и закону Де Моргана.
Стремиться прийти к выражению с конъюнкциями без отрицаний типа: Zk * Zm.
Все выражения типа Zk * Zm преобразовать по свойству
Zk * Zm = Z_{k or m}.
Путем преобразований прийти к импликации: Zk → Zm.

Согласно первому пункту производим замену:

A ∧ ¬(¬Z35 → ¬Z52) = 0

Введем отрицание в выражение, чтобы оно было истинным:

¬(A ∧ ¬(¬Z35 → ¬Z52)) = 1

По закону де Моргана:

¬A ∨ (¬Z35 → ¬Z52) = 1

По свойству импликации:

¬A ∨ (Z35 ∨ ¬Z52) = 1

Объединим слагаемые с отрицанием:

¬A ∨ ¬Z52 ∨ Z35 = 1

Чтобы прийти к конъюнкции (пункт 3), используем закон де Моргана:

¬(A ∧ Z52) ∨ Z35 = 1

Чтобы прийти к импликации (пункт 5), используем свойство импликации:

(A ∧ Z52) → Z35 = 1

Получаем:

Z_{A ∨ 52} → Z35 = 1

Вспомним свойство:

Условие Zk → Zm истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

В нашем случае это говорит о том, что все единичные биты двоичной записи числа 35 должны входить в результат Z_{A or 52}.
Рассмотрим подробно:

A       = ??0?11
52      = 110100
A or 52 = 110111
35      = 100011

поскольку мы ищем наименьшее А, то:

Аmin = 11₂ = 3₁₀

Результат: 3

Детальный разбор данного задания 15 ЕГЭ по информатике предлагаем посмотреть на видео:

Вариант решения №1 (универсальный, теоретический):
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Вариант решения №2 (не универсальный, но простой):
📹 YouTube здесь

Поразрядная конъюнкция:

15_2:

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 1100₂&0110₂ = 0100₂ = 4

Для какого наибольшего неотрицательного целого числа A формула

X & A ≠ 0 → (X & 36 = 0 → X & 6 ≠ 0)

тождественно истинна (то есть принимает значение 1 при любом неотрицательном значении переменной X)?

✍ Решение:

✎ Способ 1:

Произведем замену:

z36 = (x&36 = 0), z6 = (x&6 = 0), A = (x&A = 0)

Перепишем выражение:

¬A → (z36 → ¬ z6)

Избавимся от импликации (A → B = ¬ A ∨ B):
Сначала по правилу преобразования импликации:

¬A → (z36 → ¬ z6) = A + ¬z36 + ¬z6

По Закону де Моргана вынесем отрицание за скобки (¬ (A ∧ B) = ¬ A ∨ ¬ B):

A + ¬z36 + ¬z6 = A + ¬(z36 * z6)

Вернемся опять к импликации:

A + ¬(z36 * z6) = ¬(z36 * z6) + A = (z36 * z6) → A

Суть предыдущих действий в том, что нам необходимо прийти к импликации, но, избавившись от отрицания.
По следующему правилу Z_K * Z_M = Z_{K or M} (К. Поляков) заменим конъюнкцию:

z36 * z6 = z_{36 or 6}

Выполним поразрядную дизъюнкцию двоичных чисел 36 и 6:

100100₂ -> 36
110₂ -> 6

100100
   110
100110₂ -> 36 or 6 = 38₁₀

Получаем:

z38 → A

Необходимо обеспечить истинность данного выражения при всех x. Это возможно, когда единичные биты A входят в единичные биты числа 38. То есть:

A = 100110₂ = 38₁₀

✎ Способ 2:

Так как по заданию формула должна быть тождественно истинна, то перепишем ее так:

x&A ≠ 0 → (x&36 = 0 → x&6 ≠ 0) = 1

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

A = (x&A = 0);
P = (x&36 = 0);
Q = (x&6 = 0);

Перепишем выражение согласно введенным обозначениям:

¬A → (P → ¬Q) = 1

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

A ∨ (¬P ∨ ¬Q) = 1

A — наше неизвестное; для части выражения ¬P ∨ ¬Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A была бы единица (1).
Возьмем (¬P ∨ ¬Q) = 0, тогда А должно быть только единицей (чтобы общее выражение было = 1):

A ∨ (¬P ∨ ¬Q) = 1; 
или 
1 ∨ (0) = 1

Иными словами, выражение истинно, если при ¬P ∨ ¬Q = 0, A равно единице (1).
Получаем:

¬P ∨ ¬Q = 0
Отсюда имеем: 
¬P = 0 и ¬Q = 0 

(дизъюнкция равна 0 в единственном случае, когда все операнды равны 0)

Или запишем другим образом:

Q = 1 и P = 1

Построим побитовые маски:

100100  : 36
000110  : 6
0**0**  : маска P (x&36 = 0)
***00*  : маска Q (x&6 = 0)

Сопоставим обе маски и маску x&A = 0:

0**0**  : маска P (x&36 = 0)
***00*  : маска Q (x&6 = 0)
0**00*  : общая маска x
*00**0  : маска для A (x&A = 0)
т.е. в тех битах А, где может получиться единица (звездочки в обеих масках),
 мы поставили нули.

Так как нам необходимо получить наибольшее A (по заданию), то вместо всех «звездочек» ставим единицы:

100110 = 38₁₀

Результат: 38

Подробное решение данного задания 15 ЕГЭ по информатике предлагаем посмотреть в видео уроке:
Способ 1:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
Способ 2:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Поразрядная конъюнкция:

15_8:

Определите наименьшее натуральное число А из интервала [43, 55], такое, что выражение

((x & 17 ≠ 0) → ((x & A ≠ 0) → (x & 58 ≠ 0))) →
→ ((x & 8 = 0) ∧ (x & A ≠ 0) ∧ (x & 58 = 0))

тождественно ложно (то есть принимает значение 0 при любом натуральном значении переменной х)?

Типовые задания для тренировки

✍ Решение:

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

(¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58) = 0

Для того, чтобы выражение было истинным, поставим его с отрицанием:

¬(((¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58)) = 1

Упростим выделенную часть выражения (свойство 1, теория):

Z8 ∧ Z58 = Z_{8 or 58}  :

8  =   1000  _or
58 = 111010
     111010 = 58

Получили:

Z8 ∧ Z58 = Z58

Перепишем все выражение снова, избавившись от импликации:

¬(¬(Z17 ∨ A ∨ ¬Z58) ∨ (¬A ∧ Z58)) = 1

По закону Де Моргана получим:

(Z17 ∨ A ∨ ¬Z58) ∧ ¬(¬A ∧ Z58)) = 1

Еще раз применим закон теперь ко второй скобке:

(Z17 ∨ A ∨ ¬Z58) ∧  (A ∨ ¬Z58) = 1

Используем закон поглощения:

A ∨ ¬Z58 = 1

Приведем к импликации, чтобы избавиться от отрицания:

¬Z58 ∨ A => 
 Z58 → A = 1

Поскольку по заданию нас интересует диапазон [43;55], то проверять будет с числа 43.
По свойству 3 (теория), необходимо, чтобы единичные биты А входили в единичные биты двоичного представления числа 58:

43 = 101011 - не подходит!
58 = 111010

44 = 101100 - не подходит!
58 = 111010

45 = 101101 - не подходит!
58 = 111010

46 = 101110 - не подходит!
58 = 111010

47 = 101111 - не подходит!
58 = 111010

48 = 110000 - подходит!
58 = 111010

Результат: 48

Поразрядная конъюнкция:

15_15:

Определите набольшее натуральное число A, такое что выражение

((x & 26 = 0) ∨  (x & 13 = 0)) → ((x & 78 ≠ 0) → (x & A = 0))

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)?

Типовые задания для тренировки:

✍ Решение:

Для упрощения восприятия введем обозначения:

z26 = (x & 26 = 0)
z13 = (x & 13 = 0)
z78 = (x & 78 = 0)
A = (x & A = 0)

Таким образом, получим следующее выражение:

(z26 ∨ z13) → (¬z78 → A) = 1

Упростим выражение по свойству импликации для второй скобки:

(z26 ∨ z13) → (z78 ∨ A) = 1

Упростим левую часть, используя свойство 2 (Z_k + Z_m = Z_{k and m}):

26 : 11010   единичные биты: 4, 3, 1
13 :  1101   единичные биты: 3, 2, 0
∧ =------------------------
     01000 = 8₁₀

То есть получили z26 ∨ z13 = z8
По правилу импликации: все единичные биты двоичной записи результата (z78 ∨ A) должны входить во множество единичных битов двоичной записи z8.
Рассмотрим:

z8 → (z78 ∨ A)
z78: не влияет на решение, так как операция дизъюнкция истинна тогда, 
когда хотя бы один операнд истинен
z8 → A     : ????

Для А единичными битами должны быть общие единичные биты для z8 (1000₂). Т.е. в нашим случае — это один бит — 3-й:

Наибольшее А = 1000 = 8₁₀

Результат: 8

Задания на поиск наибольшего или наименьшего числа А

Поиск наибольшего или наименьшего числа А:

15_4: 15 задание. Демоверсия ЕГЭ 2018 информатика:

Для какого наибольшего целого числа А формула

тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?

✍ Решение:

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

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

Pascalabc.net:

begin
  for var A := 200 downto -100 do
  begin
    var OK := 1;
    for var x := 0 to 100 do
      for var y := 0 to 100 do
        if ((x <= 9) <= (x * x <= A)) and ((y * y <= A) <= (y <= 9)) = false then 
        begin
          OK := 0;
          break;
        end;
    if OK = 1 then 
    begin
      print(A);
      break
    end;
  end;
end.

Бейсик:	Python: for A in range(200,-100,-1): OK = 1 for x in range(0,100): for y in range(0,100): OK = ((x<=9) <= (xx<=A)) and((y*y<=A) <= (y<=9)) if OK: print(A) break
С++:

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

Условно разделим исходное выражение на части:

Главное действие (внешняя операция) в исходном выражении — это конъюнкция. Конъюнкция истинна, когда все операнды истинны. Т.е. в задаче обе части 1 и 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
x² <= 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
y² > A

при любых y

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

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

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

Результат: 99

Подробное решение 15 задания демоверсии ЕГЭ 2018 года смотрите на видео (аналитическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Поиск наибольшего или наименьшего числа А:

✍ Решение:

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

Pascalabc.net:

begin
  for var A := -100 to 200 do
  begin
    var OK := 1;
    for var x := 1 to 100 do
      for var y := 1 to 100 do
        if ((y+3*x<A) or (x >20)or(y>40)) = false then 
        begin
          OK := 0;
          break;
        end;
    if OK = 1 then 
    begin
      print(A);
      break
    end;
  end;
end.

Бейсик:	Python: for A in range(-100,200): OK = 1 for x in range(1,100): for y in range(1,100): OK = (y+3x<A) or (x > 20) or (y > 40) if OK: print(A) break
С++:

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

Определим основные части выражения, выделив отдельно неизвестную часть — с А, и, так сказать, известную часть, то есть остальную.

    1                 2
(y+3x < A) ∨ (x > 20) ∨ (y > 40)

Поскольку основными операциями являются операции дизъюнкции (логического сложения) и порядок их выполнения не важен, то последней, внешней, операцией будем выполнять дизъюнкцию слева, т.к. она объединяет неизвестную и известную часть.
Сначала важно рассмотреть вторую часть выражения, известную, так как от нее будет зависеть значение A. Если вторая часть истинна, то А может быть как = 1, так и = 0. Такой вариант нам не подходит:

(y+3x < A) ∨ (x > 20) ∨ (y > 40)
  ^{1 или 0?                   1               = 1}
Не подходит!

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

1. (y+3x < A) = 1
2. (x > 20) ∨ (y > 40) = 0

Дизъюнкция ложна, когда оба операнда ложны, т.е. из второго пункта имеем:

x <= 20
y <= 40

Для того, чтобы перекрыть все x и все y, возьмем наибольшие из возможных значений: x = 20, y = 40.
Выразим А:

А > 3x + y
A > 3*20 + 40
A > 100

Поскольку требуется найти наименьшее значение А, то имеем А = 101.

Результат: 101

Подробное решение досрочного ЕГЭ 2018 года смотрите на видео (аналитическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Поиск наибольшего или наименьшего числа А:

15_0:Разбор 15 задания. Демоверсия егэ по информатике 2019:

Для какого наибольшего целого неотрицательного числа А выражение

(48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)

тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?

✍ Решение:
✎ Решение 1 (теоретическое):

Разделим общее выражение на две части. Выделим неизвестную часть красным:

(48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)

Неизвестная часть должна быть истинной, она обязательно будет истинна, если известная часть — ложь:

(48 ≠ y + 2x) ∨ (A < x) ∨ (A < y) = 1
      ⁰                  ¹

Т.е. 48 ≠ y + 2x = 0 или y + 2x = 48. На графике это уравнение представляет линию. Из условия имеем два ограничения:(x > 0) and (y > 0). Отобразим линию для 1-й четверти, соответствующей положительным x и y:

y + 2x = 48  :
при x = 0, y = 48
при y = 0, 2x = 48 => x = 24

Возьмем некоторое значение A, например, A = 25, отметим его на графике белой областью так, чтобы выполнялось (A < x) ∨ (A < y). По условию имеем, что все точки данной части отрезка прямой y + 2x = 48 должны принадлежать отмеченной белой области. Заштрихуем область для всех точек прямой (голубым цветом):

То есть все точки голубого квадрата должны находиться под отрезком линии (включая вершину (A, A)), и данный квадрат, соответствует максимальному значению A.
Наибольшее значение голубая область приобретает в точке пересечения прямой y + 2x = 48 с прямой y = x:

Далее решаем полученное линейное уравнение (для x = y):

x + 2x = 48 =>
3x = 48
x = 16

Так как значение A должно быть меньше x, то наибольшее А = 15.

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

for A in range(200,0,-1):
    OK = 1
    for x in range(0,100):
        for y in range(0,100):
            OK *= (48!=y+2*x) or(A<x)or (A<y) 
    if OK:
        print(A)
        break

Результат: 15

Видео решения 15 задания демоверсии ЕГЭ 2019 (аналитическое решение):
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Поиск наибольшего или наименьшего числа А:

15_19:

Для какого наименьшего целого числа А формула

(y + 5x <= 34) → ((y — x > 4) ∨ (y <= A))

тождественно истинна, т.е. принимает значение 1 при любых целых неотрицательных x и y?

✍ Решение:

Общая идея такова:
необходимо упростить формулу так, чтобы последняя операция (внешняя) выполнялась со скобкой, в которой находится искомое A. После чего разделить формулу на две части, в одной из которых находится искомое.
Избавимся от импликации, это даст нам возможность опустить общие скобки во второй части формулы:

¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A)

Разделим формулу на две части таким образом, чтобы внешняя операции отделяла часть, в которой находится искомое A:

¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A) = 1
        1 часть                  2 часть

Формула по условию должна быть истинной (=1). Внешняя операция — дизъюнкция — истинна аж в трех случаях: a=1 b=0, a=0 b=1, a=1 b=1.
Если мы допустим, что первая часть истинна, то вторая, искомая часть, может быть как истинной, так и ложной. Поэтому такой вариант не подходит.
Допустим, что первая часть ложна, тогда вторая, искомая часть, должна быть только истинной:

¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A) = 1
        1 часть = 0               2 часть = 1

С учетом, что в первой части формулу находится операция дизъюнкция, которая ложна только в одном случае (a=0 b=0), то выпишем утверждения, получившиеся из первой части:

y + 5x > 34 = 0, значит:
1. y + 5x <= 34
y - x > 4 = 0, значит:
2. y - x <= 4

Кроме того, имеем еще одно утверждение второй части:

y <= A
или
A >= y

Отобразим получившиеся уравнения прямых на плоскости:

Раз A >= y, значит, искомая область лежит выше обеих прямых. Наименьшее значение А будет достигнуто в указанной точке пересечения двух прямых.
В точке пересечения прямых уравнения равны, т.е. имеем:

34 - 5x = 4 + x
30 = 6x
x = 5
Найдем y: 
y = 4 + 5 = 9

Поскольку имеем утверждение, что A >= y и в задании требуется найти наименьшее A, то получаем:

y = 9:
A >= 9 => наименьшее A = 9

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

for A in range(-100,100):
    OK = 1
    for x in range(0,100):
        for y in range(0,100):
            OK *= (y+5*x<=34)<=((y-x >4)or(y<=A)) 
    if OK:
        print( A )
        break

PascalABC.NET:

 
begin
  for var A := -100 to 100 do
  begin
    var OK := true;
    for var x := 0 to 100 do
    begin
      for var y := 0 to 100 do
      begin
        OK := (y + 5 * x <= 34) <= ((y - x > 4) or (y <= A));
        if OK = false then break;
      end;
      if OK = false then break;
    end;
    if OK then 
    begin
      print(A);
      break;
    end;
  end;
end.

Результат: 9

Поиск наибольшего или наименьшего числа А:

15_13:

Укажите наименьшее целое значение А при котором выражение

(2y + 5x < A) ∨ (2x + 4y > 100) ∨ (3x – 2y > 70)

истинно для любых целых положительных значений x и y.

Типовые задания для тренировки

✍ Решение:

Python:

for A in range(-200,200):
    OK = 1
    for x in range(1,100):
        for y in range(1,100):
            OK *= (2*y + 5*x < A) or (2*x + 4*y > 100) or (3*x - 2*y > 70) 
    if OK:
        print( A )
        break

PascalABC.NET:

begin
  for var A := -200 to 200 do
  begin
    var OK := true;
    for var x := 1 to 100 do
    begin
      for var y := 1 to 100 do
      begin
        OK := (2*y + 5*x < A) or (2*x + 4*y > 100) or (3*x - 2*y > 70);
        if OK = false then break;
      end;
      if OK = false then break;
    end;
    if OK then 
    begin
      print(A);
      break;
    end;
  end;
end.

Результат: 171

Видео разбора задания смотрите на видео (аналитическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Поиск наибольшего или наименьшего числа А:

15_14:

Укажите наибольшее целое значение А при котором выражение

(3y – x > A) ∨ (2x + 3y < 30) ∨ (2y – x < –31)

истинно для любых целых положительных значений x и y.

Типовые задания для тренировки

✍ Решение:

✎ Решение 1 (теоретическое):

Разделим выражение на две части: часть с неизвестным = 1, часть известная = 0:

(3y – x > A) ∨ (2x + 3y < 30) ∨ (2y – x < –31) = 1

Выпишем отдельно обе скобки известной части:

(1) 
(2x + 3y) >= 30,
y >= (30 - 2x) / 3
x = (30 - 3y) /2

(2) 
(2y – x >=–31)
y >= (x - 31) / 2
x = 2y + 31

Подберем значения координат для x и y обеих частей, и отобразим линии на графике функций:

(1)
x | y
0 | 10
15| 0

(2)
x | y
0 | -15 ( целые)
30|0

Для первого уравнения:

Для второго уравнения:

Сопоставим обе области:

Добавим на график прямую A<3y-x:

Раз A < 3y – x, то будем перемещать А снизу вверх. Наибольшее значение А будет достигнуто в указанной точке пересечения с прямой (2).
Т.е. для уравнения (2) имеем:

если y = 1, то x = 2*1 + 31 = 33

Подставим в выражение для поиска А:

А < 3y - x
A < 3-33, A < -30, A=-31

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

for A in range(200,-200,-1):
    OK = 1
    for x in range(1,100):
        for y in range(1,100):
            OK *= (3*y-x>A) or (2*x+3*y<30) or (2*y-x<-31) 
    if OK:
        print(A)
        break

Результат: -31

* В некоторых задачах использован метод, предложенный А.В. Здвижковой

Источник

Всем привет! Добрались мы до 25 задания из ЕГЭ по информатике 2023.

Рассмотрим типовые задачи, а так же новые формулировки 25 задания из ЕГЭ по информатике 2023.

Приступаем к первой классической задаче.

Задача (ЕГЭ по информатике, Демо 2022)

Пусть M – сумма минимального и максимального натуральных делителей
целого числа, не считая единицы и самого числа. Если таких делителей
у числа нет, то значение M считается равным нулю.

Напишите программу, которая перебирает целые числа, бо́льшие 700 000,
в порядке возрастания и ищет среди них такие, для которых значение M
оканчивается на 8. Выведите первые пять найденных чисел
и соответствующие им значения M.

Формат вывода: для каждого из пяти таких найденных чисел в отдельной
строке сначала выводится само число, затем – значение М.
Строки выводятся в порядке возрастания найденных чисел.

Количество строк в таблице для ответа избыточно.

Решение:

На ЕГЭ по информатике 2023 удобно писать программы на языке Python.

import math
count=0
for i in range(700001, 800000):

    b=0
    
    for j in range(2, int(math.sqrt(i)) + 1):
        if i%j==0:
            b=i//j
            break
    
    
    if  b==0: M=0
    else: M=j+b

    if M!=0 and M%10==8:
        count=count+1
        print(i, M)

    if count==5: break

В данной программе перебираются числа в цикле for, начиная с 700001.

Переменная b — считается наибольшим делителем числа i. Затем, с помощью ещё одного цикла for перебираются числа с 2 до корня числа i (включительно). Ищем тем самым наименьший делитель.

Если до корня числа включительно не встретился ни один делитель, значит, у числа нет делителей, кроме 1 и самого числа.

Пусть у нас есть число A. Если у этого числа есть делитель d1, то он находится до корня этого числа. А вот то число (так же делитель d4), на которое умножается d1, чтобы получить A, будет находиться после корня A.

Получается, что у каждого делителя есть своя пара. У единицы — это само число. Причём один делитель из пары находится до корня, другой после корня. Исключением будет тот случай, когда из числа А извлекается целый корень. Тогда для этого корня не будет пары (парой и будет само это число √A * √A = A).

Таким образом, первый найденный делитель будет являться наименьшим делителем. А вот делительный, который находится в паре с наименьшим делителем, будет наибольшим.

После того, как мы нашли наименьший делитель (он будет сидеть в переменной j) и наибольший делитель b, выходим из второго цикла for.

Если переменная b осталась равна нулю, то, значит, у числа i нет указанных делителей, и переменная M должна равняться 0. Если b не равна нулю, то M=j+b.

Проверить, на что оканчивается число, можно узнав остаток от деления числа на 10.

Переменная count следит, чтобы было распечатано ровно 5 чисел, которые удовлетворяют условию задачи.

Ответ:

700005	233338
700007	100008
700012	350008
700015	140008
700031	24168

Задача (Стандартная)

Напишите программу, которая перебирает целые числа, большие 550 000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель, не равный самому числу, не является простым числом.

Программа должна найти и вывести первые 6 таких чисел и соответствующие им значения упомянутых делителей.

Формат вывода: для каждого из 6 таких найденных чисел в отдельной строке сначала выводится само число, затем упомянутый делитель. Строки выводятся в порядке возрастания найденных чисел.

Например, для числа 105 наибольший натуральный делитель 35 не является простым, для числа 15 наибольший натуральный делитель 5 — простое число, а для числа 13 такого делителя не существует.

Решение:

Здесь мы ищем наибольший делитель числа, как и в прошлом решении.

import math

def Pr(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x%i==0: return False
    return True


count=0
for i in range(550001, 1000000):

    b=0
    
    for j in range(2, int(math.sqrt(i)) + 1):
         if i%j==0:
            b=i//j
            break


    if not(Pr(b)):
        count=count+1
        print(i, b)

    if count==6: break

Чтобы проверить число, является ли оно простым, напишем функцию Pr(). Там мы проходим до корня числа. Если не встретился не один делитель, значит, число простое — возвращаем True. Если до корня хотя бы один делитель встретили — возвращаем False.

Ответ:

550002	275001
550004	275002
550005	183335
550008	275004
550010	275005
550011	183337

Задача (Ровно 4 различных делителя)

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [258274; 258297], числа, имеющие ровно 4 различных делителя. Выведите для каждого найденного числа два наибольших делителя в порядке возрастания.

Решение:

import math

for i in range(258274, 258298):
    a=[]
    for j in range(1, int(math.sqrt(i))+1):
        if i%j==0:
            a.append(j)
            b=i//j
            if j!=b:
                a.append(b)

    if len(a)==4:
        a.sort()
        print(a[2], a[3])

Здесь для каждого числа i заводим массив a, где будем сохранять все его делители. Идём как всегда до корня. Если мы нашли делитель, мы добавляем его в массив a c помощью команды append и ищем его «брата». Второй делитель («брат») не должен равняться самому делителю j, т.к. нам сказали, что все делители должны быть различны. Одинаковые делители j и b могут получится, если из нашего числа i извлекается целый корень. Ведь для делителя √i является парой этот же делитель ( √i* √i=i).

После прохождения внутреннего цикла (с переменной j) в массиве a будут сидеть все делители числа i. Если их ровно 4, то сортируем массив a и выводим на экран два наибольших.

Ответ:

15193	258281
1427	258287
1493	258289
36899	258293
51659	258295

Задача (Крепкий орешек)

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Найдите все натуральные числа, принадлежащие отрезку [4234679; 10157812] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе само число и его наибольший нетривиальный делитель. Найденные числа расположите в порядке возрастания.

Решение:

import math

for i in range(4234679, 10157813):
    if int(math.sqrt(i))**2 == i:
        a=[]
        for j in range(2, int(math.sqrt(i))+1):
            if i%j==0:
                a.append(j)
                b=i//j
                if j!=b:
                    a.append(b)
        if len(a)==3:
            a.sort()
            print(i, a[2])

Как у нас могут быть три различных нетривиальных делителя, когда делители идут, как мы выяснили, парами? Это может быть, когда существует целый корень из этого числа. Тогда в паре два числа будут одинаковыми (√i* √i = i). Поэтому в этой задаче нас интересуют числа из которых извлекается елый корень.

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

Далее, решаем, как и в прошлый раз.

Ответ:

4879681	103823
7890481	148877

Задача (ЕГЭ по информатике, 20.06.22)

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

— символ «?» означает ровно одну произвольную цифру;

— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответсвуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10⁸, найдите все числа, соответствующие маске 1234*7, делящиеся на 141 без остатка.

В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 141.

Решение:

Здесь самый главный момент заключается в том, что есть верхняя граница 10⁸. Т.е. самое большое число, которое нужно рассмотреть 1234[999]7 <= 10⁸ = 100000000. Нижняя граница тоже задана, когда вместо звёздочки ни одной цифры не будет 12347.

i=12347

#Вместо звёздочки ноль разрядов
if i%141==0:
    print(i, i//141)

#Вместо звёздочки один разряд
for x in '0123456789':
    s = '1234' + x + '7'
    i=int(s)
    if i%141==0:
        print(i, i//141)

#Вместо звёздочки два разряда
for x in '0123456789':
    for y in '0123456789':
        s = '1234' + x + y + '7'
        i=int(s)
        if i%141==0:
            print(i, i//141)

#Вместо звёздочки три разряда
for x in '0123456789':
    for y in '0123456789':
        for z in '0123456789':
            s = '1234' + x + y + z + '7'
            i = int(s)
            if i%141==0:
                print(i, i//141)

Таким образом, нужно рассмотреть, когда вместо звёздочки ноль разрядов, один разряд, два разряда и три разряда.

Каждый разряд перебираем как цифры (символы). Формируем строку s, а затем её переводим в тип int.

Когда два разряда или три разряда нужно перебирать строку с помощью вложенных циклов.

Ответ:

1234737	8757
12341307	87527
12342717	87537
12344127	87547
12345537	87557
12346947	87567
12348357	87577
12349767	87587

Источник

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Дан набор из N целых положительных чисел. Из этих чисел формируются все возможные пары (парой считаются два элемента, которые находятся на разных местах в наборе, порядок чисел в паре не учитывается), в каждой паре вычисляются сумма и произведение элементов. Необходимо определить количество пар, у которых сумма нечётна, а произведение делится на 3.

Напишите эффективную по времени и по памяти программу для решения этой задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает одного килобайта и не увеличивается с ростом N.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,  — 4 балла.

Максимальная оценка за правильную программу, эффективную только по времени или только по памяти,  — 3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,  — 2 балла.

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

Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Описание входных и выходных данных.

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 100.

Пример входных данных:

Пример выходных данных для приведённого выше примера входных данных:

Из четырёх чисел можно составить 6 пар. В данном случае условиям удовлетворяют две пары: (2, 3) и (3, 4). Суммы чисел в этих парах (5 и 7) нечётны, а произведения (6 и 12) делятся на 3. У всех остальных пар как минимум одно из этих условий не выполняется.

Напишите эффективную по времени и по памяти программу для решения этой задачи.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,  — 2 балла.

Описание входных и выходных данных.

Пример входных данных:

Пример выходных данных для приведённого выше примера входных данных:

Из четырёх чисел можно составить 6 пар. В данном случае условиям удовлетворяют две пары: (2, 5) и (4, 5). Суммы чисел в этих парах (7 и 9) нечётны, а произведения (10 и 20) делятся на 5. У всех остальных пар как минимум одно из этих условий не выполняется.

Дан набор из N целых положительных чисел. Из них нужно выбрать и вывести два числа так, чтобы их сумма была нечётна, а произведение делилось на 3 и при этом было максимально возможным. Выбранные числа можно выводить в любом порядке. Если есть несколько подходящих пар, можно выбрать любую из них. Если подходящих пар нет, нужно вывести 0.

Напишите эффективную по времени и по памяти программу для решения этой задачи.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,  — 2 балла.

Описание входных и выходных данных.

Пример входных данных:

Пример выходных данных для приведённого выше примера входных данных:

3 4

Из 5 чисел можно составить 10 пар. В данном случае условиям удовлетворяют две пары: (2, 3) и (3, 4). Суммы чисел в этих парах (5 и 7) нечётны, а произведения (6 и 12) делятся на 3. У всех остальных пар как минимум одно из этих условий не выполняется. Из двух возможных пар выводим ту, в которой больше произведение элементов.

Дан набор из N целых положительных чисел. Из них нужно выбрать и вывести два числа так, чтобы их сумма была нечётна, а произведение делилось на 5 и при этом было максимально возможным. Выбранные числа можно выводить в любом порядке. Если есть несколько подходящих пар, можно выбрать любую из них. Если подходящих пар нет, нужно вывести 0.

Напишите эффективную по времени и по памяти программу для решения этой задачи.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,  — 2 балла.

Описание входных и выходных данных.

Пример входных данных:

Пример выходных данных для приведённого выше примера входных данных:

4 5

Из 5 чисел можно составить 10 пар. В данном случае условиям удовлетворяют две пары: (2, 5) и (4, 5). Суммы чисел в этих парах (7 и 11) нечётны, а произведения (10 и 20) делятся на 5. У всех остальных пар как минимум одно из этих условий не выполняется. Из двух возможных пар выводим ту, в которой больше произведение элементов.

Пройти тестирование по этим заданиям

Источник

ЕГЭ информатика 15 задание разбор, теория, как решать.

Преобразование логических выражений, (П) — 1 балл

Е15.42 Для какого наименьшего натурального числа А формула (ДЕЛ(x, 2) → ¬ДЕЛ(x, 3)) / (x + A ≥ 100)

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула (ДЕЛ(x, 2) → ¬ДЕЛ(x, 3)) / (x + A ≥ 100) тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х? Ответ: Демонстрационный вариант ЕГЭ 2023 г. – задание №15

Е15.41 для которого формула ((x ∈ Q) ≡ (x ∈ P)) ∨ (¬(x ∈ A) → ((x ∈ P) ∧ ¬(x ∈ Q))) тождественно истинна

На числовой прямой даны два отрезка: P = [ 6; 4 5] и Q = [18; 52]. Укажите наименьшую возможную длину такого отрезка A, для которого формула ((x ∈ Q) ≡ (x ∈ P)) ∨ (¬(x ∈ A) → ((x ∈ P) ∧ ¬(x ∈ Q))) тождественно истинна (т. е. принимает значение 1 при любом …

Е15.40 выражение (2у + 3х ≠ 135) ∨ (у > А) ∨ (x > A) истинно

Определите наибольшее целое значение A, при котором выражение (2у + 3х ≠ 135) ∨ (у > А) ∨ (x > A) истинно для любых целых положительных значений х и у. Ответ: Апробация ЕГЭ по информатике 19 февраля 2022 – задание №15 Тренировочный экзамен по информатике и ИКТ (КЕГЭ) в компьютерной форме

Е15.39 формула (x ∈ Q) → (((x ∈ P) ≡ (x ∈ Q)) ∨ (¬(x ∈ P) → (x ∈ A))) тождественно истинна

На числовой прямой даны два отрезка: P = [69; 91] и Q = [77; 114]. Укажите наименьшую возможную длину такого отрезка A, для которого формула (x ∈ Q) → (((x ∈ P) ≡ (x ∈ Q)) ∨ (¬(x ∈ P) → (x ∈ A))) тождественно истинна (т. е. принимает значение 1 при любом значении переменной …

Е15.38 выражение ((x & 26 ≠ 0) ∨ (x & 13 ≠ 0)) → ((x & 29 = 0) → (x & A ≠ 0)) тождественно истинно

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4 . Определите наименьшее натуральное число A, такое что выражение ( (x & 26 ≠ 0) ∨ (x & 13 ≠ 0)) → ((x & 29 = 0) → (x & A ≠ 0)) тождественно истинно …

Е15.37 формула (x ∈ Q) → (¬(x ∈ P) → ¬((x ∈ Q) ∧ ¬(x ∈ A))) тождественно истинна

На числовой прямой даны два отрезка: P = [19; 94] и Q = [4; 61]. Укажите наименьшую возможную длину такого отрезка A, для которого формула (x ∈ Q) → (¬(x ∈ P) → ¬((x ∈ Q) ∧ ¬(x ∈ A))) тождественно истинна (т. е. принимает значение 1 при любом значении переменной х). Ответ: источник: …

Е15.36 формула ( (x ∈ А) → (x ∈ P) ) / (x ∈ Q) тождественно истинна

На числовой прямой даны два отрезка: P = [5, 17] и Q = [13, 23]. Найдите наибольшую возможную длину отрезка A, при котором формула ( (x ∈ А) → (x ∈ P) ) / (x ∈ Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Ответ: источник: informatikaexpert.ru

Е15.35 ДЕЛ(A, 40) / (ДЕЛ(780, x) → (¬ДЕЛ(A, x) → ¬ДЕЛ(180, x)))

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула ДЕЛ(A, 40) / (ДЕЛ(780, x) → (¬ДЕЛ(A, x) → ¬ДЕЛ(180, x))) тождественно истинна, то есть принимает значение 1 при любом натуральном x? Ответ: СтатГрад Вариант ИН2010401 17.03.2021– задание №15

Е15.34 формула x & 85 = 0 → (x & 54 ≠ 0 → x & А ≠ 0) тождественно истинна

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула x & 85 = 0 → (x & 54 ≠ 0 → x & А ≠ 0) тождественно истинна (т. е. принимает …

Е15.33 формула ((x ∈ P) ∧ ¬(x ∈ A)) → ¬(x ∈ Q) тождественно истинна

На числовой прямой даны два отрезка: P = [10, 32] и Q = [18, 45]. Найдите наименьшую возможную длину отрезка A, при котором формула ((x ∈ P) ∧ ¬(x ∈ A)) → ¬(x ∈ Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Источник: informatikaexpert.ru

Источник

На этой странице вы узнаете

Как быстро работает программа?
Есть ли смысл перебирать делители после корня?
Что количество делителей может сказать о самом числе?

Гадание на кофейной гуще или на картах Таро? Может, на ромашке? Хотя лучше не доверять свои отношения цветку. Наша судьба — только в наших руках. А судьба чисел предопределена заранее. Сегодня мы будем предсказывать их жизнь и судьбу по делителям. Но главная проблема — найти эти делители.

Постановка проблемы. Переборное решение

Встречали ли вы странных персонажей в задачах, которым резко понадобилось купить 50 арбузов? А что подумаете, если ваш учитель математики задаст найти число, у которого 50 делителей?

Поиск делителей в математике не самый сложный процесс. Есть разные способы: разложение на простые множители, обычный перебор и так далее. Сложность задания будет зависеть от самого числа. Довольно быстро получится найти делители числа 24 — число небольшое, красивое, удобное. Нахождение делителей числа 1234567 займет гораздо больше времени.

Я предлагаю включить компьютер, открыть среду разработки и заставить код сделать за нас всю работу.

Идея в следующем:

Создадим список, в который мы сохраним все делители числа.
С помощью цикла for переберем все числа из диапазона от 1 до самого числа.
Если в переборе мы нашли такое число, которое является делителем исходного — остаток от деления будет равен 0 — сохраним это число в список.

В итоге мы получим список всех делителей исходного числа.

number = 1234567
dels = []

for i in range(1, number + 1):
	if number % i == 0:
		dels.append(i)

print(dels)
_____________________________________________________________________
Вывод: [1, 127, 9721, 1234567]

У этого метода есть очень большая проблема — время его работы.

Программа выполняет команды очень быстро, но не бесконечно быстро.

Как быстро работает программа?

Время работы программы можно измерить. Например, Sublime Text 3 занимается этим автоматически. И он помог посчитать, что программа выше выполнилась за 0.2 секунды. Давайте постепенно повышать ставки и смотреть, сколько времени понадобится этой же программе для поиска делителей других чисел:
— число 1234567 — 0.2 секунды;
— число 12345670 — 0.9 секунды;
— число 123456700 — 8.0 секунд;
— число 1234567000 — 115.7 секунд.

С числом 1234567 программа сделала 1234567 шагов цикла for, и справилась неимоверно быстро. Но чем больше ей придется выполнять команд, тем дольше придется работать.

Замеры времени зависят от многих факторов, например, мощности компьютера. Но мы можем повысить эффективность работы программы.

Ускоренный перебор делителей

Идея ускоренного перебора делителей заключается в том, что, найдя один делитель, мы сразу можем подобрать второй — его пару.

Возьмем число 24. Найдя его делитель 2, мы сразу можем сказать, что у 24 есть еще один делитель — 12, потому что 12 = 24 / 2. Интересная мысль? Давайте ее развивать.

Найдем по такой логике все делители числа 16.

Самый простой делитель числа — 1. И по этой логике сразу найдем второй делитель — само число 16, так как 16 / 1 = 16.

Проверим число 2. Это делитель, так что сразу найдем его пару: 16 / 2 = 8.

Проверяем число 3 — это не делитель, его просто пропускаем.

При проверке числа 4 мы столкнемся с интересной ситуацией. Его парой будет 16 / 4 = 4 — то же самое число, а мы ищем различные пары. Значит, у корня числа пары не будет: найдя корень, мы найдем только один делитель.

Если мы продолжим перебор, числа 5, 6 и 7 — не будут делителями. А за ними — 8, делитель, который мы уже нашли.

Есть ли смысл перебирать делители после корня?

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

Если у числа целого корня нет, перебираем до его округленного вниз значения.
Нам нет смысла перебирать числа после корня, так что будем перебирать до предельно близкого к нему значения, но не больше.

Логика программы будет такой:

Перебираем числа от 1 до корня исходного числа.
Если мы нашли корень числа, добавляем в список делителей только его.
Если мы нашли не корень, а обычный делитель — добавляем в список сразу пару делителей.

Пример реализации ускоренного перебора делителей для числа 1234567000:

number = 1234567000
dels = []

for i in range(1, int(number ** 0.5) + 1):
	if i * i == number:
		dels.append(i)
	elif number % i == 0:
		dels.append(i)
		dels.append(number // i)

print(len(dels))
_____________________________________________________________________
Вывод: 64

Эта программа нашла все делители числа и выдала их количество — 64. А на ее работу ушло меньше секунды.

Но и это не панацея. Что, если нам придется проверить делители сразу нескольких чисел? Например, мы хотим найти все числа, у которых ровно 7 делителей, в диапазоне от 1 до 10000.

Программу надо немного модифицировать:

заведем переменную-счетчик, которая будет считать подходящие числа;
number сделаем перебираемой переменной по нужному диапазону с помощью цикла for;
ускоренный перебор будет внутри перебора number;
в конце каждого шага цикла проверяем — если делителей у числа ровно 7, то увеличиваем наш счетчик на 1.

Теперь программа будет выглядеть следующим образом:

count = 0
for number in range(1, 10000):
	dels = []

	for i in range(1, int(number ** 0.5) + 1):
		if i * i == number:
			dels.append(i)
		elif number % i == 0:
			dels.append(i)
			dels.append(number // i)

	if len(dels) == 7:
		count += 1

print(count)
_____________________________________________________________________
Вывод: 2

Эта программа работала всего 0.2 секунды. Звучит неплохо, но давайте снова поднимать ставки:

диапазон 1 — 10000 — 0.2 секунды;
диапазон 1 — 100000 — 2.6 секунды;
диапазон 1 — 1000000 — 80.2 секунды.

Время снова увеличивается очень быстро. Что можно с этим сделать?

Еще более ускоренный перебор делителей

Не считаем, что не нужно

Обратите внимание — программа выше нашла среди чисел 1–10000 всего 2 числа, имеющих ровно 7 делителей. А сколько же у остальных? Может быть и больше, может быть и меньше. Например, у числа 9864 делителей аж 24 штуки. Стоило ли тратить время на поиск их всех, если количество делителей больше 7?

Конечно, нет. Как только мы нашли 8 штук, мы уже можем понять, что анализировать число далее нам неинтересно. Значит, нужно остановить работу цикла.

Команда break полностью останавливает работу цикла.

Мы можем модернизировать нашу последнюю программу: если в переборе делителей мы увидим, что их больше семи, завершаем цикл командой break.

count = 0
for number in range(1, 10000):
	dels = []

	for i in range(1, int(number ** 0.5) + 1):
		if i * i == number:
			dels.append(i)
		elif number % i == 0:
			dels.append(i)
			dels.append(number // i)
		if len(dels) > 7:
			break

	if len(dels) == 7:
		count += 1

print(count)

При этом завершится именно цикл перебора делителей i, так как break находится именно в нем, а цикл перебора number продолжит свою работу.

Давайте произведем замеры еще раз:

диапазон 1-10000 — 0.2 секунды;
диапазон 1-100000 — 2.1 секунды;
диапазон 1-1000000 — 53.5 секунды.

В последнем случае мы сэкономили около трети от времени работы программы. Но и это не предел.

Не считаем, что не нужно 2.0

Вернемся на несколько абзацев выше, когда мы искали делители числа 16. Мы нашли 5 делителей — 2 пары и 1 корень, который не даст пару. Это справедливо для любого числа: целый корень не будет давать пару ни с каким другим числом, а все остальные делители — будут.

Что количество делителей может сказать о числе?

Если у числа есть целый корень, количество делителей числа будет нечетным, так как корень не даст пару ни с кем.
Если же у числа целого корня нет — количество его делителей будет четным, так как все делители будут иметь пару.

Нам нужны числа, у которых ровно 7 делителей. Следовательно, нам нужны числа, у которых есть целый корень. Это можно проверить, вычислив точный корень числа и его округленное значение. Если они совпадут, значит, округлять корень было некуда и он целый.

Но как пропускать числа, которые нам не нужны?

Команда continue останавливает работу текущего шага цикла и сразу переходит к следующему.

Если мы найдем число number, у которого нет целого корня, мы можем применить команду continue: данный шаг цикла перебора number завершается, и мы сразу перейдем к следующему.

Включить эту проверку в программу можно следующим образом:

count = 0
for number in range(1, 10000):
	if number ** 0.5 != int(number ** 0.5):
		continue

	dels = []

	for i in range(1, int(number ** 0.5) + 1):
		if i * i == number:
			dels.append(i)
		elif number % i == 0:
			dels.append(i)
			dels.append(number // i)
		if len(dels) > 7:
			break

	if len(dels) == 7:
		count += 1

print(count)

Снова посмотрим на время работы программы при разных диапазонах:

диапазон 1-100000 — 0.1 секунды;
диапазон 1-1000000 — 0.5 секунды;
диапазон 1-10000000 — 4.5 секунды;
диапазон 1-100000000 — 44.4 секунды.

А делители — это вообще для чего? А таблицы со временем — это точно важно? Может, подождать проще, чем учить все это?

Нахождению делителей чисел посвящена задача 25 ЕГЭ, и без этих теоретических знаний решить ее крайне сложно. Что же касается времени работы, то за ним приходится следить внимательнейшим образом, ведь в задачах могут встречаться ситуации, когда надо найти делители для сотен миллионов чисел за раз!

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

Фактчек

Ускоренный перебор делителей подразумевает нахождение делителей попарно, при этом перебирать делители достаточно только до корня числа.
Команда break полностью останавливает работу цикла, а команда continue завершает работу лишь текущего шага цикла, перенося нас сразу на следующий.
Если у числа есть целый корень, количество делителей числа будет нечетным, так как корень не даст пару ни с кем. Если же у числа целого корня нет — количество его делителей будет четным, так как все делители будут иметь пару.

Проверь себя

Задание 1.
Для чего нужен ускоренный перебор делителей?

Обычный перебор слишком скучный
Для большей точности вычислений
Для ускорения работы программы

Задание 2.
Найдите количество делителей числа 2568568668.

Задание 3.
Найдите, сколько чисел из диапазона от 2000 до 1002000 имеют ровно 5 делителей.

Ни одного
1
10
8

Ответы: 1. — 3; 2. — 3; 3. — 4.

Источник

Примерное время на чтение статьи: 9 минут

Модуль school, встроенный в последние версии PascalABC.Net, содержит реализацию алгоритмов, часто встречающихся в школьных задачах. Их использование сильно сокращает программный код и упрощает решение задачи. Каждая реализация в основном имеет два формата – для вызова в виде функции и для записи в точечной нотации. Рассмотрим типовые для номера 25 задачи ЕГЭ и их решение двумя способами: без использования функций модуля school и с его помощью.

Нахождение делителей числа

При нахождении нетривиальных делителей натурального числа ? (которые отличны от 1 и самого числа ?) часто предлагается перебирать числа из диапазона от 2 до [?/2] (скобки [] обозначают операцию взятия целой части числа), поскольку на интервале от [?/2]+1 до ?−1 у числа ? нет делителей. При таком подходе для нахождения делителей, например ?=10000 придется перебрать 4999 чисел (от 2 до 5000).

Перебор делителей числа ? можно оптимизировать, учитывая, что наименьший из пары делителей, таких что ?∗?=?, не превышает квадратного корня из ?; нужно только аккуратно обработать случай, когда число ? представляет собой квадрат целого числа. В этом случае для нахождения делителей, например ?=10000 придется перебрать уже 99 делителей (от 2 до 100=sqrt(10000)).

Получается, что для определения количества делителей числа ? достаточно перебирать только числа от 2 до √N; если очередной делитель ? – это точный квадратный корень, добавляем в список делителей только один делитель, если нет – то добавляем пару делителей (?, [?/?]). Потом (или сразу) необходимо добавить к списку делителей единицу и само число ?.

PascalABC модуль school: список делителей числа

В PascalABC.Net для получения списка ????, содержащего все натуральные делители числа ?, включая 1 и ?, могут быть использованы:

функция ????????(?), которая в зависимости от типа ?, возвращает значение типа ????<???????> или ????<???64>;
расширение ?.???????? – делает то же самое.

Задача

Вывести все делители натурального числа ?.

Способ 1 (без school)

## 
  var n := ReadInteger;
  var lstDel := Lst(1);          // в список делителей добавили 1
  if n > 1 then lstDel.add(N); // числа от 1 имеют два делителя: 1 и N
  var lim := round(sqrt(N));
  for var d := 2 to lim do 
      if n.Divs(d)
      then if d = sqrt(N)
           then lstDel.add(d)
           else begin
                   lstDel.Add(d);
                   lstDel.Add(N div d)
                 end;
  lstDel.Sort;
  println('Делители:', lstDel);  
  println('Количество делителей:', lstDel.Count);

Способ 2 (используя модуль school)

## 
uses school;
  var n := ReadInteger;
  println('Делители:', n.Divisors);

Разложение числа в произведение простых множителей

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

PascalABC модуль school: разложение числа ? на простые множители

В PascalABC.Net для получения списка ????, содержащего все простые делители числа ?, могут быть использованы:

функция ?????????(?) – выполняет разложение числа ? типа ??????? или ???64 на простые множители, результат помещается в список ????;
расширение ?.????????? делает то же самое.

Задача

Разложить натуральное число ? в произведение простых множителей.

Рассмотрим реализацию решения задачи без использования функции ?????????(?) модуля ??ℎ???, а затем с её использованием.

Способ 1 (без school)

##
  var n := ReadInteger;
  var ans := n.ToString + ' = ';
  var prime := true;
  var lstPrimeDel := new List <integer>;
  for var d := 2 to n do
    begin
      while n mod d = 0 do begin
        lstPrimeDel.Add(d);
        prime := false;
        n := n div d
      end;
      if n = 1 
      then break
      else if (d*d>n) and prime
           then break      
    end;
  if prime then lstPrimeDel.Add(n);
  ans += lstPrimeDel.JoinToString(' * ');
  ans.Println;

Способ 2 (используя модуль school)

##
uses school;
  var n := ReadInteger;
  var rez := Factorize(n);
  var ans := n.ToString + ' = ' + rez.JoinToString(' * ');
  ans.Println;

Другие полезные функции модуля school

PascalABC модуль school: простые числа

функция ??????(?) – возвращает список ????, содержащий простые числа на отрезке [2; ?];
функция ???????????(?) – возвращает список ????, содержащий первые ? простых чисел;
расширение ?.??????? – возвращает ????, если ? – простoе и ????? в противном случае. Переменная ? должна быть типа ??????? или ???64.

PascalABC модуль school: нахождение НОД и НОК пары чисел a и b

функция НОД(?,?) – возвращает НОД типа ??????? или ???64;
расширение ?.НОД – возвращает НОД для кортежа ?=(?,?) с данными типа ??????? или ???64;
функция НОК(?,?) – возвращает НОК типа ???64;
функция НОДНОК(?,?) – возвращает кортеж вида (НОД,НОК) для пары чисел ? и ? типа ???64.

##
uses School;
    var (n, m) := ReadInteger2;
    НОД(n, m).Println;
    НОК(n, m).Println;

PascalABC модуль school: список цифр числа

Получение списка ????, содержащего все цифры числа ? в порядке их следования слева направо:

функция ??????(?) – возвращает список типа ????<???64>;
расширение ?.?????? делает то же, возвращая список типа ????<???????> или ????<???64>.

##
    uses school;
    var n := ReadInteger;
    n.Digits.Sum.print;

Решение типовых задач ЕГЭ

Демо к ЕГЭ 2021

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.

Ответ:

3 58153
7 24923
59 2957
13 13421
149 1171
5 34897
211 827
2 87251

Способ 1 (без school)

##
  var (a, b) := (174457, 174505);
  var maxd: integer;
  for var n := a to b do
  begin
    var kd := 0;
    for var d := 2 to n div 2 do
      if n mod d = 0 
      then begin
             kd += 1;
             maxd := d;
           end;
      if kd = 2 then println(n div maxd, maxd)
  end;

Способ 2 (используя модуль school и лямбда-выражения)

##
uses school;
  (174457..174505)         // возврати все числа из диапазона
  .Select(n → Divizors(n)) // получи (Select) из n все его делители
  .Where(L → L.Count = 4)  // оставь те, у кого 4 делителя
  .Foreach(L → Println(L[1], L[2])) // для тех, что остались, выведи первые 2

Статград вариант ИН2010103

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.

Ответ: 1225043; 1295029; 1442897

Способ 1 (без school)

##
  var (a, b) := (123489567, 223456789);
  var ans := new List<integer>;  //список наибольших нетривиальных делителей
  for var n := a to b do
    if trunc(sqrt(n))=sqrt(n) then
      begin
        var lstDel := new List <integer>; //список нетривиальных делителей N
        var lim := round(sqrt(N));
        for var d := 2 to lim do 
          begin
            if n.Divs(d)
            then if d = sqrt(N)
                 then lstDel.add(d)
                 else begin
                        lstDel.Add(d);
                        lstDel.Add(N div d)
                      end;
            if lstDel.Count > 3 then break;
          end;
        if lstDel.Count = 3 
        then begin
               lstDel.Sort;
               ans.Add(lstDel.Last);
             end;
      end;
  ans.Sort;
  ans.Println;

Способ 2 (используя модуль school)

##
uses school;
    var a := 123489567;
    var b := 223456789;
    var ans := new List<integer>; 
    for var n := a to b do
      if trunc(sqrt(n)) = sqrt(n) then
      begin
        var s := Divisors(n).RemoveLast;
        if s.Count - 1 = 3  then ans.Add(s.last)
      end;
    ans.Sort;
    ans.Println;

Способ 3 (используя модуль school и лямбда-выражения)

##
uses school;
    (123489567..223456789)
    .Where(x → trunc(sqrt(x))=sqrt(x))
    .Select(x → divisors(x))
    .Where(L → L.count = 5)
    .foreach(L → print(L[3]));

Статград вариант ИН2010201

Рассмотрим произвольное натуральное число, представим его всеми возможными способами в виде произведения двух натуральных чисел и найдём для каждого такого произведения разность сомножителей. Например, для числа 16 получим: 16=16∗1=8∗2=4∗416=16∗1=8∗2=4∗4, множество разностей содержит числа 15, 6 и 0. Найдите все натуральные числа, принадлежащие отрезку [1000000;2000000], у которых составленное описанным способом множество разностей будет содержать не меньше трёх элементов, не превышающих 100. В ответе перечислите найденные числа в порядке возрастания.

Ответ: 1113840; 1179360; 1208844; 1499400

Способ (без school)

##
  var a := 1000000;
  var b := 2000000;
  for var n := a to b do 
  begin
    var count := n - 1 <= 100? 1 : 0;
    var lim := trunc(sqrt(n));
    for var d := 2 to lim do 
    begin
      if n mod d = 0
      then if abs(n div d - d) <=100
           then count += 1
    end;
    if count >= 3 then 
      println(n);
  end;

Способ 2 (используя модуль school)

##
uses school;
  var a := 1000000;
  var b := 2000000;
  for var n := a to b do 
  begin
    var s := Divisors(n);
    var lst := new List<integer>;
    for var i := s.Count - 1 downto (s.count div 2) do 
      lst.add(s[i] - s[s.Count - i - 1]);
    if lst.Count(x → x <= 100) >= 3 then 
      println(n);
  end;

Статград вариант ИН2010301 (Решу ЕГЭ № 33527)

Найдите все натуральные числа, принадлежащие отрезку [101000000;102000000], у которых ровно три различных чётных делителя. В ответе перечислите найденные числа в порядке возрастания.

Ответ: 101075762; 101417282; 101588258; 101645282

Способ (без school)

##
var (a, b) := (101000000, 102000000);
var n := a;
while n <= b do 
  begin
    var keven := 1;  //само число уже чётно и оно делитель себя 
    var lim := trunc(sqrt(n));
    for var d := 2 to lim  do 
      begin
        if n mod d = 0 
        then begin
               if d mod 2 = 0 then keven+=1;
               if (d <> lim) //если d=lim, то будет чётное число чётных делителей
               then if (n div d) mod 2 = 0 then keven += 1;
             end;
        if keven > 3 then break;
      end;
    if keven = 3 then println(n);
    n += 2;  //перебираем только чётные
  end;

Способ 2 (используя модуль school)

##
uses school;
    (101000000..102000000)
    .Where(n → Divisors(n).Count(x → x.IsEven)=3)
    .Println;

P.S. Если Вы заметили ошибку, буду благодарна за комментарии.

Источник

Подготовка к ЕГЭ. Разбор заданий № 17 «Проверка делимости чисел.» (раздел Программирование).

Автор: Окунева Надежда Евгеньевна

Проверяемые элементы содержания: Умение составить алгоритм обработки числовой последовательности и записать его в виде простой программы (10– 15 строк) на языке программирования

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

→ скачать материал

Что нужно знать:

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

Ветвление – (условный оператор) — оператор, конструкция языка программирования, обеспечивающая выполнение определённой команды (набора команд) только при условии истинности некоторого логического выражения, либо выполнение одной из нескольких команд (наборов команд) в зависимости от значения некоторого выражения.

Алгоритм решения:

1. Определить начальные значения входных переменных: k, m, где k – искомое количество чисел из заданного диапазона [a, b], удовлетворяющих заданному условию; k = 0 m – minimax, т.е. если осуществляется поиск минимального значения, то m < a, иначе, при поиске максимального значения m > b.

2. Организовать внешний цикл for, где i изменяется в диапазоне от a до b.

3. Организовать каскад вложенных ветвлений if для осуществления проверки заданных условий:
a. проверка делимости (возможны логические операции or и and);
b. проверка неделимости (применяется логическая операция and);
c. проверка minimaxа.

Примеры заданий:

Вариант № 1

Рассматривается множество целых чисел, принадлежащих числовому отрезку [800; 5900], которые делятся на 17 и не делятся на 2, 3, 5. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число.

Вариант № 2

Рассматривается множество целых чисел, принадлежащих числовому отрезку [4197; 9182], которые делятся на 5 и не делятся на 6, 10, 13, 16. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число.

Связанные страницы:

Источник