[理工] 105清大演算法

看板Grad-ProbAsk作者時間6年前 (2019/02/04 17:43), 6年前編輯推噓1(1推 0噓 7→)
留言8則, 3人參與, 6年前最新討論串2/2 (看更多)
https://i.imgur.com/qVSPzoF.jpg
https://i.imgur.com/koRA6OH.jpg
這題大概了解是怎麼切割的 不過有些地方一直卡住 想問的是 花O(n)merge成的u1v2+u2v1是最後的uv相乘的結果嗎 還是(u1+u2)(v1+v2)這個才是 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.246.224.19 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549273386.A.B01.html ※ 編輯: AAQ8 (27.246.224.19), 02/04/2019 17:43:44
推
02/04 17:46, 6年前 , 1F
從中間切 之所以可以直接算u1v2+u2v1是因為權重相同可以加
02/04 17:46, 1F
→
02/04 17:46, 6年前 , 2F
起來再位移
02/04 17:46, 2F
→
02/04 18:39, 6年前 , 3F
那最後應該是要把u1v1,u2v2,u1v2+u2v1這三個merge起來才是uv
02/04 18:39, 3F
→
02/04 18:39, 6年前 , 4F
相乘的結果吧
02/04 18:39, 4F
→
02/04 18:40, 6年前 , 5F
還是我哪裡想錯了QQ
02/04 18:40, 5F
→
02/04 20:15, 6年前 , 6F
假設u=u1×10^n+u2, v=v1×10^n+v2, uv即u1×v1×10^2n+(u1+
02/04 20:15, 6F
→
02/04 20:15, 6年前 , 7F
u2)(v1+v2)×10^n+u2×v2 這東西其實叫Karatsuba
02/04 20:15, 7F
→
02/04 20:16, 6年前 , 8F
正確性其實大概證一下就知道了 其他有興趣可以去google看看
02/04 20:16, 8F
‣ 更多 AAQ8 的文章
文章代碼(AID): #1SM0agi1 (Grad-ProbAsk)
‣ 更多 AAQ8 的文章
文章代碼(AID): #1SM0agi1 (Grad-ProbAsk)