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

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

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

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

Чему равно значение (F(2025) – 2·F(2023)) / F(2021)?

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


def f(n):
    if n < 3:
        return 1
    else:
        return (n - 1) * f(n - 2)


print((f(2025) - 2 * f(2023)) // f(2021))

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

F(n) = F(n / 2) + 3, если n чётное;
F(n) = F(n / 3) + 2, если n нечётное и делится на 3;
F(n) = 0, если n нечётное и не делится на 3.

Определите минимальное значение n, для которого F(n) = 65.

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


def f(n):
    if n % 2 == 0:
        return f(n // 2) + 3
    elif n % 2 != 0 and n % 3 == 0:
        return f(n // 3) + 2
    else:
        return 0


for i in range(1000000, 10000000):
    if f(i) == 65:
        print(i, f(i))
        break

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

F(n) = F(n / 2) + 5, если n чётное;
F(n) = F(n / 5) + 2, если n нечётное и делится на 5;
F(n) = 0, если n нечётное и не делится на 5.

Сколько различных значений принимает функция F(n) на отрезке [1; 1000000]?

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


def f(n):
    if n % 2 == 0:
        return f(n // 2) + 5
    elif n % 2 != 0 and n % 5 == 0:
        return f(n // 5) + 2
    else:
        return 0


mas = []
for i in range(1, 1000001):
    mas.append(f(i))
print(len(set(mas)))