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

Сколько n с F(n) = 10

Алгоритм вычисления функции F(n) задан соотношениями: F(0) = 0; F(n) = F(n / 3) + 1, если n > 0 и n делится на 3; F(n) = F(n − 1) + 2 во всех остальных случаях. Сколько существует натуральных n от 1 до 1000 включительно, для которых F(n) = 10?

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

Ответвпиши то, что вывела программа
Показать разбор
  1. Перепиши функцию из условия. Деление пиши как n // 3: число и так делится нацело, а результат останется целым.
  2. Поставь @lru_cache(None), чтобы не считать одно и то же много раз.
  3. Прогрей функцию циклом от 1 до 1000.
  4. Заведи счётчик и пройди по всем n от 1 до 1000: если F(n) == 10, прибавь единицу.
  5. Напечатай счётчик.
from functools import lru_cache

@lru_cache(None)
def F(n):
    if n == 0:
        return 0
    if n > 0 and n % 3 == 0:
        return F(n // 3) + 1
    return F(n - 1) + 2

for n in range(1, 1001):
    F(n)
a = 0
for n in range(1, 1001):
    if F(n) == 10:
        a += 1
print(a)