Отправлено: 14.02.22 13:12. Заголовок: Задача из СтатГрад

Видимо планируют в этом году запустить:
Алгоритм вычисления значения функции 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 == 0: return 0
if n % 2 == 1: return F(n - 1) + 1
if n > 0 and n % 2 == 0: return F(n/2)
n = 1
k = 0
while n < 10 000 000:
if F(n) == 2:
k +=1
#print(n, F(n))
n +=1
print(k)
Примерно через час выдало 274. Но нужен 1 000 000 000 (миллиард ё-моё!!!) Формирование количества, в разных диапазонах не поддаётся логике

 Отправлено: 04.06.23 11:38. Заголовок: nuriatalgatovna пише..

nuriatalgatovna пишет:

цитата:

Написали программу по перестановке 3-х единиц, почему у нас правильный ответ выводит не сумму всех, а только в позиции 29?

Множество чисел с двоичной записью длиной k с тремя единицами включает в себя все числа с двоичной записью длиной от 1 до k-1. А правильный ответ в последней строке случайно получился. :-) Вот хорошее решение:

 from math import log2 
  
 MAX = 500_000_000 
 L = int(log2(MAX)) + 1 
 count = 0 
 for n in range (0, L+1): 
   for k in range (n+1, L+1): 
     for m in range (k+1, L+1): 
       if 2**n + 2**k + 2**m < MAX: 
         count += 1 
 print(count)