LeetCode-69.Sqrt(x)-牛顿迭代法

淩亂°似流年 2022-03-09 07:10 308阅读 0赞

## 题目： ##

实现 int sqrt(int x) 函数。
    计算并返回 x 的平方根，其中 x 是非负整数。
    由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
    
    示例 1:
    
    输入: 4
    输出: 2
    示例 2:
    
    输入: 8
    输出: 2
    说明: 8 的平方根是 2.82842...,  由于返回类型是整数，小数部分将被舍去。

## 解题思路： ##

**注：使用 while(r \* r> x)会溢出**  
**牛顿迭代法**：计算x2 = n的解，令f(x)=x2-n，相当于求解f(x)=0的解。 首先取x0，如果x0不是解，做一个经过(x0,f(x0))这个点的切线，与x轴的交点为x1。 同样的道理，如果x1不是解，做一个经过(x1,f(x1))这个点的切线，与x轴的交点为x2。 以此类推。 以这样的方式得到的xi会无限趋近于f(x)=0的解。 判断xi是否是f(x)=0的解有两种方法： 一是直接计算f(xi)的值判断是否为0，二是判断前后两个解xi和xi-1是否无限接近。

**另一种解释**：设r是f(x) = 0的根，选取x0作为r初始近似值，过点（x0,f(x0)）做曲线y = f(x)的切线L，L的方程为`y = f(x0)+f'(x0)(x-x0)`，求出L与x轴交点的横坐标 x1 = x0-f(x0)/f’(x0)，称x1为r的一次近似值。 过点（x1,f(x1)）做曲线y = f(x)的切线，并求该切线与x轴交点的横坐标 `x2 = x1-f(x1)/f'(x1)`，称x2为r的二次近似值。重复以上过程，得r的近似值序列，其中`x(n+1)=x(n)－f(x(n))/f'(x(n))`，称为r的n+1次近似值，上式称为牛顿迭代公式。

经过(xi, f(xi))这个点的切线方程为`f(x) = f(xi) + f '(xi)(x - xi)`，其中f’(x)为f(x)的导数，本题中为2x。令切线方程等于0，即可求出`xi+1=xi - f(xi) / f'(xi)`。 继续化简：  
`xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2`。

public static int mySqrt(int x) {
            int r;
            if(x <= 1)
                return x;
            r = x;
            while(r > x / r)
                r = (r + x / r)/2;
            return(r);
        }

**切线方程：** 曲线C：y=f(x),曲线上点P(a,f(a)) f(x)的导函数f '(x)存在，以P为切点的切线方程：`y-f(a)=f '(a)(x-a)`