JAVA应试技巧----大数开方

大数开方--牛顿迭代法：

如果一个数的位数为偶数个，那么这个数开方之后就有n/2位；

如果一个数的位数为奇数个，那么这个数开方之后就有n/2+1位；

我们以num=1000为例，位数为4，偶数，那么开方之后就有2位。我们从高位开始枚举。

首先枚举十位：

10*10=100 < 1000

20*20=400 < 1000

30*30=900 < 1000

40*40=1600 > 1000

则十位数字为3

枚举各位：

31*31=961 < 1000

32*32 =1024 > 1000

则个位数字为1

所以开方1000的结果为31。

下面的代码思路和上面的例子基本一样，稍加理解即可。其中要注意变量类型的选择和转换。

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static String n;
    public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.next();
		int length= n.length();
		int sqrtLen = 0;
		if (length % 2 == 0) {
			sqrtLen = length / 2;
		} else {
			sqrtLen = length / 2 + 1;
		}
		char[] ch = new char[sqrtLen];
		Arrays.fill(ch, '0');
		BigInteger beSqrtNum = new BigInteger(n);
		for (int i = 0; i < sqrtLen; i++) {
			for (char j = '1'; j <= '9'; j++) {
				ch[i] = j;
				String s = String.valueOf(ch);
				BigInteger sqrtNum = new BigInteger(s);
				BigInteger squareNum = sqrtNum.multiply(sqrtNum);
				if (squareNum.compareTo(beSqrtNum) == 1) {
					ch[i] -= 1;
					break;
				}
			}
		}
		System.out.println(String.valueOf(ch));
	}
}