Форум » Рекурсивные процедуры и функции » Задача 16 - №6565 » Ответить
Задача 16 - №6565
mash: Обозначим частное от деления натурального числа a на натуральное число b как a // b, а остаток как a%b. Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = n // 3 + n % 3, если n < 9; F(n) = F(n // 9) + F(n % 9), если n ≥ 9. Определите количество значений n < 9^9, для которых функция F(n) = 33. При решении количество операций будет слишком огромным, ответа придётся ждать очень долго, и вряд ли ты его вообще дождёшься. Есть ли вообще способ решить эту задачу быстро с помощью кода ? ВОТ РЕШЕНИЕ(НЕРАБОЧЕЕ): def F(n, cache): if n < 9: return n // 3 + n % 3 else: if n not in cache: cache[n] = F(n // 9, cache) + F(n % 9, cache) return cache[n] count = 0 cache = {} for n in range(1, 9**9): if F(n, cache) == 33: count += 1 print(count)
Ответов - 3
Ж: Вообще задача сводится к нахождению чисел, сумма цифр в троичной записи которых равна 33 Вот код, который считает мгновенно. [pre2] k=[0]*34 k[0]=k[1]=k[2]=1 for c in range(17): k=[k[0],k[1]+k[0]]+[sum(k[i - 2:i + 1]) for i in range(2,34)] print(k[-1]) [/pre2] Вот несколько кодов, которые решают задачу обычным способом, но все они считают от 12 до 16 минут [pre2] from time import * setrecursionlimit(2**15) kol=0 @lru_cache(2**20) def F(n): if n < 9: return n // 3 + n % 3 return F(n // 9) + F(n % 9) for c in range(9**9): if F(c)==33: kol+=1 print(kol,c) [/pre2] [pre2] from functools import * kol=0 tr=lru_cache(2**20)(lambda n: tr(n//3)+n%3 if n>0 else 0) for c in range(int('2'*16,3), 9**9): kol+=tr(c)==33 print(kol) [/pre2] [pre2] setrecursionlimit(2**15) f=lru_cache(2**20)(lambda n,s: f(n,s+'0')+f(n+1,s+'1')+f(n+2,s+'2') if n<33 and len(s)<18 else n==33 and int(s,3)<=9**9) print(f(0,'')) [/pre2]
gutgut: Мои соображения следующие. Так как F(9*k0+p0) = F(k0)+F(p0), а p0 можно рассматривать как последнюю цифру числа 9*k0+p0, записанного в девятеричной системе счисления, то применяя тот же подход для F(k0) получим F(9*k0+p0) = F(9*k1+p1) + F(p0) = F(k1) + F(p1) + F(p0) и т. д. Следовательно, итог есть сумма F(p) для каждой цифры в девятеричном представлении числа. Легко получить значение F(p) для каждой цифры. Соберём их в список V=[0,1,2,1,2,3,2,3,4], тогда F(p) = V[p]. Получить сумму 33 можно следующими способами: 1) 8*4 + 1 (отсюда следует, что в исходном числе должно быть 9 цифр, 8 даст максимум 32). Значит в числе должно быть 8 восьмерок и одна цифра 1 или 3 на любом оставшемся месте. Это 18 вариантов. 2) 7*4+3+2. Значит в числе должно быть 7 восьмерок, одна цифра 5 или 7 и одна цифра 2, 4 или 6 на двух оставшихся местах. Комбинируя эти цифры получим 12 пар, а всего C(2,9)*12 = 432 варианта. 3) 6*4+3*3. Значит в числе должно быть 6 восьмерок, остальные три места занимают цифры 5 и 7, они дают 8 вариантов, всего C(3,9)*8 = 672 варианта. Складывая эти значения получим ответ: 1122
gutgut: Мои соображения следующие. Так как F(9*k0+p0) = F(k0)+F(p0), а p0 можно рассматривать как последнюю цифру числа 9*k0+p0, записанного в девятеричной системе счисления, то применяя тот же подход для F(k0) получим F(9*k0+p0) = F(9*k1+p1) + F(p0) = F(k1) + F(p1) + F(p0) и т. д. Следовательно, итог есть сумма F(p) для каждой цифры в девятеричном представлении числа. Легко получить значение F(p) для каждой цифры. Соберём их в список V=[0,1,2,1,2,3,2,3,4], тогда F(p) = V[p]. Получить сумму 33 можно следующими способами: 1) 8*4 + 1 (отсюда следует, что в исходном числе должно быть 9 цифр, 8 даст максимум 32). Значит в числе должно быть 8 восьмерок и одна цифра 1 или 3 на любом оставшемся месте. Это 18 вариантов. 2) 7*4+3+2. Значит в числе должно быть 7 восьмерок, одна цифра 5 или 7 и одна цифра 2, 4 или 6 на двух оставшихся местах. Комбинируя эти цифры получим 12 пар, а всего C(2,9)*12 = 432 варианта. 3) 6*4+3*3. Значит в числе должно быть 6 восьмерок, остальные три места занимают цифры 5 и 7, они дают 8 вариантов, всего C(3,9)*8 = 672 варианта. Складывая эти значения получим ответ: 1122
полная версия страницы