本文共 2009 字，大约阅读时间需要 6 分钟。
| 对于任意一个数，我们都可以用类似于除法的方法计算出它的平方根，而且这个数并不一定需要是完全平方数，开不尽的数可以开到任意多位停止。 大致说来，开方分为以下几步： 首先，以小数点为界，将原数两位两位划分。如65536 分为 6 55 36，0.82432分为0. 82 43，123.456分为 1 23 .45 6。 类似于除法写在根号下(以下以65536为例） ________ /6 55 36 第一次，找到一个数，它的平方比6小，它加一的平方比6大（相当于除法中的试除），然后写法和除法类似（见下）： 2 _______ 2/6 55 36 4 _______ /2 55 接下来，把目前的结果（最上面的那个2）乘上2，写在根号左边，留出一位的位置（这里用X表示） 2 _______ 2/6 55 36 4 _______ 4X/2 55 下一步，尝试找到最大的X，使得4X*X<=255，由于45*5=225,46*6=276，于是X=5 2 5 ———————— 2/6 55 36 4 ———————— 45/2 55 2 25 ———————— / 30 36 同样，把已得的结果（25）乘上2，写在根号左边，留出一位： 2 5 ———————— 2/6 55 36 4 ———————— 45/2 55 2 25 ———————— 50X/ 30 36 找到最大的X，使得50X*X<=3036，因为506*6=3036，写6 2 5 6 ———————— 2/6 55 36 4 ———————— 45/2 55 2 25 ———————— 506/ 30 36 30 36 ———————— 0 没有余数，说明刚好开完，于是sqrt(65536)=256 以下再以2为例：写法如下，不作说明 1 4 1 4 ……………… —————————— 1/2. 1 —————————— 24/1 00 96 —————————— 281/ 4 00 2 81 —————————— 2824/ 1 19 00 1 12 96 —————————— 6 04 00 ………………于是sqrt(2)=1.414………………………… import java.math.BigInteger;import java.util.Scanner;public class Main { static void solve(BigInteger bi){ String str; str = bi.toString(); str = "0"+str; int len = str.length(); int i = len%2; BigInteger pre = new BigInteger("0"); BigInteger rmd = new BigInteger("0"); for(; i < len; i+=2){ rmd = rmd.multiply(BigInteger.valueOf(100)).add(new BigInteger(str.substring(i, i+2))); for(int j = 0; j < 10; j++){ if(rmd.compareTo(BigInteger.valueOf(20).multiply(pre).add(BigInteger.valueOf(j+1)).multiply(BigInteger.valueOf(j+1))) == -1){ rmd = rmd.subtract(BigInteger.valueOf(20).multiply(pre).add(BigInteger.valueOf(j)).multiply(BigInteger.valueOf(j))); pre = pre.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(j)); break; } } } System.out.println(pre); } public static void main(String[] args) { int T; Scanner cin = new Scanner(System.in); T = cin.nextInt(); for(int cas = 0; cas < T; cas++){ if(cas != 0) System.out.println(); solve(cin.nextBigInteger()); } }} |
转载地址：http://zdhrb.baihongyu.com/