破記憶代碼

我有一系列數字，我需要找到的總和。第一次迭代操作的值爲1，第二次爲20.隨後的每次迭代使用公式n *（n + 1）/ 2中的先前結果，因此第三次迭代，例如i03 = 20 *（20+ 1）/ 2，第四個，i04 = i03 *（i03 + 1）/ 2。這一直持續到i20 = i19 *（i19 + 1）/ 2的第20次迭代。我想使用memoization來做到這一點。這是我的代碼：破記憶代碼

def outFun(): 
    def sumFun(squares, total = 0, CONST = 20): 
     if squares > 2: 
      total = sumFun(squares - 1) * int((sumFun(squares - 1) + 1)/2) 
     elif not squares - 2: 
      total = CONST 
     return total 

    return 1 + sumFun(20)

我在做什麼錯？

來源

2013-02-20 Jack J

您有很多遞歸，但沒有記憶。也就是說，在返回它之前需要指定'_cache [inargs] = result'的地方，然後在調用時測試'if inargs in _cache：return cachedval'。 – 2013-02-20 20:04:42

這是我如何理解您的問題：你有一個公式x_n = x_{n-1} * (x_{n-1} + 1)/2定義爲x_1 = 20（或x_2 = 20從你的描述看不清？）遞歸基地。解決遞歸最有效的方法是自下而上的方法，當你開始x_1，然後計算x_2等替代方案是使用動態編程/記憶：

mem={} 
def f(x): 
    if x == 1: # base case 
     return 20 
    if not x in mem: # if we did not calculate it before - calculate 
     mem[x] = f(x-1) * (f(x-1) +1)/2 
    return mem[x] # otherwise return it 

print f(1)  
print f(2) 
print f(3)

打印

20 
210 
22155

f(20)是有點大的打印，所以我將打印的位數它：

print "number of digits: %s" % len(str(f(20))) 

number of digits: 530115

代碼歷時約9秒在我的桌面上運行：

import timeit 
mem={} 
print "Execution time: %s" % timeit.Timer("len(str(f(20)))", 
          setup = "from __main__ import f").timeit(1)

來源

2013-02-21 02:50:27

你打電話

sumFun(squares - 1)

兩次！

爲什麼不引入一個變量來存儲結果？喜歡的東西：

if squares > 2: 
    nextResult = sumFun(squares - 1) 
    total = nextResult * ((nextResult + 1)/2)

來源

2013-02-20 20:03:41

回答

相關問題