Отправлено: 23.12.22 22:17. Заголовок: задание 16 номер 120

Здравствуйте. Вот условие задания:
F(0) = 5
F(n) = 1 + F(n / 2), если n > 0 и n чётное,
F(n) = F(n // 2) в остальных случаях.
Определите количество значений n на отрезке [1, 1 000 000 000], для которых F(n) = 7

При проходе целого заданного отрезка от 1 до 1000000000 программа висит даже с модулем functools и директорией lru_cache. Пробовала разбить этот интервал на части. До 100 000 000 работает, а на интервале от 100 000 001 до 1 000 000 001 зависает и ответ не выводит.
Помогите, пожалуйста, оптимизировать программу. Вот мой код:

from functools import lru_cache

@lru_cache(None)
def f( n ):
if n==0:
return 5
if n>0:
if n%2==0:
return 1+f(n/2)
else:
return f(n//2)
k=0
for n in range (100000001, 1000000001):
if f(n)==7:
k+=1
print (k)

пробовала решать и массивом, но тоже не выводится ответ.

 Отправлено: 25.12.22 07:58. Заголовок: Если напишите решени..

Если напишите решение через массив на C-подобном языке, то точно ответ выведется.

Также, это можно даже калькулятором посчитать, нужно просто первые несколько значений функции на листочек выписать и увидеть решение.

 Отправлено: 29.12.22 12:47. Заголовок: Похожая задача, толь..

Похожая задача,
F(0) = 1
F(n) = 1 + F(n – 1), если n > 0 и n нечётное,
F(n) = F(n / 2) в остальных случаях.
только ищем F(n) =5. Сделана без рекурсии, массивом. Ответ за разумное время тоже не приходит.
def F(n):
a = [1]
for i in range(1,n+1):
if i % 2 !=0 : a.append(1+a[i-1])
else: a.append(a[i//2])
return(a[n])

cnt = 0
for n in range(500000001):
if F(n) == 5: cnt +=1
print(cnt)

Попробовала по предыдущему совету на листочке посчитать первые значения - зависимость не вижу. Подскажите, какая она, пожалуйста!

 Отправлено: 29.12.22 22:27. Заголовок: Нашла на сайт вот та..

Нашла на сайт вот такое решение Константина Юрьевича. У меня оно только и выводит .

m=[0]*1000000000
k=0
m[0]=5
for n in range (1, 1000000000):
if n%2==0:
m[n]=1+m[n//2]
else:
m[n]=m[n//2]
if m[n]==7:
k+=1
print (k)

 Отправлено: 05.01.23 15:58. Заголовок: Агаркова пишет: Наш..

Агаркова пишет:

цитата:

Нашла на сайт вот такое решение Константина Юрьевича

А у меня после запуска этого кода появляется следующая запись:

Traceback (most recent call last):
File "C:\Users\Aleks\Desktop\111.py", line 1, in <module>
m=[0]*1000000000
MemoryError

 Отправлено: 05.01.23 16:00. Заголовок: Для проверки кода ум..

Для проверки кода уменьшил значения массива до ста:

 
 m=[0]*100 
 k=0 
 m[0]=5 
 for n in range (1, 100): 
     if n%2==0: 
         m[n]=1+m[n//2] 
     else: 
         m[n]=m[n//2] 
     print('  ',n,bin(n),m[n])     
     if m[n]==7: 
         print(n,m[n]) 
         k+=1 
 print (k) 
 

анализируя распечатку, приходим к выводу, что программа считает все двоичные числа содержащие два нуля!
Отсюда напрашивается вывод, что код может быть и таким:

 
 k = 0 
 for n in range (1000000000): 
    s = bin(n)[2:] 
    if s.count('0') == 2: 
       k += 1 
 print(k)