Отправлено: 07.11.22 19:41. Заголовок: Задача с сайта Компегэ №3034

Программа работает очень долго. Как можно ее оптимизировать?
Задача
Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:

F(0) = 6
F(n) = 1 + F(n / 2) если n > 0 и n чётное
F(n) = F(n // 2) в остальных случаях

Здесь // означает деление нацело. Определите количество значений n на отрезке [1, 1 000 000 000], для которых F(n) = 9.

Моя программа
https://i.postimg.cc/Hkwbh6Hf/3034.png

def f(n):
if n==0:
return 6
if n>0 and n%2==0:
return 1+f(n//2)
if n>0 and n%2!=0:
return f(n//2)
k=0
for n in range(1,1000):
if f(n)==9:
print(n,f(n))
k=k+1
print(k)

 Отправлено: 26.01.23 14:42. Заголовок: Подумайте на такую т..

Подумайте на такую тему: "Результат функции равен 6 + количество нулей в двоичной записи числа".