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之间的数，平方后的数比元素数还要小。
2018-06-21：
PS： 针对上述分析与总结中的第3点，这里补充上算法的修正结果，即将待求解值在0-1之间的数字的平方根求解算法也支持的问题，在这里做一下兼容处理，即上述的算法做如下的调整，即可实现【0，N】其中N大于1的任何数的平方根的求解。主要是将上述java代码中的main函数做了一点点调整，区分source值是大于1还是在0-1之间的。
为何要这么分段呢？
1. 小于1的数a求平方后比原始数a小，例如0.8的平方是0.64
2. 逼近逻辑中，平方根x一定总是在原始待求解数a的右边，即x > a, 且又满足 x < 1
下面看更新后的main区域的代码：
public static void main(String[] args) { Scanner scan = null; try { scan = new Scanner(new File("./src/pingFangGeng/inputFree.txt")); int count = scan.nextInt(); for(int i = 0; i < count; i++){ double source = scan.nextDouble(); double fraction = scan.nextDouble(); double res = 0; if(source <= 1) { res = binDivFind(source, 1, source, fraction*fraction); }else{ 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(); } } }
大家感兴趣的，可以试试，效果还是不错的。 当然了，本算法中，用的是二分法，性能相对牛顿法差点，下次专门写一个用牛顿法实现求平方根的算法。