Форум » Рекурсивные процедуры и функции » Задача из СтатГрад » Ответить

Задача из СтатГрад

olennval: Видимо планируют в этом году запустить: Алгоритм вычисления значения функции 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 (миллиард ё-моё!!!) Формирование количества, в разных диапазонах не поддаётся логике

Ответов - 16, стр: 1 2 All

Поляков: Можно делать: 1) через динамическое программирование 2) через свой словарь, в котором хранятся уже вычисленные значения функции 3) если лень, то так[pre2] 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)[/pre2]

olennval: Помогут ли тут словари? Для ленивых попробовал. Для @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

Поляков: olennval пишет: Для @lru_cache, видимо, требуется сохранять количество вызовов @lru_cache(maxsize=None), иначе не работает. Странно, я прогнал программу в Python 3.10 под Win, ответ получил через несколько секунд, ошибок не было.


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

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

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

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

IIPPK: Добрый день! Решила № 16 вариант 2( 08.02.22 ) так: [pre2] 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) [/pre2] [pre2] Вариант № 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) [/pre2]

Поляков: Если "в лоб", то вот это считает примерно 5 минут: [pre2] 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)[/pre2]

школьник: аналог 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)

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

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

Поляков: школьник пишет: числовую закономерность находить - уходит много времени. есть ли другие варианты? Посмотрите замечание oval и решение IIPPK, основанное на этой идее. Оно лучшее.

Skeleton: 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)

nuriatalgatovna: Алгоритм вычисления значения функции 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

Поляков: nuriatalgatovna пишет: Написали программу по перестановке 3-х единиц, почему у нас правильный ответ выводит не сумму всех, а только в позиции 29? Множество чисел с двоичной записью длиной k с тремя единицами включает в себя все числа с двоичной записью длиной от 1 до k-1. А правильный ответ в последней строке случайно получился. :-) Вот хорошее решение: [pre2] 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) [/pre2]



полная версия страницы