算法题 - 求一个正数的开方根 - Python

求一个正数的开方根问题描述给定一个正数a求这个数的开方根要求保留精度小数点后6位。问题分析这个题目是今天火山小视频第一个面试题其实之前就遇到过LeetCode69. Sqrt(x)和这个不同的是要求是保留小数点后六位但是无外乎还是使用二分法或者牛顿迭代法来做。这次特定介绍一种前几天看到的一个方法梯度下降法在朋友的博客上看到的但是他没有详细的整理和给出可运行的代码链接。那么现在先介绍一下牛顿迭代法然后是梯度下降法最后是二分法。1方法一牛顿迭代法最常用的方法把问题转换成求解函数f ( x ) x 2 − a 0 f(x) x^{2} - a0f(x)x2−a0的一个根。现在看看牛顿迭代公式不用详细介绍了很简单其中f ′ ( x ) 2 x f(x) 2xf′(x)2x图片来自百度百科# Time :2019/02/12# Author :LiuYinxing# Python3# 牛顿迭代法classSolution:def__init__(self,th1e-4):self.thth# 设置阈值threshold th1e-4defsqrt(self,a):ifa0:# 非正数均返回 0 不做进一步细分了哈return0x1.0# 设一个初始值初始化如果为负值找到的是负根whileabs(x*x-a)self.th:# 判断是否收敛x(xa/x)/2# x x - (x*x - a)/(2x)returnxif__name____main__:soluSolution()print(solu.sqrt(0.09))2梯度下降法令x a x \sqrt{a}xa​那么问题转换一下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)31​x3−ax对x xx求导的导函数也就是积分函数。现在对函数F ( x ) 1 3 x 3 − a x F(x) \frac{1}{3}x^{3} - axF(x)31​x3−ax进行梯度下降求极值求得的那个解很显然就是f ( x ) x 2 − a 0 f(x) x^{2} - a0f(x)x2−a0的一个根了。Python3实现# Time :2019/02/12# Author :LiuYinxing# Python3# 梯度下降法classSolution:def__init__(self,lr0.01,th1e-4):self.lrlr# 设置学习率 lr0.01self.thth# 设置阈值threshold th1e-4defsqrt(self,a):ifa0:# 非正数均返回 0 不做进一步细分了哈return0x5# 设一个初始值F_curx*x*x/3-a*x# 计算初始函数值error1whileabs(error)self.th:# 判断是否收敛x-self.lr*(x*x-a)# 迭代求x其实相当于更新梯度errorF_cur-(x*x*x/3-a*x)F_curx*x*x/3-a*xreturnxif__name____main__:soluSolution(lr0.01)print(solu.sqrt(88))上面代码存在什么样的问题问题1很显然它有两个根求出的是不是正数答函数F ( x ) 1 3 x 3 − a x F(x) \frac{1}{3}x^{3} - axF(x)31​x3−ax如何画出它的坐标图那么它一定是一个先递增–递减–递增的图像很显然就一个极小值点还一个极大值点。所以理论上只要初始化x xx的值 在( − a , ∞ ] (- \sqrt{a}, \infty](−a​,∞]范围内就可以迭代到极小值点。感觉是这样哈看下图辅助理解问题2尝试了一下因为要求三次方所以a aa比较大的情况下就要考虑调整参数了而且是求解要消耗一定时间。classSolution:def__init__(self,lr0.01,th1e-4):self.lrlr# 设置学习率 lr0.01self.thth# 设置阈值threshold th1e-4defsqrt(self,a):ifa0:# 非正数均返回 0 不做进一步细分了哈return0x5# 设一个初始值whileabs(x*x-a)self.th:# 判断是否收敛x-self.lr*(x*x-a)# 迭代求x其实相当于更新梯度returnxif__name____main__:soluSolution(lr0.01)xsolu.sqrt(88)print(x,x*x)3方法三二分法简单有效哈# Time :2019/02/12# Author :LiuYinxing# Python3 二分法classSolution:defsqrt(self,x,th):ifx0:return0# 非正数均返回 0 不做进一步细分了哈ifx1:# 初始化要分两个区间进行[0, 1], [1, 正无穷]low,high1,xelse:low,highx,1whilehigh-lowth:mid(lowhigh)/2mid2mid**2ifmid2x:returnmidelifmid2x:lowmidthelifmid2x:highmid-threturnhighif__name____main__:soluSolution()print(solu.sqrt(0.09,th1e-6))声明总结学习有问题或不当之处可以批评指正哦谢谢。