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;
}
中查找“C++倍增的思想求a^n”更多相关内容
中查找“C++倍增的思想求a^n”更多相关内容更多精彩
赞助商链接
