题目：
Implement pow(x, n), which calculates x raised to the power n (xn).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Note:
- -100.0 < x < 100.0
- n is a 32-bit signed integer, within the range [−231, 231 − 1]
思路：
这道题可以采用二分法来做。首先观察n。
- 如果n%2为0，返回x/2 * x/2。
- 如果n%2为1，返回x/2 * x/2 * x。
- 如果n为0，则返回1。因为任何数除了0之外的0次方全为1.
举例：
57按照以上原则分解
53 * 53 * 5
51 * 51 * 5 * 51 * 51 * 5 *5
50 * 50 * 5 * 50 * 50 * 5 * 5 * 50 * 50 * 5 * 50 * 50 * 5 * 5 * 5 = 57
注意：
如果n为负数，首先按照n的绝对值计算xn再用1除以xn，即最终结果。
代码：
/**
* Calculating pow(x, n).
* @param x
* @param n
* @return
*/
public double myPow(double x, int n) {
if(x == 0){
return 0.0;
}
if(n > 0){
return Pow(x, n);
}else{
return 1 / Pow(x, -n);
}
}
private double Pow(double x, int n){
if(n == 0)
return 1;
double mid = Pow(x, n/2);
if(n%2 == 0){
return mid * mid;
}else{
return mid * mid * x;
}
}
