C++倍增的思想求a^n
2012-08-27 15:13:16 来源:WEB开发网核心提示: 用最直观的方法n个a相乘是很慢的,这种实现需要执行n次,C++倍增的思想求a^n,而如果用倍增的思想,则可以在logN复杂度中求得结果,具体的思路参见附件中的ppt,我这里就直接贴代码了
用最直观的方法n个a相乘是很慢的,这种实现需要执行n次,而如果用倍增的思想,则可以在logN复杂度中求得结果。
具体的思路参见附件中的ppt,我这里就直接贴代码了。
#include<stdio.h>
int solve(int a,int n){//这个程序用来求a^n
int ans,tmp,flag;
if(a==0)return 0;
ans=1;tmp=a;
while(n){
flag=n&1;
if(flag==1){
ans*=tmp;
}
n=n>>1;
tmp*=tmp;
}
return ans;
}
int main(){
printf("%d",solve(2,10));
//output: 1024
return 0;
}
更多精彩
赞助商链接