Помогите решить задачу из ЕГЭ по информатике

Question

Помогите решить задачу из ЕГЭ по информатике

Павел Сметанов Ученик (87), на голосовании 1 год назад

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

F(0) = 0;

F(n) = F(n − 1) + 1, если n нечётно;

F(n) = F(n / 2), если n > 0 и при этом n чётно.

Укажите количество таких значений n < 1 000 000 000, для которых F(n)  =  3.

Моё решение:

def F(n):
if n % 2 != 0:
return F(n - 1) + 1
if n == 0:
return 0
if n > 0 and n % 2 != 0:
return F(n / 2)

k = 0
for i in range(3, 31):
k = k + i - 1
print(k)

Что не так с кодом?

Answer 1

Рекурсия будет считать до конца жизни. Лучше использовать динамическое программирование, но и с ним для миллиарда у меня считало минут 5-10

 N = 1000000000 
F = [0] * (N + 1) 
count = 0 
 
for n in range(1, N + 1): 
    if n % 2 == 0: 
        F[n] = F[n // 2] 
    else: 
        F[n] = F[n - 1] + 1 
    if F[n] == 3: 
        count += 1 
 
print(count)
# ответ 4060