Главная / 2 февраля 2026 г.

№15. Преобразование логических выражений

Ограничение рекурсии

В Python рекурсия используется для решения различных задач, таких как обход деревьев, вычисление факториалов и решение задач динамического программирования. Однако у рекурсии есть свои ограничения, и одно из них – это лимит глубины рекурсии. Python по умолчанию устанавливает ограничение на максимальную глубину рекурсии. Это сделано для предотвращения переполнения стека вызовов, что может привести к сбоям программы. Если рекурсивная функция превышает этот лимит, вы получите ошибку

RecursionError: maximum recursion depth exceeded.

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

605) (PRO100-ЕГЭ) Для какого наибольшего целого неотрицательного числа А логическое выражение

(68 160 ≠ 2y + 4x) ∨ (x ∙ y > A) ∨ (x > y)

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

Решение

606) (PRO100-ЕГЭ) Для какого наименьшего целого неотрицательного числа А логическое выражение

(x < 5 ∙ y) ∨ (y ∙ x < A) ∨ (x > 680)

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

Решение

608) (PRO100-ЕГЭ) Для какого наименьшего целого неотрицательного числа А логическое выражение

(250 000 < x) ∨ (y + 2x < A) ∨ (y > 250 000)

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

Решение

610) (PRO100-ЕГЭ) Для какого наибольшего целого неотрицательного числа А логическое выражение

(x > A) ∨ (y > A) ∨ (y < x + 200 000) ∨ (y > 2x – 100 000)

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

Решение

613) * Для какого наименьшего натурального числа А логическое выражение

(2496315 ≠ 4y + 2x) ∨ (A > x) ∧ (A > y)

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

Решение
def expr(x, y, A):
    return (2496315 != 4 * y + 2 * x) or (A > x) and (A > y)


A = 1
while True:
    if all(expr(2496315 - 4 * y, y, A) for y in range(1, 625080)):
        print(A)
        break

621) *Для какого наименьшего натурального числа А логическое выражение

(581625 ≠ 29y + 31x) ∨ (A > 5x) ∧ (A > 4y)

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

Решение

Ответ: 93746

180) (А. Богданов) Обозначим частное от деления натурального числа a на натуральное число b как a // b, а остаток – как a % b. Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = n // 3 + n % 3, если n < 9;
F(n) = F(n // 9) + F(n % 9), если n ≥ 9.

Определите количество значений n < 9⁹, для которых функция F(n) = 33.

Решение
def F(n):
    if n < 9:
        return n // 3 + n % 3
    else:
        return F(n // 9) + F(n % 9)


k = 0
for n in range(9 ** 9 - 2, 20000, -2):
    if F(n) == 33:
        k += 1
        print(n, k)
print(k)

181) (Е. Джобс) Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 1, если n ≥ 10000;
F(n) = F(n + 3) + 7, если n < 10000 и чётное;
F(n) = F(n + 1) – 3, если n < 10000 и нечётное.

Чему равно значение выражения F(50) – F(57)?

Решение
F = [0] * 10011

for n in range(10010, 20, -1):
    if n > 10000:
        F[n] = 1
    elif n < 10000 and n % 2 == 0:
        F[n] = F[n + 3] + 7
    elif n < 10000 and n % 2 != 0:
        F[n] = F[n + 1] - 3

print(F[50] - F[57])