leetcode

题目链接
Description
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
Explanation: 2-2 = 1/22 = 1/4 = 0.25

解题思路
求幂运算，利用二分法降低复杂度。对奇数幂=偶数幂*x，对负数幂=1.0/正数幂。对偶数幂，递推进行平方运算。

示例代码

double myPowx(double x, int n)
{
    double res = 1;
    if (n == 0)
        return 1;
    if (n % 2 == 0)
    {
        double tmp = myPowx(x, n / 2);
        res = tmp * tmp;
    }
    else
    {
        double tmp = myPowx(x, n / 2);
        res = tmp * tmp*x;
    }
    return res;
}
double myPow(double x, int n) {
    if (n >= 0)
        return myPowx(x, n);
    else
        return 1.0 / myPowx(x, n);
}