Python: 当网格尺寸太大时，遍历网格的递归调用计数方法会产生不正确的答案

Question

问题：

Imagine you start at the corner of an X by Y grid. You can only move in two directions: right and down. How many possible paths are there for you to go from (0, 0) to (X, Y)

我有两种方法，第一种是使用记忆增强的递归算法，第二种是使用二项式计数策略

递归方式

def gridMovingCount(x, y, cache):
    if x == 0 or y == 0:
        return 1
    elif str(x)+":"+str(y) in cache:
        return cache[str(x)+":"+str(y)]
    else:
        cache[str(x)+":"+str(y)] = gridMovingCount(x-1, y, cache) + gridMovingCount(x, y-1, cache) 
        return cache[str(x)+":"+str(y)]

二项式计数

def gridMovingCountByBinomial(x, y):
    return int(math.factorial(x + y) / (math.factorial(x) * math.factorial(y)))

当x和y相对较小时，这两种方式给出相同的答案

 #the same result
 print(gridMovingCount(20, 20, cache))    #137846528820
 print(gridMovingCountByBinomial(20, 20)) #137846528820

当 x 和 y 较大时

# gave different result
print(gridMovingCount(50, 50, cache))    #100891344545564193334812497256
print(gridMovingCountByBinomial(50, 50)) #100891344545564202071714955264

这是什么解释。某种堆栈溢出？但是，它不会抛出任何异常。递归调用有没有办法克服这个问题？

Answer 1

我暂时被难住了，但我有一些不错的进步。我尝试了一些方法来跟踪这个：

我将您的字典键从字符串更改为元组 (x,y)，只是为了使代码更具可读性。
我在几个地方添加了结果变量，以帮助跟踪返回值。
我添加了几个打印语句。这些跟踪缓存的最后一个角值、函数中计算的结果以及接收到的结果。

新代码如下，输出也是如此。您可以在输出中看到关键问题：函数确实计算出正确的值并将其 returns 传递给调用程序。但是，调用程序收到一个更大的值。这发生在 Python 3.5.2 中，但 2.6.6 计算正确。还有一个符号差异：2.6.6 大值在显示值上有尾随 "L"。

代码：

import math

def gridMovingCount(x, y, cache):
    if x == 0 or y == 0:
        return 1
    elif (x,y)  in cache:
        if x+y > 98:
          print ("returning cached", x, y, result)
        return cache[(x,y)]
    else:
        cache[(x,y)] = gridMovingCount(x-1, y, cache) + gridMovingCount(x, y-1, cache) # stack will overflow
        result = cache[(x,y)]
        if x+y > 98:
          print ("returning binomial", x, y, result)
        return result

def gridMovingCountByBinomial(x, y):
    return int(math.factorial(x + y) / (math.factorial(x) * math.factorial(y)))


cache={}
#the same result
print(gridMovingCount(20, 20, cache))    #137846528820
print(gridMovingCountByBinomial(20, 20)) #137846528820

# gave different result
print()
print("50x50 summed  ", gridMovingCount(50, 50, cache))    #100891344545564193334812497256
with open("p3.4_out", 'w') as fp:
   lout =  sorted(list(cache.items()))
   for line in lout:
      fp.write(str(line) + '\n')

result = gridMovingCountByBinomial(50, 50)
print()
print("50x50 binomial", result) #100891344545564202071714955264
print("50x50 cached  ", cache[(50,50)])

输出：

$ python3 so.py
137846528820
137846528820

returning binomial 49 50 50445672272782096667406248628
returning binomial 50 49 50445672272782096667406248628
returning binomial 50 50 100891344545564193334812497256
50x50 summed   100891344545564193334812497256

50x50 binomial 100891344545564202071714955264
50x50 cached   100891344545564193334812497256

相差8736902458008；在十六进制中，这是 0x7f237f7aa98——也就是说，在 base 2 中没有什么特别有趣的。它不是缓存中任何地方的值。

我知道这不是一个完整的答案，但我希望它能将问题范围缩小到另一个 SO 居民认可的范围。

顺便说一句，我比较了缓存文件；它们是相同的，除了 2.6.6

中每个长整数的尾随 'L'

Answer 2

这里的问题是 浮点运算的限制 以及 python2 和 python3 在 除法方面的差异运算符.

在 python 2 中，除法运算符 returns 如果参数是整数或长整数（如本例），则除法结果的底数；如果参数是浮点数，则为合理的近似值或复杂。 Python 另一方面，3 returns 与参数类型无关的除法的合理近似值。

在数字足够小的情况下，这个近似值足够接近，以至于转换回整数最终得到与 python 2 版本相同的结果。然而，当结果变得足够大时，浮点表示法不足以近似地在转换回 int 时得到正确的结果。

在 python2.2 中引入了 floor division 运算符 // 并且在 python3 true division 替换了 经典分区 （请参阅此处的术语来源：https://www.python.org/dev/peps/pep-0238/）

#python2
from math import factorial
print(int(factorial(23)/2))  # 12926008369442488320000
print(int(factorial(23)//2))  # 12926008369442488320000

#python3
from math import factorial
print(int(factorial(23)/2))  # 12926008369442489106432
print(int(factorial(23)//2))  # 12926008369442488320000

所有这一切的结果是，对于您的二项式函数，您可以删除对 int 的转换并使用显式的底除法运算符来获得返回的正确结果。

def gridMovingCountByBinomial(x, y):
    return math.factorial(x + y) // (math.factorial(x) * math.factorial(y))

Python: 当网格尺寸太大时，遍历网格的递归调用计数方法会产生不正确的答案

Python: Recursive call counting ways of walking grid yield incorrect answer when grid size is too large

python

recursion

counting

python-3.x