Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

思路：二分查找法解决这道题

class Solution { public:int sqrt(int x) {if(x<=1)return x;int low=1;int high=x;while(low<=high){int mid=low+(high-low)/2;if(mid==x/mid)return mid;else if(mid<x/mid)low=mid+1;elsehigh=mid-1;}return high;} };

 思路二：用牛顿求根法。首先，选择一个接近函数零点的，计算相应的和切线斜率（这里表示函数的导数）。然后我们计算穿过点并且斜率为的直线和轴的交点的坐标，也就是求如下方程的解：

我们将新求得的点的坐标命名为，通常会比更接近方程的解。因此我们现在可以利用开始下一轮迭代。迭代公式可化简为如下所示：

已经证明，如果是连续的，并且待求的零点是孤立的，那么在零点周围存在一个区域，只要初始值位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。

class Solution { public:int sqrt(int x) {if(x<=1)return x;double a=x;double b=0;while(abs(b-a)>1e-6){b=a;a=(b+x/b)/2;}return (int)a;} };

 

 

转载于:https://www.cnblogs.com/awy-blog/p/3750307.html

总结

以上是生活随笔为你收集整理的Sqrt(x)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。