0

我编写了代码来计算 Ackermann 函数并存储结果，但在某个随机点它会停止（尽管仅适用于查找版本），正常版本只是运行而不会停止。

不可能是递归限制，可能是字典太大了？不过，它并没有使用太多内存。

这是代码：

import time, sys
sys.setrecursionlimit(100000)

lookup = {}
def ackermann(m,n,look):

    if (m,n) in lookup and look: #Checks if the pair is in the table
        print("pair found")
        return lookup[(m,n)]

    else: #Regular ackermann
        if m == 0:
            print("Base found for {} {}".format(m,n))
            return n+1

        if n == 0:
            print("Case 2: {} {}".format(m,n))
            result = ackermann(m-1,1,look)
            if look:
                lookup[m,n] = result
            return result

        else:
            print("Case 3: {} {}".format(m,n))
            result = ackermann(m-1,ackermann(m,n-1,look),look)
            if look:
                lookup[m,n] = result
            return result




def call_ack(m,n):
    t1= time.time()
    result1 = ackermann(m,n,True)    
    t2= time.time()
    result2 = ackermann(m,n,False)
    t3= time.time()
    print("Result with lookup:",result1, "\nElapsed time:",t2-t1)
    print("\nResult without lookup:",result2, "\nElapsed time:",t3- t2)
    print("Difference: ", t3+t1-t2*2)

这是其中一个输出的最后一部分：

Case 3: 1 7947
Case 3: 1 7946
pair found
Base found for 0 7947
Base found for 0 7948
Case 3: 1 7949
Case 3: 1 7948

如果我再次运行它：

Case 3: 2 4695
Case 3: 2 4694
Case 3: 2 4693
Case 3: 2 4692
Case 3: 2 4691
Case 3: 2 4690
Case 3: 2 4689
Case 3: 2 4688
Case 3: 2 4687
Case 3: 2 4686
Case 3: 2 4685
Case 3: 2 4684
Case 3: 2 4683
Case 3: 2 4682
Case 3: 2 4681
Case 3: 2 4680
Case 3: 2 4679

无需改变任何东西。哦，男孩，我喜欢不一致的结果！值得注意的是，对于较小的值，它运行得非常完美。

编辑：我刚刚尝试过这个在线python解释器，它工作得很好。

编辑2：我试过用另一个版本的python（3.8.2而不是3.7）运行它，它以堆栈溢出错误关闭。问题是它几乎没有使用内存 - 根据任务管理器最多 6.6 MB。

4

0 回答 0