计算2的n次方程序设计思路?通常,计算一个数的整数次方的简单粗暴的方法是用一个循环,其时间复杂度为long(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-
,