精华内容
下载资源
问答
  • Java-求根号n

    2017-09-16 19:33:00
    平方,开根号在java中是很简单的,Math.sqrt(double n)或者 Math.pow(double a, double b),a的b次方。但是我们可以自己想想,这些方法到底是怎么实现的。 就拿开根号来解释,它有两种方法,二分法和牛顿迭代法。...

    平方,开根号在java中是很简单的,Math.sqrt(double n)或者 Math.pow(double a, double b),求a的b次方。但是我们可以自己想想,这些方法到底是怎么实现的。

    就拿开根号来解释,它有两种方法,二分法和牛顿迭代法。

    二分法:

    比如求根号5

    第一步:折半:       5/2=2.5

    第二步:平方校验:  2.5*2.5=6.25>5,并且得到当前上限2.5,记录。

    第三步:再次向下折半:2.5/2=1.25

    第四步:平方校验:1.25*1.25=1.5625<5,得到当前下限1.25,记录

    第五步:再次折半:2.5-(2.5-1.25)/2=1.875

    第六步:平方校验:1.875*1.875=3.515625<5,得到当前下限1.875,替换下限值

    ......

    一直到与5的差值在你定义的误差范围内才结束循环

    代码:

    import java.text.DecimalFormat;
    
    public class Main {
          
        public static double sqrt(double num){
            if(num<0) {
                return -1;
            }
            
            double low = 0;
            double high = num/2;
            double precision = 0.000001;
            //格式化,保证输出位数
            DecimalFormat df = new DecimalFormat("#.00");
            
            double res = high;
            while(Math.abs(num-(res*res))>precision) {
                if(high*high > num) {
                    double n= high - (high-low)/2;
                    if(n*n>num) {
                        high = n;
                    } else if(n*n<num){
                        low = n;
                    }else {
                        return Double.valueOf(df.format(n));
                    }
                    res = n;
                    
                } else if(high*high < num){
                    double m = high + (high-low)/2;
                    if(m*m>num) {
                        low = high;
                        high = m;
                    } else if(m*m<num){
                        low = high;
                        high = m;
                    }else {
                        return Double.valueOf(df.format(m));
                    }
                    res = m;
                } else {
                    return Double.valueOf(df.format(high));
                }
            }
            
            return Double.valueOf(df.format(res));
        }
        
        public static void main(String[] args) {
            double a = 7;
            System.out.println(sqrt(37));
        }
    }

     

    牛顿迭代法:

    其实就是逼近的思想,例如我们要求a的平方根,首先令f(x)=x^2-a,那么我们的目的就是求得x使得f(x)=0,也就是求x^2-a这条曲线与x轴的交点,画图举例:

     

     

     

    由函数f(x)=x^2-a,我们求导可以知道,函数上任意一点(x,y)的切线的斜率为2x。假设过点(x0,y0)的切线方程为y=kx+b,那么切线与x轴的交点横坐标为-b/k。而b=y0-kx0,k=2x0,y0=x0^2-a,化简-b/k=(x0+a/x0)/2。

    也就是说(x0+a/x0)/2是过点(x0,y0)的切线与x轴的交点的横坐标。记(x0+a/x0)/2=x',继续求过点(x',f(x'))的切线与x轴的交点的横坐标x'',很明显x''比x'更靠近函数f(x)=x^2-a与x轴的交点的横坐标(即a的正平方根)。逐渐的逼近f(x)=0;

    所以公式为:x' = (x'+a/x')/2。

    代码:

    import java.text.DecimalFormat;
    
    public class Main1 {
        public static double sqrt(double x) {  
            if(x<0) {
                return -1;
            }
            //格式化,保证输出位数
            DecimalFormat df = new DecimalFormat("#.00");
            
            double k = x; 
            double precision = 0.000001;
            while((k*k-x)>precision) {
                k=0.5*(k+x/k);  
            }
            return Double.valueOf(df.format(k));
        }
        
        public static void main(String[] args) {
            double a = 9;
            System.out.println(sqrt(a));
        }
    }

     

    参考文献:

    二分法和牛顿迭代法求平方根(Python实现)

    牛顿迭代法求平方根

    转载于:https://www.cnblogs.com/loren-Yang/p/7532476.html

    展开全文
  • 一个数开根号的二分法和牛顿法

    千次阅读 2018-03-08 11:53:20
    偶然在知乎上看到求解一个数开根号怎么求,闲来无事练习下C;首先自己想到的就是二分法,写出来了才知道这个叫二分法,是一个比较直观的方法,比如求in的开根号,设置一个low,一个high,每次用low和high 的中值的...

    偶然在知乎上看到求解一个数开根号怎么求,闲来无事练习下C;

    首先自己想到的就是二分法,写出来了才知道这个叫二分法,是一个比较直观的方法,比如求in的开根号,设置一个low,一个high,每次用low和high 的中值的平方去和in比较,在误差范围之内就退出,误差大就继续迭代,然后根据每次比较的结果更新low和high 的值,最后得到一个理想的结果。


    牛顿法是在网上查的,做二分法时,感觉到可能迭代的太慢,二分肯定不是最优的,刚好看到牛顿迭代,在纸上画了下感觉也比较简单,就是求一个二次方程的根,根据切线方法来迭代,一下子找到迭代的规则,就可以写出来了。

    下面是二分法和牛顿法的求根号的结果,按理说是牛顿比较快,感兴趣的可以研究下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    double twofen(double in)
    {
    
    double out;
    double low,high;
    int i=0;
    if (in<=0) 
    	{
    		printf("fushu ,shurucuowu!");
    		return 0;
    	}
    	low=0;
    	high=in;
    
    while(fabs(in-out*out)>0.0001)
    
    	{     
    		out =(low+high)/2;
    		if(out*out>in)  	{high=out;}
    		else if(out*out<in) 	 {low=out;}
    		i++;        
    	}
    
    	return out;
    }
    
    double newton(double in)
    {
    	double current;
    	double next;
    	current=1;
    	while(fabs(next*next-in)>0.0001)
    	{
    	next=(current+in/current)/2;
    	current=next;
    	}
    	return next;
    }
    
    
    void main()
    {
    	double in;
    	printf("shuru yige zhengshu :\n");
    	scanf("%lf",&in);
    	printf("2fen(%lf) de jieguo shi %lf\n",in,twofen(in));
    	printf("---------------------\n");
    	printf("newton(%lf)de jieguo shi %lf\n",in,newton(in));
    	printf("finish");
    }

    注意的是都是double类型,如果不小心设置了int型,或者不小心用了abs,没用fabs就会得不到正确的结果哦。

    展开全文
  • 怎么最快找出出现过最多次的 QQ 号。(此题与稍后下文的第 14 题重复,思路参考请 见下文第 14 题)。 首先你要注意到,数据存在服务器,存储不了(内存存不了),要想办法统计每一个qq出现的次数。 比如,因为...
    腾讯 
    1.服务器内存 1G,有一个 2G 的文件,里面每行存着一个 QQ 号(5-10 位数),
    怎么最快找出出现过最多次的 QQ 号。(此题与稍后下文的第 14 题重复,思路参考请
    见下文第 14 题)。

           首先你要注意到,数据存在服务器,存储不了(内存存不了),要想办法统计每一个qq出现的次数。
    比如,因为内存是1g,首先  你用hash的方法,把qq分配到10个(这个数字可以变动,比较)文件(在硬盘中)。
    相同的qq肯定在同一个文件中,然后对每一个文件,只要保证每一个文件少于1g的内存,
    统计每个 qq 的次数,可以使用 hash_map(qq, qq_count)实现。
    然后,记录每个文件的最大访问次数的qq,最后,从10个文件中找出一个最大,即为所有的最大。

    那若面试官问有没有更高效率的解法之类的?
    这时,你可以优化一下,但是这个速度很快,hash函数,速度很快,他肯定会问,你如何设计,用bitmap 也行。

    2.如何求根号2的值,并且按照我的需要列出指定小数位,比如根号2是1.141,
    我要列出1位小数就是1.1,2位就是1.14,1000位就是1.141......等; 


    方法1:二分逼近 ,解方程,用折中法或者直线法逼近
    但是这种达不到很高的位数 
    方法2:用微积分函数展开,即将x^(1/2)展开

    解:√(1+x)=(1+x)^(1/2)(按泰勒公式展开) 
    =1+(1/2)x+(1/2)[(1/2)-1]x^2)/2!+(1/2)[(1/2)-1][(1/2)-2]x^3)/3!+…+(1/2)[(1/2)-1][(1/2)-2]…[(1/2)-n+1](x^n)/n!+o(x^n) 
    =1+(x/2)-(x&sup2;/8)+(x&sup3;/16)-…+[(-1)^(n-1)](2n-3)!!(x^n)/(2n)!! +o(x^n) 

    (2n)!!=(2n)×(2n-2)×(2n-4)×…×4×2,即隔一个相乘,一直乘到能取到的最小正整数。 
    则√2=(1+1)^(1/2) 
    =1+(1/2)-(1/8)+(1/16)-…+[(-1)^(n-1)](2n-3)!!/(2n)!!+o(1) 
    如按前四项展开,则√2≈1+(1/2)-(1/8)+(1/16)=1.4375 
    十分位是精确值,取的项越多,近似程度越高。

    //方法1: 
    #include<iostream>
    #include<stdio.h>
    #include<math.h> 
    #include<stdlib.h>
    #include<string.h>
    using namespace std; 
    
    double sqrtN(int n, int m)
    {
        double left=0;
        double right=n*1.0;
        double err=1,mid;
        for(int i=0;i<m;i++)
            err*=0.1;
       
        while(fabs(left-right)>err)
        {
            mid=(left+right)/2;
            if(mid*mid>(double)n)
                right=mid;
            else if(mid*mid<(double)n)
                left=mid;
        }
        return left;
    }
    
    int main()
    {
    	double res=sqrtN(2,8);
    	printf("%.8lf\n",res);
    	return 0; 
    }
    展开全文
  • 计算机如何实现开根号

    万次阅读 2015-05-20 14:58:16
    如何一个数字的算术平方根(又叫开根号,或者开方)? 大家普遍都是用计算器直接计算的,对于程序员来说,就是调用sqrt()方法。但是其内部又是怎么实现的呢?下面作了下总结。———-方法一:迭代法学过计算方法的...

    今天看到一个问题:计算机如何实现开根号?

    如何求一个数字的算术平方根(又叫开根号,或者开方)? 大家普遍都是用计算器直接计算的,对于程序员来说,就是调用sqrt()方法。但是其内部又是怎么实现的呢?下面作了下总结。

    ———-

    方法一:迭代法

    学过计算方法的应该都还有印象:一个函数 f(x) 在区间 [a,b] 上连续,且 f(x)=0 在 x∈[a,b] 上有解,求x?
    最简单的就是用二分法:分别求f(a)、f(b)、f[(a+b)/2],哪两个乘积为负数则把那两个区间当做 [a,b] ,然后一直循环,直到 a-b 达到要求的精度为止。
    再有一种就是用迭代法:迭代法有很多种,公共的思想是选一个数值,然后不断循环迭代,让它逐渐逼近真实解。至于怎么迭代可以让它趋近真实解,不同问题的求解用的迭代方法不同,我们暂且先忽略。
    其实二分法也算是迭代法的一种了。

    好了,直接看开根号的迭代法代码吧:

    double _sqrt(double a)
    {
        double x1 = a;
        double x2 = a/2;
        while(fabs(x1-x2) > 0.00000001)
        {
            x1 = x2;
            x2 = (x1+a/x1)/2;     ///////迭代的核心代码
        }
        return x1;
    }


    方法二:数学推导

    用计算机设计算法解决问题时,特别是数学问题,最直观的思路有两个。
    一个是利用计算机强大的计算能力,用穷举、递归、迭代等方法,直接求解,或者不断趋近、收敛于真实解。例如有些密码的破解,例如线性方程组的求解等等。
    另外一种就是利用数学,把问题用数学推导简化成一条公式,再通过计算机求解这条公式即可。最典型的就是圆周率Pi的计算公式:π/4=1-1/3+1/5-1/7+1/9-1/11+……

    百度里面有一个求开方的很好的方法,原址见此
    这里写图片描述
    以上方法可以笔算求解出任意一个正数的算术平方根。可是为什么要乘以20呢?为什么a要这样试验得到呢?这些数学原理我们不用深究,毕竟我们的目的不是搞数学研究。
    我们的重点是,这应该怎样转化成程序代码呢?我的大约思路是:
    1、用要求开方的这个数用字符数组存储,然后把它分隔成两个两个字符,用atoi函数转成int型存在一个整型数组里边,然后对这个整型数组进行操作。这样就能求任意长的数字的开方了,这是用第一种方法做不到的。
    2、看上面的图,暂且把193.9叫做商,把29、383、3869叫做除数。则:把商的每一位数存在int型数组里边,则各个除数都能用商的各位数表示出来了。
    3、逻辑实现:重点有两个,一个是除法的实现,另外一个是小数的处理。
    具体的代码就不放出来了。



    以上两种解法,只是解决了开根号的问题而已。我们注重的是求解思路,而不是具体的方法。毕竟生活中的问题不少,而解法又各式不同。但知道了从哪个方向去利用计算机开根号,那开立方、求对数 这些问题也就都容易解了。

    生命不息,学习不止,以后如果还遇到其他解法,再来补上。


    转载请注明出处,谢谢!(原文链接:http://blog.csdn.net/bone_ace/article/details/45870975
    展开全文
  • 我需要循环B=sqrt(i*i+a) , a是一个变量整数,i的范围从1-500,当i=182的时候,计算溢出,请问怎么处理呀? i是int, a是float, B也是float 怀疑这里的int的范围在32767之间,i=182平方刚好溢出,请问我需要...
  • 牛顿迭代这个名字听起来好像非常的高大上,但是其实也算是比较基础的数学,让我们来分析一下牛顿迭代到底是怎么样解决开更好的问题吧。 首先我们来看一下根的函数式 f(x)=x2−vf(x) = x^2 - vf(x)=x2−v 当f(x)=0f...
  • 方法还是一样的,只不过另外一边是负数开根号,得到单位为i的复数 这个题目的话: x^2-2x+1=-4 (x-1)^2=-4 x-1=正负2i x=1+2i或1-2i 就是 根号下(-16)的结果是:正负i 根号下(-16)的结果是:正负i ...
  • 12、计算机如何实现开根号

    千次阅读 2018-04-17 10:16:44
    如何一个数字的算术平方根(又叫开根号,或者开方)? 大家普遍都是用计算器直接计算的,对于程序员来说,就是调用sqrt()方法。但是其内部又是怎么实现的呢? 方法一:迭代法 学过计算方法的应该都还有印象:...
  • 怎么想都没想出来 $\log n$ 做法,那么这道题基本就是根号分治了. 题目描述中保证 $\sum k \leqslant 10^5$,然后 $k$ 在每次询问中又是相同的,那么就考虑对 $k$ 根号分治. 先对 $s$ 建立后缀自动机,然后把倍增...
  • 递归最大素因数(java)

    千次阅读 2018-10-16 22:36:45
    首先分析,怎么求一个数的最大素因数。首先,我们以前求过最大因数,求最大因数的最暴力为2—n-1暴力查找,但是这样太超时了,后来发现在根号n前或者后某个区域查找就行了。因为找某个因数时候。n=a* b;a=根号n;...
  • 当需要对复数求模的时候,用FPGA怎么求呢?怎么开根号? 方法1:先求幅值平方和,再使用cordic IP开根号。(蠢办法) 方法2:直接用cordic求取模值。 此处只介绍方法2,资源占用更少,更方便。 求模原理如下图...
  • 现在有一个16000的复数指针complex,将它理解为一个二维数组 Rn = complex[n][0]是实部,In = complex[n][1]是虚部,(n=0,1,2,3......15999),我想这个复数的模 也就是 根号(Rn^2+In^2) (复数的绝对值也是...
  • 牛顿迭代法平方根

    千次阅读 2016-01-16 19:37:26
    直接进入主题,打开计算器平方根到底是怎么计算的,一直是我心里的一个疑问,从上初中学了根号以后,老师就让我背根号2等于1.41,根号三是1.732,其他的不用记,题目出现会在后面告诉你。那么这些数字到底是怎么来的...
  • 求根号5 a:折半: 5/2=2.5 b:平方校验: 2.5*2.5=6.25>5,并且得到当前上限2.5 c:再次向下折半:2.5/2=1.25 d:平方校验:1.25*1.25=1.5625<5,得到当前下限1.25 e:再次折半:2.5-(2.5-1.25)/2=1.875 f:平方校验:1....
  • 原文地址 一个数的平方根函数sqrt(int num) ,在大多数语言中都提供实现。那么要求一个数的平方根,是怎么实现的呢? ...实际上平方根的算法方法主要...求根号5 a:折半: 5/2=2.5 b:平方校验: 2.5*2.5=6
  • Q:求解小于或等于整数N的最大素数 A:穷举法枚举从N到√N,逐个用2到√N的数去...怎么证明最大素数一定在根号n到n之间出现? A:伯特兰-切比雪夫定理 //根号n到n的每一个数的因数范围都可以被n的判断范围所...
  • javascript算数运算

    2010-08-31 09:45:00
    在js中没有什么公式是用来开根号,求...怎么求对数呢? log(16)4 = Math.log(16)/Math.log(4) 怎么开根号? 16开根号2 =Math.pow(16,1/2) 转载于:https://www.cnblogs.com/lunalord/archive/2010/08/31/1813353.html...
  • 51nod 1239欧拉函数之和

    2017-02-16 15:14:51
    题意:1-n的欧拉函数前缀和,n^10; 这题要有一定数学基础。。 ...这里就不赘述了,毕竟...问题是出来了式子以后怎么做。 n/i>根号n的取值只有根号n个,小于的也是,那么我们可以预处理根号n以内的,根号n以上的递
  • POJ3347计算几何

    2019-04-01 09:18:22
    怎么求左右端点的左边呢?假设求第i个正方形左端点,已知前i-1个,那么我们假设第i个与前面几个都相切,求左端点,然后取最大值。相切怎么求?画画图就很清楚了。 最后不断缩小左右端点的范围。只有边长长的才能...
  •   如果给你一个数N,让你去求N的约数是多少,你应该怎么求呢?我们当然可以暴力的从1到N循环一遍,然后看有多少个数能够被N整除就可以,时间复杂度为O(N),但是如果当这个N足够大的时候,这个时间肯定是很长的呢。...
  • [luogu3601]签到题

    2019-09-22 16:32:39
    一个朴素的想法是枚举l~r,根号求\(\phi\),显然这样是\((r-l)\sqrt r\),时间无法承受 考虑怎么优化\(\phi\)的时间, 我们知道对于一个数x,超过\(\sqrt x\)的质因子最多只有一个 我们考虑对[l,r]的数开vector记录质...
  • 19.1 三角形的面积问题描述:给出三角形的三条边,其面积。提示: Python的开根号函数sqrt。你需要判断三角形三边的关系,a+b>c,即任意两边之和大于第三边。19.2在命令下实验结果:19.3 Python程序实现如下:...
  • 2道腾讯面试的C++题目

    2013-02-25 23:57:20
    1.服务器内存1G,有一个2G的文件,里面每行存着一个QQ号(5-10位数),怎么...2.如何求根号2的值,并且按照我的需要列出指定小数位,比如根号2是1.141 我要列出1位小数就是1.1 2位就是1.14, 1000位就是1.141...... 等
  • 首先这题如果想用O(N)做就too native了~ 所以我们就要寻求更有效的算法。 其实hzwer讲得挺好的: 题目中要求出∑gcd(i,N)(1 ...枚举n的约数k,令s(k)为满足gcd(m,n)=k,(1 ...至于笔者一开始没想到怎么根号时间

空空如也

空空如也

1 2 3
收藏数 59
精华内容 23
关键字:

根号怎么求