Java习题之实现平方根(sqrt)函数

这篇具有很好参考价值的文章主要介绍了Java习题之实现平方根(sqrt)函数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言

二分查找

牛顿迭代法

总结


🎁博主介绍:博客名为tq02,已学C语言、JavaSE,目前学了MySQL和JavaWeb

🎥学习专栏:  C语言        JavaSE      MySQL基础

🎄博主链接:tq02的博客_CSDN博客-C语言,Java,MySQL领域博主

前言

        可使用java.lang.Math类的sqrt(double)方法求平方根。Math是java.lang包中的类,而Double为对象中的基本类型。但是如果不使用库函数呢?有什么办法实现平方根函数呢?

        方法:二分查找牛顿迭代法、利用平方数的性质


利用平方数的性质

        平方数的性质:n²=1+1+2+2+....+n-1+n-1+n。例如4²=1+1+2+2+3+3+4=16。

1+3为2的平方,1+3+5为3的平方,

Java习题之实现平方根(sqrt)函数,Java习题,java,开发语言,笔记

也就是说每一次加一个奇数,再设置一个变量记录加了多少个奇数。 

复杂度分析:
时间复杂度:O(N),每次+2的循环,为(1/2)N的时间复杂度,去掉系数,为O(N)
空间复杂度: O(1),只使用了有限常数个变量;

int sqrt(int x) {
     if(x<=0) return 0;  //小于等于0 返回0
     int ans = 1; 
     int num = 1;
     int  i = 3;
     while(num+i<=x){
         num+=i;  
          ans ++; // 每加一个奇数,ans+1
          i += 2;
        }
        return ans;
    }

二分查找

        如果求解一个数的平方根,这个结果肯定是在1到这个数的范围,因此我们可以使用二分查找的方法。例如求解x的平方根,思路

  1. 初始范围:1 ~ x,使用left标记1,right标记x ,取left~right的中间值,为 middle
  2. middle*middle <= x && (middle+1)*(middle+1) > x时,返回结果
  3. 当 middle*middle < x时,到右半部分继续寻找,范围改成 middle+1 ~ right
  4. middle*middle > x时,到左半部分继续寻找,范围改成 left ~ middle+1

注: 这种方法只能使用于整数的开跟

Java习题之实现平方根(sqrt)函数,Java习题,java,开发语言,笔记

复杂度分析:
时间复杂度:O(logn),二分查找的复杂度,每次循环减少一半
空间复杂度;O(1),只使用了有限常数个变量;

代码实现: 

