Алгоритм вычисления значения функции , где – целое неотрицательное число, задан следующими соотношениями: Сколько существует чисел , меньших 1000, для которых значение будет равно 0?

Задание 16 № 15721: Вычисление значения рекурсивной функции — ЕГЭ по информатике

Алгоритм вычисления значения функции $F(n)$ , где $n$ – целое неотрицательное число, задан следующими соотношениями: $F(n) = 0 \text{ при } n = 0$ $F(n) = F(n/2) - 1 \text{ при чётных } n > 0$ $F(n) = 1 + F(n - 1) \text{ при нечётных } n > 0$ Сколько существует чисел $n$ , меньших 1000, для которых значение $F(n)$ будет равно 0?

Решение:

Решение на Python:

from functools import lru_cache
@lru_cache (None)
def f(n):
    if n == 0: return n
    if n > 0 and n % 2 == 0: return f(n/2) - 1
    if n > 0 and n % 2 != 0: return 1 + f(n-1)
for n in range(4000): f(n)
k = 0
for n in range(1000):
    if f(n) == 0: k+=1
print(k)

Ответ: 41

Ответ: