LeetCode刷题记录：Power（x,n）

这题用到的是递归分支的思想：

先来演算一下计算的过程：
假设 n = 32: x → x 2 → x 4 → x 8 → x 16 → x 32 quad x rightarrow x^2 rightarrow x^4 rightarrow x^8 rightarrow x^{16} rightarrow x^{32} x→x2→x4→x8→x16→x32
但是如果 n 为奇数怎么办？ 我们倒着来分析：
假如 n = 33： x 33 → x 16 x → x 8 → x 4 → x 2 → x quad x^{33}rightarrow x^{16}x rightarrow x^8 rightarrow x^4 rightarrow x^2 rightarrow x x33→x16x→x8→x4→x2→x
发现中间出现了一次： x 16 x x^{16}x x16x，这是为了方便继续向下分治

接下来我们将以上步骤模型化：
若求： x n x^n xn，我么将其分为： y = x ⌊ n 2 ⌋ y = x^{lfloor frac{n}{2} rfloor} y=x⌊2n​⌋
若n为偶数，那么 x n = y 2 x^n = y^2 xn=y2，若n为奇数，那么， x n = y 2 x x^n = y^2x xn=y2x
然后继续对： x ⌊ n 2 ⌋ x^{lfloor frac{n}{2} rfloor} x⌊2n​⌋进行分治
最后递归的终止条件为： n = = 0 n==0 n==0

java代码：

class Solution {
    public double myPow(double x, int n) {
        return n > 0 ? function(x,n) : 1.0 / function(x,-n);
    }
    public double function(double x,int n){
        if(n == 0) return 1;
        double y = function(x, n / 2);
        return n % 2 == 0 ? y * y : y * y * x;
    }
}

C++代码：

#include
using namespace std;
int fun(double x, int n){
    if(n == 0) return 1;
    int y = fun(x, n/2);
    return n % 2 == 0 ? y * y : y * y * x;
}
int powerFun(double x, int n){
    return n > 0 ? fun(x, n) : 1.0 / fun(x, -n); 
}
int main(){
    double x;
    cout<<"Enter x : ";cin>>x;
    int n;
    cout<<"Enter n : ";cin>>n;
    cout<<"Result : "< 
 
 
记录下来，方便复习，如果对你也有帮助，记得点赞哦！！！