略
题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
分析
自以为题目简单的解法
看到这题一般人心中窃喜，如此之简单，用一个循环来控制n次方，那就可以了。代码可以为：
1
2
3
4
5
6
7
| public class Solution {
public double Power(double base, int exponent) {
double result = 1.0;
for(int i = 1; i<=exponet;++i) result *= base;
return result;
}
}
|
但是，这一题并不对，因为，代码并不具有完整性，如果exponent是小于1（即是0或者负数时），本程序就实现不了了。
全面但不够高效的算法
对于本题，要考虑一下当exponent参数为0时的情况。例如3的0次幂为1，但0的0次幂在数学上是无意义的，所以要报出异常。也要考虑exponent参数小于0的情况，例如3的-1次幂为三分之一，0的-1次幂也应该报出异常。总结为，如果exponent<0且base不为0，先求exponent的绝对值，然后按照正数来计算，最后结果求倒数即可。
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 class Solution {
public double Power(double base, int exponent) {
if(equal(base,0.0) && exponent < 0){
throw new RuntimeException("分母不能为0");
}
int absExponent = exponent;
if(absExponent < 0)
absExponent = -exponent;
double result = 1.0;
for(int i = 1;i<=absExponent;++i)
result *= base;
if(exponent<0)
result = 1.0/result;
return result;
}
static private boolean equal(double num1,double num2){
if((num1-num2>-0.0000001) && (num1-num2<0.0000001))
return true;
else
return false;
}
}
|
全面且高效的算法
上个算法中，计算结果result值时，是使用了用循环去实现累乘来实现的，但是我们知道对于一个数的多少次幂，如果是偶数次幂，例如32次幂，那么它等于两个16次幂相乘，16次幂等于两个8次幂相乘，8次幂等于两个4次幂相乘，4次幂等于两个2次幂相乘，2次幂等于两个底数相乘。如果是奇数次幂，例如13次幂，它等于两个6次幂相乘再乘以底数，6次幂等于两个3次幂相乘，3次幂等于两个底数相乘然后再乘以底数。
一个数的n次幂，如果n为偶数，它等于两个这个数的n/2次幂相乘；如果n为奇数，它等于两个这个数的（n-1）/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
31
32
33
34
35
36
37
38
39
40
41
| public class Solution {
public double Power(double base, int exponent) {
if(equal(base,0.0) && exponent < 0){
throw new RuntimeException("分母不能为0");
}
int absExponent = exponent;
if(absExponent < 0)
absExponent = -exponent;
double result = PowerWithAbsExponent(base,absExponent);
if(exponent<0)
result = 1.0/result;
return result;
}
static private boolean equal(double num1,double num2){
if((num1-num2>-0.0000001) && (num1-num2<0.0000001))
return true;
else
return false;
}
private double PowerWithAbsExponent(double base,int exponent){
if(exponent == 0) return 1;
if(exponent == 1) return base;
double result = PowerWithAbsExponent(base,exponent>>1);
result *= result;
if((exponent & 0x1) == 1)
result *= base;
return result;
}
}
|
总结
- 对于保证代码的完整性通常要做：功能测试、边界测试、负面测试，具体如下：
- 功能测试：就是将需要的功能实现（基本功能都没有的代码是无用的）。
- 边界测试：就是要考虑各种边界条件是否正确，如果用递归，则递归的终止边界值是否正确；如果用循环，则结束循环的边界条件是否正确。
- 负面测试：就是要考虑各种错误的输入，例如账户名需要输入全是数字，当输入字符时，应该判定账户名错误。
- 三种错误的处理方式：
- 函数返回值：例如错误返回码，如果发生错误就返回相应的返回码，可以根据返回码找到错误在哪，类似于网页的404。
- 设置全局变量：例如设置布尔类型的全局变量A，当A为true则表示无错，当A为false则表示存在错误，调用者只需要判断这个变量就知道是否出错了。
- 异常处理：java中现在常用的方式，我通常用
throw new RuntimeException("这是条错误信息");来输出异常。
- float和double类型的小数判断相等时，不能用
A == B，这是因为计算机内表示小数时都是存在误差的。判断两个是否相等可以用上文的方法来指定精度。
- 位运算的效率比乘除法及求余运算的效率高很多，所以要多用位运算。