概述
问题：
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
对此有何解释？堆栈溢出某种？但是,它不会抛出任何异常.有没有办法克服这个递归调用？
在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))
总结
以上是编程之家为你收集整理的Python：当网格大小太大时,递归调用计数行走网格的方式会产生错误的答案全部内容，希望文章能够帮你解决Python：当网格大小太大时,递归调用计数行走网格的方式会产生错误的答案所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧
602392714
清零编程群