数据结构算法之n的平方根保留m位小数

求n的平方根x,x精确到m位小数。例如求n精确到小数点后4位的平方根。

思路:

求n的平方根x,则首先想到的是可不可以从1开始,分别求1、2、3等的平方,看是否等于n。这里就有个问题我为什么首先从1开始,而且为什么各个数的步长为1?也就是说我们应该从哪里开始去试,每次去试时,各个数的步长应该怎么选?

从上面的分析中得出求n的平方根其实就是从小于n的数中找到x,使x*x等于n,这就变成了一个查找的问题,而且是在有序数据集中查找,则最容易想到的就是二分查找,则从哪里开始去试,每次去试时,各个数的步长问题就都解决了。

下面看下二分查找的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int binarySearch(int[] arr, int target){
int low = 0;
int high = arr.length-1;
while (low <= high){
int mid = (low + high) / 2;
if (target > arr[mid]){
low = mid + 1;
}else if (target < arr[mid]){
high = mid - 1;
}else {
return mid;
}
}
return -1;
}

使用二分查找找到平方根的范围然后递增步长

对于一个数的平方根能够找到该跟的范围,即xx < n < yy,则n的平方根在x和y之间,且x+1=y
找到平方根所在的区域之后,把所要保留的精度的平方根做为步长对x进行递增,直到|n-x*x|<0.0001(精度)为止。

例如求12的平方根,精度为小数点后2位。代码示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static double sqrtByInc(int n, double precision){
int low = 0;
int high = n;
int mid = (low + high) / 2;
// 二分查找找到平方根的区域
while (low <= high){
if (mid * mid > n){
high = mid - 1;
}else if (mid * mid < n){
if ((mid+1)*(mid+1) > n){
break;
}
low = mid + 1;
}else {
break;
}
mid = (low + high) / 2;
}
// 按照精度的平方根做为步长
double r = mid;
while (Math.abs(n-r*r) > 0.0001){
if (r * r < n){
r += 0.01;
r = BigDecimal.valueOf(r).setScale(2, RoundingMode.HALF_UP).doubleValue();
}else {
break;
}
}
return r;
}

改进

上面的方法只是用二分查找找到平方根的范围,然后递增步长进行尝试,虽然能够快速找到根的范围,但是递增步长将是一个漫长的等待。

|n-x*x|<0.0001(精度)可得n的平方根减去x小于0.01,n的平方根和x都是根的候选者,则只要只要两个候选者的差值小于0.01,则x就是所要求的平方根。这样就可以直接使用二分查找进行查找。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static String sqrt(int n, double precision){
double start = 0;
double end = (double) n;
double last = end;
double mid = (start + end) / 2.0;
while (Math.abs(last - mid) > precision){
if (mid * mid > n){
end = mid;
}else {
start = mid;
}
last = mid;
mid = (start + end) / 2.0;
}
DecimalFormat df = new DecimalFormat("0.00");
return df.format(mid);
}

迭代计算平方根

对于这种数学类型的问题,使用数学公式应该是最快的。求n的平方根有一个公式可以使用,叫牛顿迭代法。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
public static double SqrtByNewton(int n, double precision)
{
double val = n; //最终
double last; //保存上一个计算的值
do
{
last = val;
val =(val + n/val) / 2;
}while(Math.abs(val-last) > precision);
return val;
}
您的肯定,是我装逼的最大的动力!