Python - 计算 nth 根的线性和二分搜索方法

Question

我写了两个函数来计算一个数字的n次根。一个是用线性搜索的方法，另一个是用二分搜索的方法。可是，当我尝试调用这两个函数时，都出现了问题。系统只是告诉我，我指定的数字无法计算这个根。我感到很困惑，不知道自己哪里出错了。有没有人能帮我想想？

def rootBisect(root, num):
    low = 0.0
    high = num
    ans = (high + low)/2.0
    while ans ** root < abs(float(num)):
        if ans ** root < num:
            low = ans
        else:
            high = ans
        ans = (high + low)/2.0
    if ans ** root != abs(num):
        print '%d cannot be taken to %d root.' % (num, root)
    else:
        if num < 0:
            ans = -ans
        print '%d root of %d is %d.' % (root, num, ans)
    return ans

def rootLinear(root, num):
    ans = 0
    while ans ** root < abs(float(num)):
        ans += 0.1
    if ans ** root != abs(num):
        print '%d cannot be taken to %d root.' % (num, root)
    else:
        if num < 0:
            ans = -ans
        print '%d root of %d is %d.' % (root, num, ans)
    return ans

rootBisect(2, 16)

rootLinear(2, 16)

Answer 1

num1=input("Please enter a number to find the root: ")#accepting input and saving in num1
num2=input("Please enter another number as the root: ")#accepting input and saving in num2
x=float(num1)#converting string to float
n=float(num2)#converting string to float

least=1#the lower limit to find the average
most=x#the lower limit to find the average

approx=(least+most)/2#to find simple mean using search method taught in class

while abs(approx**n-x)>=0.0000000001:#for accuracy

    if approx**n>x:
        most=approx
    else:
        least=approx

    approx=(least+most)/2

print("The approximate root: ",approx)#output

我希望这个代码能更清晰、更简单！

Answer 2

问题在于你期望 ans ** root == abs(num) 这个条件成立。但实际上，这种情况不太可能，因为浮点数运算的精度是有限的。看看这个：

>>> import math
>>> math.sqrt(7)
2.6457513110645907
>>> math.sqrt(7)**2
7.000000000000001
>>> math.sqrt(7)**2 == 7
False

你应该改变你的成功条件。例如：

acceptable_error = 0.000001
if abs(ans ** root - abs(num)) <= acceptable_error):
    # success

需要注意的是，如果你的线性搜索步伐很大，acceptable_error 也必须设置得大一些。

至于二分搜索，你应该有类似这样的代码：

while abs(ans ** root - abs(num)) > acceptable_error):
    ...