→ suhorng : 是不是有哪題 UVa 的題目是這題 (思) 09/27 17:10
推 bjiyxo : 應該可以允許除法，只是演算法可能就沒這麼簡單了 09/27 19:18
推 t0444564 : 改成2進位制 09/28 14:06
※ 引述《bjiyxo (若自礌)》之銘言：
: 如題，能否證明次方最快的算法是Divide & Conquer嗎?
: 由於我沒有學過演算法，可能這個對大家很簡單QQ
: 而D&C這個演算法是這樣的
: 如果我要算a^7
: 而直接拿a乘上7次，對於指數如果是很大的數字會非常慢
: 但是如果我將他分解
: 分解成a^3*a^3*a
: 先將7/2等於3餘1，將a^7divide成a^3再計算
: 如此兩兩分對的結果就會讓結果只要乘4次就好
: 而如果遇到大一點的指數，則會不斷的兩兩分對計算
: 那麼最後請問這個D&C能否證明是所有次方的最快的計算方法呢？
可以允許除法嗎?
如 a^63 可以a的平方再平方再平方... 到a^64, 再除以a
這樣只要7次
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.72.177.253
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1411806733.A.10F.html