WEB开发网      濠电娀娼ч崐濠氬疾椤愶附鍋熸い鏍ㄧ〒闂勫嫰鏌﹀Ο渚Ц闁诲氦顕ч湁婵犲﹤楠告禍鍓х磼鏉堛劌绗氶柟宄版嚇閹晠宕归銈嗘濠电偞鍨堕幐鎾磻閹捐秮褰掓偐閻戞﹩妫勯梺鎼炲妼鐎涒晝绮嬪澶樻晝闁挎繂鏌婇敃鍌涚厵閻庢稒锚閻忥絾绻濇繝鍐ㄧ伌闁诡垰鍟村畷鐔碱敂閸♀晙绱樺┑鐐差嚟婵儳螞閸曨剚鍙忛柍鍝勬噹缁€澶嬬箾閹存繄锛嶆鐐灲閹綊宕惰濡插鏌涢妸銉ヮ劉缂佸倸绉归弫鎾绘晸閿燂拷 ---闂備焦瀵уú鈺呭箯閿燂拷
开发学院软件开发C++ C++倍增的思想求a^n 阅读

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;
}

Tags:倍增 思想

编辑录入:爽爽 [复制链接] [打 印]
    赞助商链接