数据结构与算法解析习题2.16：不用递归，写出快速求幂的程序

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

#include <stdio.h>
#include <math.h>

#define MAXN 1000

int PowersOfXO[MAXN];

int main() {

    int x, n, cnt, i;
    int ans = 1;
    scanf("%d %d", &x, &n);
    cnt = (int)log2(n);
    PowersOfXO[0] = x;
    for (i = 1; i <= cnt; i++)
    {
        PowersOfXO[i] = PowersOfXO[i - 1] * PowersOfXO[i - 1];
    }
    i = 0;
    while (n > 0) {//将n转换为2进制，如果为1乘
        if (n % 2 == 1)
            ans *= PowersOfXO[i];
        i++;
        n /= 2;
    }
    printf("%d", ans);
}