惨痛的教训——阿里一面

编程送分题,结果当时可能脑子进💩了,面试结束后,才知道自己有多么愚蠢。此贴仅以记录这一愚蠢时刻。
引以为戒。勿怠勿忘。
题目:求一整数的平方根,精确到0.001。

二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def sqrt_bi(num):
if num < 0:
raise ValueError("Please enter vaild number!")
if num == 0:
return 0
min_num = 0
max_num = num
while True:
if max_num * max_num == num or max_num - min_num < 1e-4:
return round(max_num, 3)
if min_num * min_num == num:
return round(min_num, 3)
mid = (max_num + min_num) / 2
if mid * mid > num:
max_num = mid
else:
min_num = mid

牛顿法

牛顿法用来求解方程$f(x)=0$的根。
原理:在初始值处做切线,该切线与x轴的交点作为下一个迭代值。切线方程为$y=f(x_0)+f’(x_0)(x-x_0)$,其与x轴交点为$x_1 = x_0-f(x_0)/f’(x_0)$。
对于方程$x^2-n=0$,更新式为$x^{new}=x^{old}-\frac{x^{old}-\frac{n}{x^{old}}}{2}$。

1
2
3
4
5
6
7
8
9
10
def sqrt_newton(num):
if num < 0:
raise ValueError('Please enter a valid number!')
if num == 0 or num == 1:
return num
last, res = 0, 1
while abs(last - res) > 1e-3:
last = res
res -= (res - num / res) / 2
return round(res, 3)