Re: [問題] a的b次方實作時間logb之遞迴寫法

看板C_and_CPP作者 (小Ben)時間15年前 (2010/03/24 15:43), 編輯推噓2(205)
留言7則, 5人參與, 最新討論串3/6 (看更多)
原理其實差不多,而且我也沒有寫得挺漂亮 int power (int x, int y) { if (y == 1) return x; if (y == 2) return (x * x); int k = power (x, y / 2); return (y % 2) ? (k * k * x) : (k * k); } ※ 引述《conan77420 (人生就是不停的戰鬥)》之銘言: : a的b次方計算時間在logb內完成 : 這題好像之前有在板上看過,但好像沒有遞迴版的 : 非遞迴的寫法我自己寫的如下: : #include<iostream.h> : using namespace std; : int fastpow(int ,int ); : int main() : { : int num=0, pow=0; : cout<<"Enter num:"; : cin>>num; : cout<<"Enter pow:"; : cin>>pow; : cout<<fastpow(num,pow); : system("pause"); : } : int fastpow(int a,int b) : { : int temp=1; : while(b!=0) : { : if(b&1) : {temp=temp*a;} : a=a*a; : b=b>>1; : } : return temp; : } : ================================= : 造裡說非遞迴出的來〝遞迴〞應該就出的來 : 無奈可能非遞迴沒寫得很好,遞迴我實在想不出來要怎麼寫才漂亮 : 請教大家 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.227.132

03/24 23:43, , 1F
沒想到樓上有人早先一步了
03/24 23:43, 1F

03/24 23:52, , 2F
我偷懶只寫示意, 沒處理細節 XD 你比較勤勞
03/24 23:52, 2F

03/24 23:59, , 3F
return statement 的 (?:) operator 有筆誤
03/24 23:59, 3F

03/25 00:08, , 4F
已修正, 謝謝眼睛很尖的樓上
03/25 00:08, 4F
※ 編輯: Benedy 來自: 220.136.227.132 (03/25 00:09)

03/25 10:07, , 5F
sqrt() 應該會比 pow(,0.5) 快?
03/25 10:07, 5F

03/25 10:08, , 6F
眼殘...我還是去讀書好了...Orz
03/25 10:08, 6F

03/25 12:05, , 7F
y == 0 會 k*k 無限循環到 stack overflow
03/25 12:05, 7F
文章代碼(AID): #1BgZCHJU (C_and_CPP)
討論串 (同標題文章)
文章代碼(AID): #1BgZCHJU (C_and_CPP)