问题：
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)
我有两种方法,第一种是使用通过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,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
对此有何解释？堆栈溢出某种？但是,它不会抛出任何异常.有没有办法克服这个递归调用？
最佳答案
这里的问题是浮点运算的局限性以及python2和python3之间关于除法运算符的区别.
原文链接：https://www.f2er.com/python/438659.html在python 2中,如果参数是int或long(如本例所示),则除法运算符返回除法结果的最低值,如果参数是浮点数或复数则返回合理的近似值.另一方面,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))