Re: [問題] a的b次方實作時間logb之遞迴寫法
※ 引述《conan77420 (人生就是不停的戰鬥)》之銘言：
: a的b次方計算時間在logb內完成
//break;
: 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;
: }
: =================================
: 造裡說非遞迴出的來〝遞迴〞應該就出的來
: 無奈可能非遞迴沒寫得很好，遞迴我實在想不出來要怎麼寫才漂亮
: 請教大家
a^b 可以換成 a^(b/2 + (b-b/2)) 變成 a^(b/2) * a^(b-b/2).
而任何 n^k 的底數是 n^0 = 1 或 n^1 = n.
遞迴程式是:
double power(double a, int b) {
if (b <= 0)
return 1;
if (b == 1)
return a;
return power(a, b/2) * power(a, b-b/2);
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.16.135
→
03/25 09:31, , 1F
03/25 09:31, 1F
→
03/25 09:42, , 2F
03/25 09:42, 2F
→
03/25 10:01, , 3F
03/25 10:01, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 6 篇)：