本文共 917 字，大约阅读时间需要 3 分钟。

141. x的平方根

实现 int sqrt(int x) 函数，计算并返回 x 的平方根。

样例

样例 1:

输入: 0

输出: 0

样例 2:

输入: 3

输出: 1

样例解释：

返回对x开根号后向下取整的结果。

样例 3:

输入: 4

输出: 2

挑战

O(log(x))

public class Solution {

    /**

     * @param x: An integer

     * @return: The sqrt of x

     */

    public int sqrt(int a) {

        // write your code here

        double x = 1.0;

        double cheak;

        do {

            x = (a / x + x) / 2.0;//差不多可以理解为二分查找，X是a的平方根

            cheak = x * x - a;//当前x的平方和a的误差

        } while ((cheak >= 0 ? cheak : -cheak) >0.1);//0.1代表误差

        // System.out.println(x);

        return (int) x;

    }

}

牛顿迭代法

比如136161这个数字，首先我们找到一个和136161的平方根比较接近的数，任选一个，比方说300到400间的任何一个数，这里选350，作为代表。

　　我们先计算0.5(350+136161/350)，结果为369.5。

　　然后我们再计算0.5(369.5+136161/369.5)得到369.0003，我们发现369.5和369.0003相差无几，并且369²末尾数字为1。我们有理由断定369²=136161。

　　一般来说，能够开方开的尽的，用上述方法算一两次基本结果就出来了。再举个例子：计算 。首先我们发现600²<469225<700²，我们可以挑选650作为第一次计算的数。即算0.5(650+469225/650)得到685.9。而685附近只有685²末尾数字是5，因此685²=469225。从而 。　

　　对于那些开方开不尽的数，用这种方法算两三次精度就很可观了，一般达到小数点后好几位。

　　实际中这种算法也是计算机用于开方的算法

转载地址：https://blog.csdn.net/xwdrhgr/article/details/116004921 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！