湖南省第八届大学生程序设计大赛原题 D - 平方根大搜索 UVA 12505 - Searching in sqrt(n)

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=30746#problem/D

D - 平方根大搜索

UVA12505 - Searching in sqrt(n)

解题思路：求出n的平方根，去整数，化二进制，字符串子串查找。

基本思路简单，但是求平方根那里，不能直接用库函数方法，因为Math.sqrt()返回值的精度比较小。我们这里要用到的精度最高是140位。所以，求平方根的函数（中心代码转自http://blog.****.net/nujiah001/article/details/6657422）要自己写。不单只是自己写，由于设计的精度过高，一般的数据类型（如double）无法存储。所以必须用到JAVA中的大数类import java.math.BigDecimal;。

1545839

20114045007

D

Accepted

125440 KB

5044 ms

Java

2593 B

2013-09-09 14:35:32

import java.util.*;
import java.math.*;
public class Main{
	static String tob(BigDecimal d)  //求小数d的二进制表示，返回二进制存储串s
	{
	    String s=new String();
	    int n=150;
	    while(!d.equals(BigDecimal.ZERO)&&n--!=0)
	    {
	    	d=d.multiply(BigDecimal.valueOf(2));
	    	BigInteger x=d.toBigInteger();
	        s+=x;
	        d=d.subtract(BigDecimal.valueOf(x.longValue()));
	    }
	    return s;
	}
	public static BigDecimal culsqrt(int num)  //以下三个函数（方法）用来求num的平方根
	{

		return sqrtMathod(num);

	}

	public static BigDecimal sqrtMathod(int num)
	{
		BigDecimal sqrtNum = BigDecimal.valueOf(-1);
		boolean isFindSqrt = false;

		// get int sqrt num
		double tempSqrt = 0;
		if (num > 0)
		{
			if (num == 1)
			{
				return BigDecimal.valueOf(1);
			}
			else
			{
				for (int j = 0; j <= num / 2 + 1; j++)
				{
					if (j * j == num)
					{
						sqrtNum = BigDecimal.valueOf(j);
						isFindSqrt = true;
						break;
					}
					if (j * j > num)
					{
						tempSqrt = j - 1;
						break;
					}
				}
			}
		}

		if (!isFindSqrt)
		{
			sqrtNum = recuFindSqrt(num, BigDecimal.valueOf(tempSqrt), isFindSqrt, BigDecimal.valueOf(1));
		}

		return sqrtNum;
	}

	private static BigDecimal recuFindSqrt(int num, BigDecimal sqrtValue, boolean isFindSqrt, BigDecimal ac)
	{
		ac = ac.multiply(BigDecimal.valueOf(10));
		BigDecimal tempSqrt = BigDecimal.valueOf(0);
		for (int i = 0; i < 10; i++)
		{
			tempSqrt = sqrtValue .add(BigDecimal.valueOf(i).divide(ac) );
			if (tempSqrt .multiply(tempSqrt) .equals(BigDecimal.valueOf(num)))
			{
				isFindSqrt = true;
				sqrtValue = tempSqrt;
			}
			else if (tempSqrt .multiply(tempSqrt) .compareTo(BigDecimal.valueOf(num))==1)
			{
				tempSqrt = sqrtValue.add(BigDecimal.valueOf(i - 1) .divide( ac));
				sqrtValue = tempSqrt;
				break;
			}
		}

		BigDecimal temp = tempSqrt;
		if (temp.toString().length() <= 150 && !isFindSqrt)
		{
			sqrtValue = recuFindSqrt(num, tempSqrt, isFindSqrt, ac);
		}

		return sqrtValue;
	}

	public static double add(double v1, double v2)
	{
		BigDecimal b1 = new BigDecimal(Double.toString(v1));
		BigDecimal b2 = new BigDecimal(Double.toString(v2));
		return b1.add(b2).doubleValue();
	}

	public static void main(String[] args) {
		Scanner in= new Scanner(System.in);
		int t;
	    int n;
	    String st;
	    t=in.nextInt();
	    while(t--!=0)
	    {
	        n=in.nextInt();
	        st=in.next();
	        BigDecimal d=culsqrt(n);  //求平方根
	        BigInteger x=d.toBigInteger();
	        d=d.subtract(BigDecimal.valueOf(x.longValue()));  //分离出小数部分
	        String tobs=tob(d);  //将小数转化为二进制，存储在串tobs中
	        System.out.println(tobs.indexOf(st));  //输出查找结果
	    }
	}
}