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

№16. Рекурсивные алгоритмы

234) *(О. Лысенков) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:

F(n) = (n + 1) ∙ n, если | n | < 5;
F(n) = F(n – 5) + 2∙n + 2356, если | n | ≥ 5 и n кратно 5;
F(n) = F(n + 5) + 7∙n, если | n | ≥ 5 и n не кратно 5.

Определите количество таких целых n, для которых значение F(n) определено и | F(n) | < 132567821562.

Решение
import timeit
from functools import *


@lru_cache
def f(n):
    if -5 < n < 5:
        return (n + 1) * n
    elif n % 5 == 0:
        if n >= 5:
            return f(n - 5) + 2 * n + 2356
        else:
            return float('inf')
    else:
        if n >= 5:
            return float('inf')
        else:
            return f(n + 5) + 7 * n


LIMIT = 132567821562
t0 = timeit.default_timer()
k = 0
for i in range(1, 10 ** 6):
    if abs(f(i)) < LIMIT:
        k += 1

for i in range(0, -10 ** 6, -1):
    if abs(f(i)) < LIMIT:
        k += 1

print(k, timeit.default_timer() - t0)

236) (Досрочный ЕГЭ-2025) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 1 при n ≤ 5;
F(n) = n + F(n – 2), если n > 5.

Вычислите значение выражения F(2126) – F(2122).

Решение
import sys
sys.setrecursionlimit(2000)


def f(n):
    if n <= 5:
        return 1
    if n > 5:
        return n + f(n - 2)


print(f(2126) - f(2122))

237) (Открытый вариант-2025) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 1 при n ≥ 2025;
F(n) = 2n + F(n + 2), если n < 2025.

Вычислите значение выражения F(82) – F(81).

Решение
import sys
sys.setrecursionlimit(2000)


def f(n):
    if n >= 2025:
        return n
    if n < 2025:
        return 2 * n + f(n + 2)


print(f(82) - f(81))

238) (ЕГКР-2025) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = n при n < 20;
F(n) = (n – 6) ∙ F(n – 7), если n ≥ 20.

Вычислите значение выражения (F(47872) – 290 ∙ F(47865)) / F(47858).

Решение
import sys
sys.setrecursionlimit(7000)


def f(n):
    if n < 20:
        return n
    if n >= 20:
        return (n - 6) * f(n - 7)


print((f(47872) - 290 * f(47865)) / f(47858))

239) (Апробация-2025) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 3 при n < 3;
F(n) = 2n + 6 + F(n – 2), если n ≥ 3.

Вычислите значение выражения F(3027) – F(3023).

Решение
import sys
sys.setrecursionlimit(2000)


def f(n):
    if n < 3:
        return 3
    if n >= 3:
        return 2 * n + 6 + f(n - 2)


print(f(3027) - f(3023))

240) * (В. Лашин) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = G(n – 50000) + G(n + 50000);
G(n) = 5ⁿ, если n ≤ 6;
G(n) = G(n – 3) + 2, если n > 6.

Вычислите значение F(100000).

Решение
from functools import *


@lru_cache(None)
def g(n):
    if n <= 6:
        return 5 ** n
    else:
        return g(n - 3) + 2


@lru_cache(None)
def f(n):
    return g(n - 50000) + g(n + 50000)


for n in range(100000):
    g(n)
for n in range(100000):
    f(n)

print(f(100000))