【leetcode】第69题 x 的平方根牛顿迭代法实现求平方根函数 C++

「爱情、让人受尽委屈。」 2022-01-16 03:26 380阅读 0赞

这题属于简单题，但是因为学到了新的算法：牛顿迭代法（或牛顿法），这里做一下记录。

**题目描述：**  
实现 int sqrt(int x) 函数。  
计算并返回 x 的平方根，其中 x 是非负整数。  
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

**示例 1:**  
输入: 4  
输出: 2

**示例 2:**  
输入: 8  
输出: 2  
说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

**方法1：牛顿迭代法**  
简介：  
牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

思路：  
设我们要求的是 n 的平方根，根据题意，则我们要求的是等式  x 2 − n = 0 x^2 - n=0 x2−n=0 的正整数解  
设  f ( x ) = x 2 − n f(x) = x^2 -n f(x)=x2−n ，则其导数为  f ′ ( x ) = 2 x f&\#x27;(x) = 2x f′(x)=2x，即  f ( x ) f(x) f(x) 的图像上任意一个点  ( x , y ) (x, y) (x,y) 的切线的斜率为  2 x 2x 2x，又因为我们要求的平方根是  f ( x ) f(x) f(x) 函数图像与 X 轴正半轴交点的 x值，我们可以用导数  f ′ ( x ) f&\#x27;(x) f′(x) 的函数图像（一条直线）与 X 轴正半轴的交点无限逼近所要求的值，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
**然后我们推导一下公式：**  
条件： f ( x ) = x 2 − n f(x)=x^2-n f(x)=x2−n ， f ′ ( x ) = 2 x f&\#x27;(x)=2x f′(x)=2x  
如上图中任选一点 ( x , f ( x ) ) (x,f(x)) (x,f(x))  
其切线的斜率为  f ( x ) x − x ′ \{f(x)\} \\over \{x-x&\#x27;\} x−x′f(x) = 2 x =2x =2x  
所以可得  x ′ = x − x&\#x27;=x- x′=x− f ( x ) 2 x \{f(x)\} \\over \{2x\} 2xf(x) ，即 x ′ = x − x&\#x27;=x- x′=x− x 2 − n 2 x \{x^2-n\} \\over \{2x\} 2xx2−n = = = x + n / x 2 \{x+n/x\} \\over \{2\} 2x\+n/x  
因此我们只需要任选一个 x，然后用 x 求出 x’，让 x’ 不断逼近所求的平方根就行。

**以下是代码：（其中的 x 即是公式中的 n，res 即是公式中的 x，因为函数名及其参数是题目规定好的。。）**

int mySqrt(int x){
        
            double res = 1;
            if( x == 0 || x == 1) return x;
            while( fabs( res*res - x ) > 0.5){
         // 相差小于0.5时退出循环
                res = ( res + x/res )/2;
            }
            return int(res);
     }

![在这里插入图片描述][20190615002856534.png]

**方法2：**  
普通暴力法，就是从1开始一直遍历到 x/2 + 1，找出 x 的平方根。（ x 的平方根不可能大于 x/2 + 1）  
只要注意使用长整型防止平方溢出就行。  
代码：

int mySqrt(int x){
        
            long long i=0;
            long long res;
            long long nextRes;
            if( x == 0 || x == 1) return x;
            for(i=1; i <= x/2+1; i++){
        
                res = i*i;
                nextRes = (i+1)*(i+1);
                if( res <= x && nextRes > x )
                    break;
            }
            return i;
        }

![在这里插入图片描述][20190615003006330.png]

**方法3：**  
改进版暴力法，和普通暴力思路一样，只是把遍历过程进行改进，使用二分法进行遍历，提高效率。

代码：

int mySqrt(int x){
        
            int left, right;
            if( x == 0 || x == 1) return x;
            left = 1;
            right = x/2 + 1;
            while(left <= right){
        
                long long mid = ( left + right )/2;
                long long res = mid * mid;
                if( res == x ) return mid;
                else if( res < x )
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            return right;
        }

![在这里插入图片描述][20190615003109704.png]

[github源码][github]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20220114/dd962fb98db14cf1a5b4ba1bf924c1fb.png
[20190615002856534.png]: /images/20220114/5ae9e8534f494b0a93a1804ce0007eb1.png
[20190615003006330.png]: /images/20220114/35709008c0ac495c92704b3948dbf644.png
[20190615003109704.png]: /images/20220114/cac6356766c040d786d6b5db8694394c.png
[github]: https://github.com/yohstone/Programming-practice/blob/master/leetcode-69-sqrt%28x%29.cpp