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

发布时间：2020-12-16 22:46:38 所属栏目：Python 来源：网络整理

导读：问题： 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增强的递归算法,第二

问题：

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之间关于除法运算符的区别.

在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))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!