Спасите не понимаю потиму большое число

Question

Спасите не понимаю потиму большое число

*-* Ученик (117), открыт 1 день назад

Def f(x, y):
if x > y or x == 12:
return 0 if x == y:
return 1 else:
return f(x + 1, y) + f(x + 2, y) + f(x * 3, y)
print(f(3, 40))

Answer 1

Код:

 def f(x, y, memo={}): 
    # Проверка наличия результата в словаре мемоизации 
    if (x, y) in memo: 
        return memo[(x, y)] 
     
    # Базовые условия 
    if x > y: 
        result = 0 
    elif x == y: 
        result = 1 
    else: 
        # Рекурсивные вызовы с мемоизацией 
        result = f(x + 1, y, memo) + f(x + 2, y, memo) + f(x * 3, y, memo) 
     
    # Сохранение результата в словаре мемоизации 
    memo[(x, y)] = result 
    return result 
 
print(f(3, 40))

Answer 2

Ну, в первом приближении ты получишь примерно 3^20, Потому что первое слагаемое растет МЕДЛЕННО, а рекурсия размножается БЫСТРО. Ничего особенно удивительного я тут не вижу, кроме того, что от такой глубокой рекурсии у тебя не выпадает стек или куча.

Answer 3

 f = {40: 1}
for x in range(39, 2, -1):
  if x != 12: f[x] = f.get(x + 1, 0) + f.get(x + 2, 0) + f.get(x * 3, 0)
print(f[3])

Задача решается динамическим программированием БЕЗ рекурсии.

Обобщённый вариант для произвольных x, y:

 def f(x, y):
  t = {y: 1}
  for i in range(y - 1, x - 1, -1):
    if i != 12:
      t[i] = t.get(i + 1, 0) + t.get(i + 2, 0) + t.get(i * 3, 0)
  return t.get(x, 0)