Форум » Рекурсивные процедуры и функции » Задача из СтатГрад » Ответить
Задача из СтатГрад
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
Поляков: 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]
полная версия страницы