每周一道算法题(五十二)
2018-05-13 本文已影响30人
CrazySteven
上周题目难度Hard，就没做。本周题目难度'Easy'，使用语言'Python'
题目：求一个数的平方根，精确到整数即可。
思路：追求简单的直接return int(math.sqrt(x))就行了，这里我们用牛顿迭代法来做。原则就是Xn与Xn+1的差值小于0.00001(不同的精度数值不一样)即可。Xn与Xn+1的关系是Xn+1 = Xn * 0.5 + X / (2 * Xn)，知道这两条就很简单了。
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if (x <= 1): return x
# 定义Xn与Xn+1
x1 = 1
x2 = x1 * 0.5 + x / (2 * x1)
# 满足精度返回结果即可
while(abs(x1 - x2) > 0.00001):
x1 = x2
x2 = x1 * 0.5 + x / (2 * x1)
return int(x1)
效率尚可，这题还可以用二分法，泰勒展开等来做。
