首页 > 编程语言 > 详细

一个求解平方根的算法题

时间:2018-06-20 10:44:59      阅读:265      评论:0      收藏:0      [点我收藏+]

1. 问题描述

问题是这样子的,给定一个数a,求解这个数的平方根,要求精度f<0.0001.

好久没有操刀实现算法代码了,今天就来写一个小的,后续算法依旧是研究的重点。比较软件中,算法是核心是灵魂啊!

 

2. 算法分析

说起来,这个算法题其实不是太麻烦,主要采取的就是不断试探,逼近真是目标值的思路,最容易想到的就是,不断的折半逼近,有点类似二分的思想。同时,一个重要的思想:

1. 设目标值平方根为Se

2. 待求解的输入数据为St

3. |Se*Se - St| < f*f

4. 求出一个Se*Se - St > 0的情况下的Se值,因为平方根分正负两个值,求出一个即可,这里求正值

 

3. 实现过程

这里,直接上JAVA的实现代码,注意,这里只实现了平方根大于1的问题场景,至于平方根在0~1之间这种场景,未处理!

package pingFangGeng;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

/**
 * @author shihuc
 * @date  2018年6月19日 上午8:31:51
 * 
 * 本算法近似计算一个大于1的数字的平方根
 */
public class Solution {

    /**
     * @author shihuc
     * @param args
     */
    public static void main(String[] args) {
        Scanner scan = null;
        try {
            scan = new Scanner(new File("./src/pingFangGeng/input.txt"));
            int count = scan.nextInt();
            for(int i = 0; i < count; i++){
                int source = scan.nextInt();
                double fraction = scan.nextDouble();
                double res = binDivFind(0, source, source, fraction*fraction);
                System.out.println("No." + i + ": source=" + source + ", fraction=" + fraction + ", result=" + res);
            }
        } catch (FileNotFoundException e) {            
            e.printStackTrace();
        } finally {
            if (scan != null){
                scan.close();
            }
        }
    }
    
    /**
     * 算法思路:
     * |Se*Se - St| < fraction*fraction
     * 其中Se为目标值,St为给定待求解的数据,fraction为给定的精度
     *  
     * @author shihuc
     * @param src
     * @param fraction
     * @return
     */
    private static double binDivFind(double st, double ed, double tar, double fraction) {
        double Se = (double) ((st + ed) / 2);
        double Se2 =  Se * Se;
        double Set = Se2 - tar;
        double res = Set * Set;
        double rval = Se;
        if(res >= fraction){
            if(Set > 0){
                rval = binDivFind(st, Se, tar, fraction);
            }else{
                rval = binDivFind(Se, ed, tar, fraction);
            }
        }
        return rval;
    }

}

 

代码中的测试用例,请看下面的文件:

6
9876543 0.0001
33 0.001
999 0.0001
777 0.00001
8888 0.001
1000000 0.0001

 

测试运行的结果,如下:

No.0: source=9876543, fraction=1.0E-4, result=3142.696771881704
No.1: source=33, fraction=0.001, result=5.744636535644531
No.2: source=999, fraction=1.0E-4, result=31.606961332261562
No.3: source=777, fraction=1.0E-5, result=27.874719826038927
No.4: source=8888, fraction=0.001, result=94.27618705481291
No.5: source=1000000, fraction=1.0E-4, result=999.9999999763531

 

分析与总结:

1. 整个算法实现,主要是通过递归的思路,不断折半试探,逐步逼近目标值。

2. 待求解数据,在算法实现过程中,若用float的数据类型,则会出现较大的误差,采用double的话,精度可信。

3. 0~1之间平方根的场景,只需将当前的算法做一个反向思路实现,因为0~1之间的数,平方后的数比元素数还要小。

一个求解平方根的算法题

原文:https://www.cnblogs.com/shihuc/p/9202564.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!