0

我有一系列数字，我需要找到它们的总和。第一次迭代操作的值是 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)

我究竟做错了什么？

4

2 回答 2

1

你在打电话

sumFun(squares - 1)

两次！

为什么不引入一个变量来存储结果呢？就像是：

if squares > 2:
    nextResult = sumFun(squares - 1)
    total = nextResult * ((nextResult + 1) / 2)
于 2013-02-20T20:03:41.927 回答
1

我是这样理解您的问题的：您有一个公式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-21T02:50:27.920 回答