LeetCode x的平方根

在网上学习了其他人的方法以后，写了出来，学到了新的方法，在此记录一下

1，返回整型的时候，可以使用二分法

2 ，返回double时，可以使用牛顿迭代法，

a、求取一个整数的平方根时，其平方根一定是不大于（n/2+1),所以在（0,n/2+1]这个范围内求取，

代码如下：

    int mySqrt(int x) {
        if(x <= 1)
            return x;
        long i = 0;
        long j = x/2 + 1;
        long mid = 0;
        while(i <= j)
        {
        	mid = (i+j)/2;
        	if(mid*mid == x)
        		return (int) mid;
        	if(mid*mid < x)
        		i = mid + 1;
        	else
        		j = mid - 1;
        }
        if(mid*mid > x)
        	mid--;
		return (int) mid;

    }

b、当返回double时，二分法不能实现，需要使用牛顿迭代法，所谓牛顿迭代法：在本题目中，需要对x^2=n求取x，即f(x)=x^2-n，令f(x)=0，即可求出解。首先选取一个x0，如果x0不是此方程的解，那么就过(x0,f(x0))做曲线的切点，切点与x轴的交点为x1,c再验证x1是不是方程的解，以此迭代，到xi时，求出方程的解，得到f(xi)=0。

切线的方程为，f(x)-f(xi)=f(xi)'(x-xi)，

令切线方程为0，得到解xi+1=xi-f(xi)/f(xi)'，

在本题目中，f(x)求导后得到f(x)'为2x，

所以代入后得到xi+1=(xi+n/xi)/2。

终止程序判断条件可为，xi是否等于xi-1或者f(xi)师傅等于0。

LeetCode x的平方根

代码如下：

double sqrt(double x) {
	if (x == 0) return 0;
	double last = 0.0;
	double res = 1.0;
	while (res*res-x!=0)
	{
		last = res;
		res = (res + x / res) / 2;

	}
	return res;
}

参考自：http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html

LeetCode x的平方根

相关推荐