实现函数double Power(double base, int exponent)，求base的 exponent次方。

不得使用库函数，同时不需要考虑大数问题。

只要输出结果与答案的绝对误差不超过$10^{-2}$ 即视为正确。

注意：

  • 不会出现底数和指数同为0的情况
  • 当底数为0时，指数一定为正

样例1

1
2
3

输入：10 ，2

输出：100

样例2

1
2
3

输入：10 ，-2  

输出：0.01

解题思路

$$ 4^2 = 44 = 2^2 * 2^2 \ 6^7 = 6^{1+6} = 6 6^6\

x^{y} = xxx…*x \hspace{1em} {y个 x相乘} \

我们令 f(x,y) = x^y 则推导出:\

f(x,y) = x*f(x,y-1)\

也就是说，我们可以对 f(x,y)进行分组:\ 例如: f(2,1) = 2\ f(2,2) = 2f(2,1)\ f(2,3) = 2f(2,2)\ 这样进行逆推:\ f(x,y) = 1/{f(x,-y)}

$$

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    double Power(double base, int exponent) {
        if(exponent == 0) return 1;
        if(exponent == 1) return base;
        
        
        // if(exponent<0) 
        // {
        //     return 1/Power(base,-exponent);
        // }
        double res = 1;
        #define ll long long
        for(ll k = abs((ll)exponent);k;k>>=1) {
            if(k & 1) res *= base;
            base *= base;
        }
        if(exponent < 0) return 1/res;
        return res;
        
        
        
    }
};