计算2的n次方程序设计思路（利用二分思维实现一个数的整数次方计算）

通常，计算一个数的整数次方的简单粗暴的方法是用一个循环，其时间复杂度为long(n);，下面我们就来聊聊关于计算2的n次方程序设计思路?接下来我们就一起去了解一下吧!

计算2的n次方程序设计思路

通常，计算一个数的整数次方的简单粗暴的方法是用一个循环，其时间复杂度为long(n);

double pow(double x, int n) // 这里没有考虑n为负数的情况 { double ret = 1.0; for(int i=1;i<=n;i ) ret *= x; return ret; }

简单直接粗暴的思路往往不是最佳解法，如我们计算，不会机械地计算= 2*2*2*2*2*2*2*2*2*2 = 1024

化简为=4*8*=32*32=1024

来计算就要简单些。

对于,其中的n可以可以表示为序列：的某个组合之和，也就是：

… (b==0 || b==1)

(b==0 || b==1)

关于指数n的迭代关系，有点像10进制求二进制，如将一个十进制数打印出二进制位：

void intPrintBinary(int n) { if(n<=0) return; if(n!=0) { intPrintBinary(n/2); printf("%d",n%2); } }

计算一个数的整数次方，，有如下伪代码：

double ret = 1; while(n>0{ if(n%2 == 1) // 相当于上述表达式中 (b==0 || b==1) ret *= x; // 连乘 n /=2； // 指数连续二分迭代 x *=2; // 相当于上述表达式中 x^2^i }

伪代码转换为代码：

#include <stdio.h> double pow(double x,int n) { double ret = 1.0; while(n>0) { if(n%2==1) // 相当于上述分析中的 (b==0 || b==1) ret *= x; // 当b==1时，项的值迭代到结果中 x *= x; // 相当于上述分析中 x^2^i n /= 2; // 对应x^2^i，x以自身倍数迭代增长，n以二分自己减小 } return ret; } int main() { for(int i=1;i<100;i ) printf(".2f\n",pow(i i*.1,3)); getchar(); }

能以二分方法解决的问题的时间复杂度为O(long2n)，如上例，问题的边界为(0,n)，以n /= 2来迭代n，直到n==0，迭代的次数为log2n。

-End-