Отправлено: 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 (миллиард ё-моё!!!) Формирование количества, в разных диапазонах не поддаётся логике

 Отправлено: 14.02.22 15:03. Заголовок: Можно делать: 1) чер..

Можно делать:
1) через динамическое программирование
2) через свой словарь, в котором хранятся уже вычисленные значения функции
3) если лень, то так

 from functools import lru_cache 
 @lru_cache 
 def F(n): 
   if n == 0: return 0 
   if n % 2 == 1: return F(n - 1) + 1 
   return F(n/2) 
 k = 0 
 for n in range(1,10000000): 
   if F(n) == 2: 
     k +=1 
     #print(n, F(n)) 
   n +=1 
 print(k)

 Отправлено: 14.02.22 16:44. Заголовок: Помогут ли тут слова..

Помогут ли тут словари?

Для ленивых попробовал.
Для @lru_cache, видимо, требуется сохранять количество вызовов @lru_cache(maxsize=None), иначе не работает.
Для 10 000 000 работает (20 сек обработки), но нужен миллиард.
При таком большом значении возникает ошибка:

Traceback (most recent call last):
File "C:\Users\panda\AppData\Local\Programs\Python\Python36-32\1.py", line 10, in <module>
if F(n) == 2:
MemoryError

 Отправлено: 14.02.22 16:57. Заголовок: olennval пишет: Для ..

olennval пишет:

цитата:

Для @lru_cache, видимо, требуется сохранять количество вызовов @lru_cache(maxsize=None), иначе не работает.

Странно, я прогнал программу в Python 3.10 под Win, ответ получил через несколько секунд, ошибок не было.

 Отправлено: 14.02.22 17:01. Заголовок: Потому что Вы написа..

Потому что Вы написали для 10 миллионов, а нужен 1 млрд, на 30 млн уже ошибка

 Отправлено: 14.02.22 17:07. Заголовок: А если подумать :sm3..

А если подумать
Функция возвращает "+ 1" для нечетных и переходит к n-1, т.е. в двоичной записи меняем последнюю 1 на 0.
Для четных делим на 2, откидываем последний 0.
Итого функция возвращает количество 1 в двоичной записи числа.
для миллиарда в двоичной сс надо 30 разрядов.
ответ: С₃₀³, если будет большее кол-во 1, не забыть проверить, что не вылезаем за границу

 Отправлено: 14.02.22 18:49. Заголовок: oval пишет: Функция ..

oval пишет:

цитата:

Функция возвращает "+ 1" для нечетных и переходит к n-1, т.е. в двоичной записи меняем последнюю 1 на 0. Для четных делим на 2, откидываем последний 0. Итого функция возвращает количество 1 в двоичной записи числа.

 Отправлено: 14.02.22 18:22. Заголовок: Поставил maxsize=128..

Поставил maxsize=128, и всё получилось. Правда, ждать пришлось минут 40 - 50
Спасибо, Константин Юрьевич.
oval'у отдельный респект

 Отправлено: 15.02.22 21:07. Заголовок: Добрый день! Решила ..

Добрый день!
Решила № 16 вариант 2( 08.02.22 ) так:

 
 d = 0 
 for n in range(2, 100): 
     for k in range(1, n): 
         for m in range(0, k): 
             if ((2**n + 2**k + 2**m) < 1000000000): 
                 d += 1 
 print(d) 
 

 
 Вариант № 1 
  
 count = 0 
 for n in range (1, 100): 
     for k in range (0, 100): 
         if (2**n + 1)*(2**k) < 1000000000: 
             count += 1 
 print(count) 
 

 Отправлено: 15.02.22 21:20. Заголовок: Если "в лоб"..

Если "в лоб", то вот это считает примерно 5 минут:

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

 Отправлено: 10.03.22 20:00. Заголовок: аналог 317 Ряд 3, 5,..

аналог 317
Ряд 3, 5, 9, 17, 33, … (i*2-1) – каждый элемент удваивается до верхней границы
i=2
s=0
ma=500000000
while i<ma:
i=i*2-1
k=i
while k<ma:
k=k*2
s=s+1
print(s)

 Отправлено: 10.03.22 20:59. Заголовок: mem = *1000000000 ..

mem = [0]*1000000000
выдает переполнение

 Отправлено: 10.03.22 21:01. Заголовок: числовую закономерно..

числовую закономерность находить - уходит много времени. есть ли другие варианты?

 Отправлено: 10.03.22 21:16. Заголовок: школьник пишет: числ..

школьник пишет:

цитата:

числовую закономерность находить - уходит много времени. есть ли другие варианты?

Посмотрите замечание oval и решение IIPPK, основанное на этой идее. Оно лучшее.

 Отправлено: 28.03.22 17:18. Заголовок: c = 0 for i in range..

c = 0
for i in range (0,31):
for j in range (i+ 1, 31):
x = 2**i + 2**j
if x < 10**9:
c += 1
print(c)

 Отправлено: 17.05.23 22:18. Заголовок: 4965

Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(0) = 1
F(n) = 1 + F(n - 1), если n > 0 и n нечётное
F(n) = F(n / 2) в остальных случаях
Определите количество значений n на отрезке [1, 500 000 000], для которых F(n) = 4.

Определили, что 4 ка выходит, если в двоичном коде числа 3 единицы.
Максимальная длина - 29.

from math import *
p = 0
for k in range(3,29+1):
p+=factorial(k)/(factorial(3)*factorial(k-3))
print(p)

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

3 1.0
4 4.0
5 10.0
6 20.0
7 35.0
8 56.0
9 84.0
10 120.0
11 165.0
12 220.0
13 286.0
14 364.0
15 455.0
16 560.0
17 680.0
18 816.0
19 969.0
20 1140.0
21 1330.0
22 1540.0
23 1771.0
24 2024.0
25 2300.0
26 2600.0
27 2925.0
28 3276.0
29 3654.0
27405.0

 Отправлено: 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)