计算x的n次方有递归和递推程序。不论从时间或空间来看，自然递推优于递归。
然而，二分法则是极其优的一种方法，用在计算x的n次方完全没有问题，而且不是递归而是递推的程序。
程序中使用条件编译，以便于统计分析算法的计算量。
正解是函数power3。
/* * * 计算x的n次方程序：1.递归程序；2.非递归程序;3.二分法。 * */#include <stdio.h>//#define DEBUG#ifdef DEBUGint c1=0, c2=0, c3=1;#endiflong power1(int, int);long power2(int, int);long power3(int, int);int main(void){ int x = 2, n = 23; printf("power1: %d %d result=%ldn", x, n, power1(x, n)); printf("power2: %d %d result=%ldn", x, n, power2(x, n)); printf("power3: %d %d result=%ldn", x, n, power3(x, n));#ifdef DEBUG printf("c1=%d c2=%d c3=%dn", c1, c2, c3);#endif return 0;}long power1(int x, int n){#ifdef DEBUG c1++;#endif return (n==1)?x:x * power1(x, n-1);}long power2(int x, int n){ int i; long result = 1; for(i=1; i<=n; i++) {#ifdef DEBUG c2++;#endif result *= x; } return result;}long power3(int x, int n){ long res = 1L; while(n) {#ifdef DEBUG c3++;#endif if(n & 1L) res *= x; x *= x; n >>= 1; } return res;}
转载于:https://www.cnblogs.com/tigerisland/p/7564962.html