→ aries198012:我走錯版了嗎@@? 怎麼這裡變成code版? 12/24 08:22
→ bleed1979:是的，你走錯了，因為台灣沒有軟體產業，請按左鍵離開。 12/24 08:41
我會這樣寫。
偽碼：
ret_value function (base, power) {
if(power == 1) {
return base;
}
temp = function (base, power >> 1);
if((power & 1) != 0) {
return temp * temp * base;
}
return temp * temp;
}
改寫自BigMod()
附帶一提，拆三等份實測不會比較快。
※ 引述《oaz (幸福治安：破案數/十萬人)》之銘言：
: 解法三確實是演算法
: 一個經典的例子是，計算 a**n (a 的 n 次方)
: 如果一般的解法
: long ans=1;
: for(int i=0; i<n; i++) {
: ans *= a;
: }
: 時間複雜度是 O(n) ，如果 b 很大（譬如考慮大數），就很久
: 假設用 3**19 來說，因為 19 的二進位制是 10011
: 3**19 = 1 * 3**1
: + 1 * 3**2 3**2 = (3**1)**2
: + 0 * 3**4 3**4 = (3**2)**2
: + 0 * 3**8 3**8 = (3**4)**2
: + 1 * 3**16 3**16 = (3**8)**2
: 比較快的演算法為：
: long ans=1;
: long base=a;
: for(; n>0; n/=2) {
: if(n%2==1) {
: ans*=base;
: }
: base=base*base;
: }
: 時間複雜度是 O(log n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
※ 編輯: bleed1979 來自: 114.32.177.97 (12/23 09:18)