Re: [中學] 能證明所有次方最快的算法是D&C嗎?
※ 引述《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能否證明是所有次方的最快的計算方法呢？
要說最快真的很有DP的味道
因為我們做一次乘法或除法為兩個數
得到的第三個數的次方也和前兩個不同
可以看作一個湊數字的遊戲
一次只能拿兩個數相加或相減
數字可以重複但要湊出來才可以用
得到數字後不可以再湊一樣的數字
求湊到某個數字動作次數最少
一開始只有 1
要有2只能拿兩個1湊
要有3則是先湊2
再拿1和2湊
7比較有趣
則是先湊2
再拿兩個2湊4
4和2湊6
6和1湊出7
或是4和4湊8
8和1互剪湊7
看到這邊大概知道遊戲怎麼玩了
所以說策略是
你要計算某數
就要拿那個數去拆解成兩個數相加或相減
再拿這兩個數分別遞迴做一樣的事情
相減我還不確定有什麼剪枝的方法
相加則很簡單
比方9為例子
要湊九一開始就有4種方式
1 8
2 7
3 6
4 5
接著再遞迴砍枝
要快就是用DP反轉
用貪婪記住每次最佳解
把加解釋成步數
2就是 拆解成1加1 等於0步+0步+本身1步為1
3就是 拆成1加2等於0步+1步+本身的1步為2
4就是 1+3為0+1+2=3或是2+2為 1+0(二被算出來記在表裡不用再算)+本身的1=2
取最佳則為2
5就是1+4為0+2+1=3步
或2+3為1步加2步加本身1步=4步
取最佳則為3
以此類推
可以做另一個表格把最佳路徑走法記下來
實作真的次方乘法就很簡單啦
減法的比較複雜要想一下
就交給其他厲害的人啦
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.67.187
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1492293440.A.351.html
※ 編輯: stu51211 (123.194.67.187), 04/16/2017 06:41:45
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：