残缺的记忆密码

Question

我有一系列的数字需要求和。第一次迭代运算的值是1，第二次迭代运算的值是20。接下来的每次迭代都使用公式n*（n+1）/2中的前一个结果，因此第三次迭代，即i03=20*（20+1）/2，第四次迭代，即i04=i03*（i03+1）/2。这一直持续到i20=i19*（i19+1）/2的第20次迭代。我想用回忆录来做这件事。这是我的密码：

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)

我做错什么了？你知道吗

Answer 1

你在打电话吗

sumFun(squares - 1)

两次！你知道吗

为什么不引入一个变量来存储结果呢？比如：

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

Answer 2

我是这样理解你的问题的：你有一个公式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)