劍指offer編程題Java實現——面試題11數值的整數次方

題目：

實現函數double power(double base,int exponent),求base的exponent次方。不得使用庫函數，同時不需要考慮大數問題。

解題思路：最一般的方法實現數值的n次方就是將一個數自身連乘n次
底數要考慮到正數、負數和零的情況
指數要考慮到正整數，負整數和零的情況。可能的情況有九種，其中尤其要注意底數為0，指數為負數的情況下是無意義的，因此要做特殊處理
指數為負數的乘方運算，可先按照指數為正求得，然後求倒數得到真正結果
解法一：全面不高效，考慮到所有邊界條件和負面測試使用循環計算乘方
解法二：全面高效完美的算法，使用公式，利用遞歸實現，減少計算次數

a^n=a^(n/2)*a^(n/2) 　　　n是偶數

a^n=a^(n/2)*a^(n/2)&a 　　n是奇數

 1 package Solution;
 2 /**
 3  * 劍指offer面試題11：數值的整數次方
 4  * 題目：實現函數double power(double base,int exponent),求base的exponent次方。
 5  * 不得使用庫函數，同時不需要考慮大數問題。
 6  * 解題思路：實現數值的n次方就是將一個數自身連乘n次
 7  * 底數要考慮到正數、負數和零的情況
 8  * 指數要考慮到正整數，負整數和零的情況。因此可能的情況有九種，其中尤其要注意底數為0，指數為負數的情況下是無意義的，因此要做特殊處理
 9  * 指數為負數的乘方運算，可先按照指數為正求得，然後求倒數得到真正結果
10  * 解法一：全面不高效，考慮到所有邊界條件和負面測試
11  * 解法二：全面高效完美的算法，使用公式a^n=a^(n/2)*a^(n/2)    n是偶數
12  *                                   a^(n/2)*a^(n/2)&a    n是奇數    
13  * @author GL
14  *
15  */
16 public class No11Power {
17 
18     public static void main(String[] args) {
19         System.out.println("底數為2，指數為2運算結果為："+power(2,2));
20         System.out.println("底數為2，指數為-2運算結果為："+power(2,-2));
21         System.out.println("底數為2，指數為0運算結果為："+power(2,0));
22         System.out.println("底數為-2，指數為2運算結果為："+power(-2,2));
23         System.out.println("底數為-2，指數為-2運算結果為："+power(-2,-2));
24         System.out.println("底數為-2，指數為0運算結果為："+power(-2,0));
25         System.out.println("底數為0，指數為2運算結果為："+power(0,2));
26         System.out.println("底數為0，指數為0運算結果為："+power(0,0));
27         System.out.println("底數為2，指數為1運算結果為："+power(2,1));
28         System.out.println("底數為0，指數為-2運算結果為："+power(0,-2));
29     }
30 
31     public static double power(double base,int exponent){
32         if(equal(base,0.0)&&exponent<0)
33             throw new RuntimeException("while exponent is minus,the base can't be zero");
34         int absExponent=exponent;
35         if(exponent<0)
36             absExponent=~exponent+1;//整數按位取反+1得到他的相反數
37         //double result=powerWithUnsignedExponent(base,absExponent);
38         double result= powerWithUnsignedExponentByRecursion( base, absExponent);
39         if(exponent<0)
40             result=1.0/result;
41         return result;
42     }
43     //解法一：求指數為非負數時候的乘方運算,連乘
44     private static double powerWithUnsignedExponent(double base, int absExponent) {
45         double result=1.0;
46         for(int i=1;i<=absExponent;i++){
47             result=result*base;
48         }
49         return result;
50     }
51 
52     //解法二：計算一個數的乘方的時候，通過計算指數的一半次，得到的結果相乘即可得到，這樣計算量會大大減少
53     private static double powerWithUnsignedExponentByRecursion(double base,int exponent){
54         if(exponent==0)
55             return 1.0;
56         if(exponent==1)
57             return base;
58         double result= powerWithUnsignedExponentByRecursion(base,exponent>>1);
59         result=result*result;
60         if((exponent&0x1)==1)
61             result=result*base;
62         return result;
63     }
64     
65 
66     //浮點數由於精度問題不能用==判斷是否想等，如果兩數滿足一定條件精度，可以看做相等
67     private static boolean equal(double number1,double number2){
68         if(number1-number2>-0.0000001&&(number1-number2)<0.0000001)
69             return true;
70         return false;
71     }
72 }