Python:当网格大小太大时,递归调用计数行走网格的方式会产生错误的答案

Question

问题:

想象一下,你从X by Y网格的角落开始.您只能向两个方向移动:向右和向下.从(0,0)到(X,Y)的路径有多少

我有两种方法,第一种是使用通过memoization增强的递归算法,第二种是使用二项式计数策略

递归方式

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

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

在 python 2 中，如果参数是整数或长整型（如本例所示），除法运算符将返回除法结果的下限；如果参数是浮点数或复数，则除法运算符返回合理的近似值。另一方面，Python 3 返回一个合理的除法近似值，与参数类型无关。

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

在 python2.2 中引入了向下除法//运算符，在 python3 中真正的除法取代了经典除法（请参阅此处的术语起源：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))