算法题 - 求一个正数的开方根 - Python
问题描述：
给定一个正数a，求这个数的开方根，要求保留精度小数点后6位。
问题分析：
这个题目是今天火山小视频第一个面试题，其实之前就遇到过，LeetCode：69. Sqrt(x)和这个不同的是，要求是保留小数点后六位，但是无外乎还是使用二分法或者牛顿迭代法来做。这次特定介绍一种前几天看到的一个方法，梯度下降法（在朋友的博客上看到的，但是他没有详细的整理和给出可运行的代码：链接）。那么现在先介绍一下牛顿迭代法，然后是梯度下降法，最后是二分法。
（1）方法一：牛顿迭代法（最常用的方法）：
把问题转换成，求解函数f ( x ) = x 2 − a = 0 f(x) = x^{2} - a=0f(x)=x2−a=0的一个根。现在看看牛顿迭代公式，不用详细介绍了，很简单：
其中：f ′ ( x ) = 2 x f'(x) = 2xf′(x)=2x
（图片来自百度百科）
# @Time :2019/02/12# @Author :LiuYinxing# Python3# 牛顿迭代法classSolution:def__init__(self,th=1e-4):self.th=th# 设置阈值threshold th=1e-4defsqrt(self,a):ifa<=0:# 非正数均返回 0 ，不做进一步细分了哈return0x=1.0# 设一个初始值（初始化如果为负值，找到的是负根）whileabs(x*x-a)>=self.th:# 判断是否收敛x=(x+a/x)/2# x = x - (x*x - a)/(2x)returnxif__name__=='__main__':solu=Solution()print(solu.sqrt(0.09))（2）梯度下降法：
令x = a x = \sqrt{a}x=a，那么问题转换一下，f ( x ) = x 2 − a f(x) = x^{2} - af(x)=x2−a，即求f ( x ) = 0 f(x)=0f(x)=0的一个解。现在问题是，如何把这个问题转换成梯度下降问题，一般的认识是梯度下降法是求解极值问题，我们把这个问题转换成极值问题即可，不难看出，f ( x ) = x 2 − a f(x) = x^{2} - af(x)=x2−a是函数F ( x ) = 1 3 x 3 − a x F(x) = \frac{1}{3}x^{3} - axF(x)=31x3−ax对x xx求导的导函数（也就是积分函数）。
现在对函数F ( x ) = 1 3 x 3 − a x F(x) = \frac{1}{3}x^{3} - axF(x)=31x3−ax进行梯度下降求极值，求得的那个解，很显然就是f ( x ) = x 2 − a = 0 f(x) = x^{2} - a=0f(x)=x2−a=0的一个根了。
Python3实现：
# @Time :2019/02/12# @Author :LiuYinxing# Python3# 梯度下降法classSolution:def__init__(self,lr=0.01,th=1e-4):self.lr=lr# 设置学习率 lr=0.01self.th=th# 设置阈值threshold th=1e-4defsqrt(self,a):ifa<=0:# 非正数均返回 0 ，不做进一步细分了哈return0x=5# 设一个初始值F_cur=x*x*x/3-a*x# 计算初始函数值error=1whileabs(error)>=self.th:# 判断是否收敛x-=self.lr*(x*x-a)# 迭代求x，其实相当于更新梯度error=F_cur-(x*x*x/3-a*x)F_cur=x*x*x/3-a*xreturnxif__name__=='__main__':solu=Solution(lr=0.01)print(solu.sqrt(88))上面代码存在什么样的问题：
问题1：很显然它有两个根，求出的是不是正数？
答：函数F ( x ) = 1 3 x 3 − a x F(x) = \frac{1}{3}x^{3} - axF(x)=31x3−ax如何画出它的坐标图，那么它一定是一个先递增–>递减–>递增的图像，很显然就一个极小值点（还一个极大值点）。所以理论上只要初始化x xx的值 在( − a , + ∞ ] (- \sqrt{a}, +\infty](−a,+∞]范围内，就可以迭代到极小值点。（感觉是这样哈，看下图辅助理解）
问题2：尝试了一下，因为要求三次方，所以a aa比较大的情况下，就要考虑调整参数了，而且是求解要消耗一定时间。
classSolution:def__init__(self,lr=0.01,th=1e-4):self.lr=lr# 设置学习率 lr=0.01self.th=th# 设置阈值threshold th=1e-4defsqrt(self,a):ifa<=0:# 非正数均返回 0 ，不做进一步细分了哈return0x=5# 设一个初始值whileabs(x*x-a)>=self.th:# 判断是否收敛x-=self.lr*(x*x-a)# 迭代求x，其实相当于更新梯度returnxif__name__=='__main__':solu=Solution(lr=0.01)x=solu.sqrt(88)print(x,x*x)（3）方法三：二分法（简单有效哈）
# @Time :2019/02/12# @Author :LiuYinxing# Python3 二分法classSolution:defsqrt(self,x,th):ifx<=0:return0# 非正数均返回 0 ，不做进一步细分了哈ifx>=1:# 初始化要分两个区间进行，[0, 1], [1, 正无穷]low,high=1,xelse:low,high=x,1whilehigh-low>th:mid=(low+high)/2mid2=mid**2ifmid2==x:returnmidelifmid2<x:low=mid+thelifmid2>x:high=mid-threturnhighif__name__=='__main__':solu=Solution()print(solu.sqrt(0.09,th=1e-6))声明：总结学习，有问题或不当之处，可以批评指正哦，谢谢。