题号：69
难度：Easy
链接：https://leetcode.cn/problems/sqrtx/

思路

看到本题的第一眼，便认定这是个数学问题，一定有一个计算平方根的数学原理。这东西不大可能靠我这点数学能力想出来了，果断搜索相关内容。

果不其然，我找到了牛顿迭代法。

对于方程 $f(x)=0$ ，可以由以下迭代式求取近似值：

$$
x{n+1} = x{n} - \frac{f(x_n)}{f'(x_n)}
\tag{1}
$$

对于本题，方程可设为：

$$
f(x)=x^2 - N
\tag{2}
$$

其中 $N$ 就是函数的传入参数x。

那么：

$$
f'(x)=2x
\tag{3}
$$

将方程 $(2)$ 和 $(3)$ 代入 $(1)$ 式可得：

$$
x{n+1} = x{n} - \frac{x_{n}^{2} - N}{2x_n}
\tag{4}
$$

化简后可得：

$$
x{n+1} = \frac{x{n} - \frac{N}{x_{n}}}{2}
\tag{5}
$$

有了具体的迭代公式，便可以开始写代码了。另外，牛顿迭代法需要一个初值，我这里设为传入参数的一半。

代码

#include <math.h>

using std::abs;

class Solution {
public:
    int mySqrt(int x) {
        if(x<2) return x;
        double root=x/2;
        while(abs(root*root - x)>=1) root=(root+x/root)/2;
        return int(root);
    }
};

while中的条件指定了误差范围，在误差绝对值大于等于1时继续迭代，否则停止迭代，并返回抹去小数部分的近似值。

其实从具体代码来看，也不难理解迭代的原理。

在root=(root+x/root)/2;一句中，等式右边的root和x/root，其实可以理解为近似区间的上下界。在确定root为边界后，显然x/root可以作为另一个边界，而将区间中点作为近似值。当精度不达要求时，便进一步缩小区间，直到满足要求。

提交结果

大成功。去评论区逛了一圈，高赞解法也用此方法。

虽然这次不是完全独立完成，但也很满足了。

全文完