public int mySqrt(int x) {
    if (x <= 0) {
        return 0;
    }
    int left = 1, right = x;
    while (true) {
        int middle = (left + right) >> 1;
        if (middle <= x / middle && (middle+1) > x / (middle+1)) {
            return (int) middle;
        } else if (middle < x / middle) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
}

牛顿迭代法

牛顿迭代法简介

         假设方程 F(x)=0  在 x 附近有一个根,那么用以下迭代式子:

Java习题之实现平方根(sqrt)函数,Java习题,java,开发语言,笔记

 依次计算X1、X2、X3、...........那么序列将无限逼近方程的根。

  牛顿迭代法的原理很简单,其实是根据f(x)在x0附近的值和斜率,估计f(x)和x轴的交点,看下面的动态图:

Java习题之实现平方根(sqrt)函数,Java习题,java,开发语言,笔记

Java习题之实现平方根(sqrt)函数,Java习题,java,开发语言,笔记

 代码示例:

public class Solution {
	public int sqrt (int x) {//牛顿迭代法
        if(x==0||x==1) return x;//题中告诉我们x的范围: 0 <= x < 2^31-1
		long X0 = x;//使用int进行加法运算可能溢出,所以采用long型
		long X1 = 0;//下一个迭代变量,为了方便理解,也可只使用X0
		while(X0 > x/X0 ) {    // X0^2>x循环
			X1=(X0+x/X0) >> 1;//由迭代公式得,采用右移1位操作代替除以2,运算更快
			X0=X1;//把下一个迭代变量赋给X0,统一操作,方便继续处理
		}
		return (int)X0;//返回值类型为int,因此需要做强制类型转换
    }
}

       

总结

        牛顿迭代法不像二分查找法、平方数,需要唤醒一下各位哥哥姐姐们的高中数学知识,只有这样才能理解该公式。如果唤醒失败,推荐使用二分查找法,不要逞强哦。文章来源地址https://www.toymoban.com/news/detail-552004.html

到了这里,关于Java习题之实现平方根(sqrt)函数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 平方根法、改进的平方根法解方程组

    本篇内容包含两个部分:平方根法、改进的平方根法。感觉这种题绝大部分是靠套公式,记住公式和解题思路,还是相当简单的。 1 平方根法 1.1 解题思路 1.2 核心公式 1.3 例题解析 由 Ly=b L^t*x=y 解得 2 改进的平方根法 2.1 为什么要使用改进的平方根法 2.2 改进的平方根法解题公

    2024年02月06日
    浏览(52)
  • Python求平方根

    Python求平方根的方法有很多种,但是在不同情况下使用也不同 方法一:常用的是math模块的sqrt()函数 方法二:math模块的pow()函数 方法三:使用内置函数pow() 有时候math模块无法使用,这时候就需要使用自带的内置函数pow() 方法四:使用指数运算符** 注:将其中的1/2换成1/3则是

    2024年02月05日
    浏览(38)
  • leetcode69---x 的平方根

    大家好,我是大唐,刚刷完了几道经典的leetcode题,今天给大家分享一道leetcode上面的二分查找经典题型---x 的平方根,我们往下看。 给你一个非负整数  x  ,计算并返回  x  的  算术平方根  。 由于返回类型是整数,结果只保留  整数部分  ,小数部分将被  舍去 。 注意

    2024年03月18日
    浏览(45)
  • Python算法例4 求平方根

    实现int sqrt(int x)函数,计算并返回x的平方根。 sqrt(3)=1;sqrt(4)=2;sqrt(5)=2;sqrt(17)=4。 要实现计算整数x的平方根函数sqrt(x),可以使用二分查找法。 首先,我们定义一个变量left = 0用来表示搜索区间的左边界,以及一个变量right = x用来表示搜索区间的右边界。初

    2024年02月05日
    浏览(39)
  • leetcode69 x 的平方根

    题目变形为找到 f ( x ) = x 2 − c = 0 f(x)=x^2-c=0 f ( x ) = x 2 − c = 0 的根,其中 x x x 是非负整数。由于 f ( 0 ) = − c ≤ 0 , f ( c ) = c 2 − c ≥ 0 f(0)=-cle0,f(c)=c^2-cge0 f ( 0 ) = − c ≤ 0 , f ( c ) = c 2 − c ≥ 0 ,则 [ 0 , c ] [0,c] [ 0 , c ] 之间必然存在一个根,使用二分法。 但是由于计算

    2024年02月22日
    浏览(42)
  • FPGA verilog 简单的平方根求法

    用下面的平方根求法不需要乘法,只需简单的移位就能实现。 原理参照论文 A New Non-Restoring Square Root Algorithm and Its VLSI Implementations

    2024年02月04日
    浏览(35)
  • LeetCode每日一题——x 的平方根

    乍一看题目只需要算一个数的平方根,根据我们之前学的C语言我们能很快的想到使用sqrt,pow这类的math.h库函数,但是题目要求我们不能使用,那么我们便可以使用我们的数学思想,将给的整数拆成两个一样的数相乘。 代码实现: 运行结果:   PS:看到这里了,码字不易,给

    2024年03月23日
    浏览(48)
  • 力扣:69. x 的平方根(Python3)

    给你一个非负整数  x  ,计算并返回  x  的  算术平方根  。 由于返回类型是整数,结果只保留  整数部分  ,小数部分将被  舍去 。 注意: 不允许使用任何内置指数函数和算符,例如  pow(x, 0.5)  或者  x ** 0.5  。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球

    2024年02月12日
    浏览(69)
  • 【算法专题突破】二分查找 - x 的平方根(18)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:69. x 的平方根 - 力扣(LeetCode) 这道题就是求算数平方根, 要注意的点是他只需要保留整数部分,小数部分会舍去 我们确定好一个区间 1 ~ x,数字 x 的算数平方根一定在这里面, 最简单的思路就是用暴力解法

    2024年02月07日
    浏览(39)
  • 算法leetcode|69. x 的平方根(rust重拳出击)

    给你一个非负整数 x ,计算并返回 x 的 算术平方根 。 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。 注意 :不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。 0 = x = 2 31 - 1 面对这道算法题目,二当家的再次陷入了沉思。 要开平方,但

    2024年02月13日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包