【算法初学】之 使用分治+递归思想 求x的n次幂

比如求2的3次幂可以分解为3个2相乘 2*2*2，x=2的n=5次幂就是2*2*2*2*2 == (2*2)*2*(2*2) == 4*2*4
倒过来就是 4*2*4 -> 2*2*2*2*2  也就是
n 是偶数的时候 result = mi(x, n/2) *  mi(x, n/2);
n 是奇数的时候 result = mi(x, (n+1)/2) *  mi(x, (n-1)/2);

递归到什么时候为止呢？ 分解到不能再分解位置也就是n 个x的1次幂相乘。即分解到mi(x,1)为止。

代码如下：

#include <stdio.h>


long mi(long x, int n){
    long result;
    if(n==1){
        return x;
    }
    if( n%2 == 0 ){
        result = mi(x,n/2) * mi(x,n/2);
    }
    else{
        result = mi(x,(n+1)/2) * mi(x,(n-1)/2);
    }
    return result;
}

void main (void)
{
    int x=2;
    int n = 30;

    printf(" %d 的 %d 次幂 = %d\n",x,n,mi(2,30));
    return ;
}