文章目录
穷举法求立方根
x = int(input('Enter an interger: '))
ans = 0
while ans**3 < abs(x):
ans = ans+1
if ans**3 != abs(x):
print(f'{x} is not a perfect cube.')
else:
if x < 0:
ans = -ans
print(f'Cube root of {str(x)} is {str(ans)}.')
穷举法求近似平方根
x = 25
epsilon = 0.01
step = epsilon**2
numGuesses = 0
ans = 0.0
while abs(ans**2-x) >= epsilon and ans <= x:
# 循环终止条件：
# ans**2 和 x 之间的差距小于 epsilon 时，
# 或者 ans>x, 也就是解空间不包含真正的答案，如0.25的平方根是0.5
print(f'ans={ans}, epsilon={epsilon}')
ans += step
numGuesses += 1
print(f'numGuesses={numGuesses}')
if abs(ans**2-x) >= epsilon:
print(f'Failed on square root of {x}.')
else:
print(f'{ans} is close to square root of {x}.')
二分法求近似平方根
x = 0.25
if x < 0:
print(f'{x} is a negative number which has no real square root.')
else:
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x) # 能够找到 0.5*0.5=0.25
ans = (low+high)/2
while abs(ans**2-x) >= epsilon:
print(f'low={low}, high={high}, ans={ans}')
numGuesses += 1
if ans**2 < x:
low = ans
else:
high = ans
ans = (low+high)/2.0
print(f'numGuesses={numGuesses}')
print(f'{ans} is close to square root of {x}.')
牛顿法求近似平方根
基于牛顿证明的一个定理：
如果某个数（令其为 guess ）是一个一元多项式 p(x) 的近似根，那么guess−p′(guess)p(guess)将会是一个更好的近似根。此处 p′是多项式 p(x) 的一阶导数。
利用该定理将求某个数（假设是c）的近似平方根的问题变成了 “求多项式 x2−c=0 的近似根”。
x = 0.25
if x < 0:
print(f'{x} is a negative number which has no real square root.')
else:
epsilon = 0.01
numGuesses = 0
guess = x/2.0
while abs(guess**2-x) >= epsilon:
print(f'guess={guess}')
numGuesses += 1
guess = guess - (((guess**2)-x)/(2*guess))
print(f'numGuesses={numGuesses}')
print(f'{guess} is close to square root of {x}.')
求数的n次方根，二分法+python函数机制
def findRoot(x, power, epsilon):
'''
x: 要求根的数
power: 求几次根
epsilon: 近似的精度
'''
# 排除x为负数或者power小于等于0的情况
if x < 0 and power % 2 == 0:
return None
low = min(-1.0, x)
high = max(1.0, x)
ans = (low+high)/2.0
while abs(ans**power - x) >= epsilon:
if ans**power < x:
low = ans
else:
high = ans
ans = (low+high)/2.0
return ans
参考书目：
《计算思维导论——一种跨学科的方法》