不使用已有函数求出一个数的平方根

      前一段时间领导出了一道算法题（找出一个数的平方根，精确到小数点后两位，不使用函数库），对此一直耿耿于怀，始终觉得自己的答案是有问题的，但是暂时没有想到其他好的办法。

      我是先求出最接近这个数的一个能够整除的平方根，比如说1的平方根是1，2的最接近的平方根也是1，3的最接近平方根也是1，而5的最接近的平方跟是2，那么以2为基数，每次叠加0.01，加入说root是平方根，那么找出root 乘以root，然后乘积比该数大0.001的数。具体算法见以下代码：

import java.math.BigDecimal;
import java.math.RoundingMode;

/**
 * 找出一个数的平方根，精确到小数点后两位，不使用函数库.
 * 
 * @author qinge
 *
 */
public class Square {

	public static void main(String[] args) {
		for (int num = 1; num <= 1000; num++) {
			System.out.print(num + "的函数平方根：" + Math.sqrt(num));
			double root = findSmallRoot(num);
			System.out.print(" 小数点前一位是：" + root);
			while (true) {
				double product = root * root;
				if (product == num) {
					System.out.print(" 计算得出平方根是：" + root + "\n");
					break;
				} else if (product > num) {// 此处算法有遗漏
					if (product - num > 0.001) {
						System.out.print(" 计算得出平方根是：" + root + "\n");
						break;
					}
				}

				// 用加0.01进行控制
				root = root + 0.01;
				// 对double类型进行精度控制
				root = BigDecimal.valueOf(root).setScale(2, RoundingMode.HALF_UP).doubleValue();
			}
		}
	}

	/**
	 * 找出num的平方根的小数点前面的数字
	 * 
	 * @param num
	 * @return
	 */
	public static int findSmallRoot(int num) {
		// 遍历平方根的基数，基数的乘机必然会小于等于num
		for (int i = 1; i <= num && i * i <= num; i++) {
			// 找出基数则返回
			if (i * i == num) {
				return i;
			}
		}
		// 找num-1
		return findSmallRoot(num - 1);
	}
}

 相信一些大牛们一定有自己更神奇的算法，那么就贴出来吧！学习膜拜中...

评论

6 楼 thihy 2015-06-14  

qing_gee 写道

thihy 写道

1. 二分！
2. 级数展开！
3. 迭代的方法：如牛顿下山法：http://blog.csdn.net/free4294/article/details/6929950

看了牛顿迭代法，还没想清楚为什么。

可以看牛顿下山法的图示，与0.001的累加效果差不多，但是牛顿的方法更加快，一般几个迭代就O了。

5 楼 a942010 2014-08-04  

import java.util.Scanner;

public class PingFangGen {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		double i = scanner.nextDouble();
		for (double j = 0; j < 100;) {
			j += 0.001;
			if (j * j <= i && j * j >= i - 0.01) {
				System.out.println(j);
				break;
			}
		}
	}
}

还可以这样

4 楼 a942010 2014-08-04  

import java.util.Scanner;


public class PingFangGen {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
double i = scanner.nextDouble();
for (int j = 0; j < 1; ) {
double d = Math.random()*10;
if(d*d<=i&&d*d>=i-0.01){
System.out.println(d);
break;
}
}
}
}



可以这样吗？

3 楼 lasaka 2014-08-04  

package acer;

import java.io.IOException;
import java.util.Scanner;

public class Test {

	public static void main(String aa[]) throws IOException {
		double inputNumber = 0;
		int sqare = 0;
		double sqresult = 0;
		double closeNumber = 0;
		double closeNumberMinusOne = 0;
		double lastCloseNumber = 0;
		boolean check = true;
		boolean first = true;

		Scanner scanner = new Scanner(System.in);
		inputNumber = scanner.nextDouble();//數字
		sqare = scanner.nextInt();//平方數

		for (int i = 1; i < inputNumber + 1; i++) {
			sqresult = i;
			for (int j = 1; j < sqare; j++) {
				sqresult *= i;
			}
			if (sqresult >= inputNumber) {
				closeNumber = i;
				closeNumberMinusOne = closeNumber - 1.0;
				break;
			}
		}

		while (check) {
			if (sqresult == inputNumber) {
				check = false;
				sqresult = sqare(sqare, closeNumber);
			} else {
				// 表示超過小數點第16位了
				if (closeNumberMinusOne != 0
						&& lastCloseNumber == closeNumberMinusOne) {
					check = false;
				}
				if (first) {
					first = false;
					lastCloseNumber = closeNumberMinusOne;
					closeNumberMinusOne += (closeNumber - closeNumberMinusOne) / 2;
				} else {
					closeNumber = closeNumberMinusOne;
					if (sqresult > inputNumber) {
						if (lastCloseNumber > closeNumberMinusOne) {
							closeNumberMinusOne -= (lastCloseNumber - closeNumberMinusOne) / 2;
						} else {
							closeNumberMinusOne -= (closeNumberMinusOne - lastCloseNumber) / 2;
						}
					} else {
						if (lastCloseNumber > closeNumberMinusOne) {
							closeNumberMinusOne += (lastCloseNumber - closeNumberMinusOne) / 2;
						} else {
							closeNumberMinusOne += (closeNumberMinusOne - lastCloseNumber) / 2;
						}
					}
					lastCloseNumber = closeNumber;
				}
				sqresult = sqare(sqare, closeNumberMinusOne);
			}
		}
	}

	public static double sqare(int sqare, double result) {
		double sqresult = result;
		for (int j = 1; j < sqare; j++) {
			sqresult *= result;
		}
		System.err.println("次方根: " + result);
		System.err.println("次方結果: " + sqresult);
		return sqresult;
	}
}

2 楼 qing_gee 2014-08-04  

thihy 写道

1. 二分！
2. 级数展开！
3. 迭代的方法：如牛顿下山法：http://blog.csdn.net/free4294/article/details/6929950

看了牛顿迭代法，还没想清楚为什么。

1 楼 thihy 2014-08-03  

1. 二分！
2. 级数展开！
3. 迭代的方法：如牛顿下山法：http://blog.csdn.net/free4294/article/details/6929950