2016年8月29日

二分查找法求某数的任意次方根

以下代码出自 MOOC 《计算机科学和 Python 编程导论》第四讲。

这段代码比较简单,但至少有以下值得注意和学习的地方:

  • 二分查找法的使用
  • 测试用例覆盖所有情况(在这里是:正数、负数、绝对值大于 1、绝对值小于 1)
  • 对 low 和 high 赋值的方式,比较巧妙
  • 为每个功能函数添加说明文档(即使工作多年的职业程序员,也不一定做到)
def findRoot(x, power, epsilon):
    """x and epsilon int or float, power an int
         epsilon > 0 & power >= 1
       returns a float y s.t. y**power is within epsilon of x.
       if such a float does not exist, it returns None"""
    if x < 0 and power % 2 == 0:
        return None
    # can't find even powered root of negative number
    low = min(-1, x)
    high = max(1, x)
    ans = (high + low) / 2.0
    while abs(ans**power - x) > epsilon:
        if ans**power < x:
            low = ans
        else:
            high = ans
        ans = (high + low) / 2.0
    return ans

if __name__ == "__main__":
    print findRoot(0.25, 3, .001)
    print findRoot(-0.25, 3, .001)
    print findRoot(25, 2, .001)
    print findRoot(-27, 3, .001)

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注


*