美团二面 - 求数的平方根,不使用Math.sqrt-阿里云开发者社区

开发者社区> 负债程序猿> 正文

美团二面 - 求数的平方根,不使用Math.sqrt

简介: 题目,给一个整数,求它的平方根,不能使用java自带的Math.sqrt(); 说来尴尬,我都不知道平方根是啥 0.0
+关注继续查看

题目,给一个整数,求它的平方根,不能使用java自带的Math.sqrt();


说来尴尬,我都不知道平方根是啥 0.0


贴心的面试官老哥告诉我就是开平方,比如4的平方根是2,100的平方根是10;


刚开始懵了,又是现场编程,本来就紧张,还不知道啥是平方根,严重影响发挥;


题解:

public class MySqrtDemo {
    public static void main(String[] args) {
        System.out.println(sqrt(100));//10
    }

    public static int sqrt(int i) {
        if (i <= 0) return i;
        int result;
        //从1开始疯狂试探
        for (int j = 1; true; j++) {
            if ((j * j <= i) && ((j + 1) * (j + 1) > i)) {
                result = j;
                //记得跳出循环
                break;
            }
        }
        return result;
    }
}

思路:

我这个方法没啥特点,就是从1开始疯狂试探,直到有一个数 i 满足i * i<=x&&((i+1)*(i+1)>x),这个 i 就是x的平方根;


优化

上面这个临时想出来的算法显然太鲁莽,优化优化

基于上面的算法,大体思路不会变,我们在 j * j 不等于入参的时候,对结果进行二分后再返回,无限二分,直到不能再细分,这样的值会更接近真实平方根;

public class MySqrtDemo {
    public static void main(String[] args) {
        System.out.println(sqrt(10));// 3.1622772216796875
        System.out.println(Math.sqrt(10));// 3.1622776601683795
    }

    public static double sqrt(int i) {
        if (i <= 0) return i;
        double result;
        //从1开始疯狂试探
        for (int j = 1; true; j++) {
            if (j * j == i) {
                result = j;
                //记得跳出循环
                break;
            } else if ((j * j < i) && ((j + 1) * (j + 1) > i)) {
                result = half(i, j, j + 1);
                //记得跳出循环
                break;
            }
        }
        return result;
    }

    public static double half(int i, double small, double big) {
        double average = (small + big) / 2;
        double result = average * average;
        if (result == i) {
            //如果平均值*平均值等于入参,直接返回
            return average;
        } else if (result > i) {
            //大于,则在前一个数和平均值之间递归二分
            if (String.valueOf(average).length() >= 18) return average;
            return half(i, small, average);
        } else {
            //小于,则在平均值后一个数之间递归二分
            if (String.valueOf(average).length() >= 18) return average;
            return half(i, average, big);
        }
    }
}

再次优化

利用牛顿法求解,这个解法对于我们这种学渣理解起来还是很有难度的,毕竟二次方程求导那些知识点早忘了

private static double mySqrt(int num) {
    double result = num;
    //精度控制,精确到多少位,但并不是截取到多少位,只是超过这个位数后面的值不精确了
    double accuracy = 0.001;
    //精度越高,循环次数越多
    while (result * result - num > accuracy) {
        //牛顿法,由切线方程求导转换而来,具体原理我还没搞懂 0.0
        result = (result * result + num) / (2 * result);
    }
    return result;
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
美团二面 - 求数的平方根,不使用Math.sqrt
题目,给一个整数,求它的平方根,不能使用java自带的Math.sqrt(); 说来尴尬,我都不知道平方根是啥 0.0
13 0
使用Matplotlib绘制正余弦函数、抛物线
今天第一次使用python的Matplotlib库,绘制函数非常方便,参考Matplotlib官方指南绘制了正余弦函数和抛物线.
548 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10089 0
Format方法使用详解
VBA 的 Format 函数与工作表函数 TEXT 用法基本相同,但功能更加强大,许多格式只能用于VBA 的 Format 函数,而不能用于工作表函数 TEXT ,以下是本人归纳的几点用法,不到之处,敬请谅解。
976 0
使用matplotlib和pygal实现数据可视化。
今天学习了:如何使用数据集以及如何对其进行可视化;如何使用matplotlib创建简单的图表,以及如何使用散点图来探索随机漫步过程;如何使用Pygal;来创建直方图,以及如何使用直方图来探索同时掷两个面数不同的骰子的结果。
2146 0
Java程序内存分析:使用mat工具分析内存占用
国内私募机构九鼎控股打造APP,来就送 20元现金领取地址:http://jdb.jiudingcapital.com/phone.html内部邀请码:C8E245J (不写邀请码,没有现金送)国内私募机构九鼎控股打造,九鼎投资是在全国股份转让系统挂牌的公众公司,股票代码为430719,为“中国PE第一股”,市值超1000亿元。
804 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13891 0
+关注
负债程序猿
知道的越多,不知道的越多
119
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载