0У
Все задачи №16
№16

Три функции

Алгоритм вычисления функций Q(n), G(n) и H(n) задан соотношениями: Q(n) = 1, если n ≥ 3000; Q(n) = Q(n + 1) + 2, если n < 3000; G(n) = n, если n ≤ 3; G(n) = G(n − 1) + (остаток от деления Q(2 · n) на 5), если n > 3; H(n) = 1, если n ≤ 2; H(n) = H(n − 1) + G(n) − (остаток от деления Q(n) на 3), если n > 2. Чему равно значение H(2000)?

Учебная задача

Ответвпиши то, что вывела программа
Показать разбор
  1. Перепиши три функции из условия и поставь на каждую @lru_cache(None).
  2. Определи порядок прогрева: сначала та функция, на которую опираются остальные. Здесь это Q, потом G, потом H.
  3. Q смотрит вверх, поэтому греем её по убыванию, от 3000 до 1.
  4. G и H смотрят вниз, поэтому греем их по возрастанию, от 1 до 2000.
  5. Напечатай H(2000).
from functools import lru_cache

@lru_cache(None)
def Q(n):
    if n >= 3000:
        return 1
    return Q(n + 1) + 2

@lru_cache(None)
def G(n):
    if n <= 3:
        return n
    return G(n - 1) + Q(2 * n) % 5

@lru_cache(None)
def H(n):
    if n <= 2:
        return 1
    return H(n - 1) + G(n) - Q(n) % 3

for n in range(3000, 0, -1):
    Q(n)
for n in range(1, 2001):
    G(n)
for n in range(1, 2001):
    H(n)
print(H(2000))