首页 > 代码库 > Leetcode:sqrt 开方运算
Leetcode:sqrt 开方运算
戳我去解题
Implement int sqrt(int x)
.
Compute and return the square root of x.
1. 二分查找
2. 牛顿迭代法
不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根,这个函数的导数是2x。
也就是说,函数上任一点(x,f(x))处的切线斜率是2x。那么,x-f(x)/(2x)就是一个比x更接近的近似值。
代入f(x)=x^2-a得到x-(x^2-a)/(2x),也就是(x+a/x)/2。
一个sqrt引发的血案
牛顿迭代法
class Solution { public: int sqrt(int x) { assert(x >= 0); double tmp = x; double exp = 10e-5; while (fabs(tmp * tmp - x) > exp) { tmp = 0.5 * (tmp + x / tmp); } return tmp; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。