学步园

题意：要求实现pow(x,n)

思路：刚开始我写的程序如下：

class Solution {
public:
    double pow(double x, int n) {
        double y = 1.0;
        while(n>=0 && n--)
        {
            y *= x;
        }
        while(n<0 && n++)
        {
            y /= x;
        }
        return y;
    }
};

结果超时。

其实求幂有快速求幂的方法：

x^n = x^(n/2)*x^(n/2) (n为偶数)

x^n= x^(n/2)*x^(n/2)*x(n为奇数）

class Solution {
public:
    double pow(double x, int n) {
        double result;
        if (n == 0)
        {
            return 1.0;
        }     
        result = pow(x, n/2);
        if (n%2 == 0)
        {
            return result*result;
        }        
        else 
        {
            if (n>0)
             return result*result*x;
            else
             return result*result*1.0/x;
        }    
    }
};