PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 大數相乘問題

看板Prob_Solve (計算數學 Problem Solving)作者 (劉大俠)時間14年前 (2011/01/07 23:25), 編輯推噓2(2推 0噓 27→)
留言29則, 3人參與, 最新討論串1/1
假設有兩組數要相乘 2 3 4 5 6 3 4 1 2 4 而又假設一次只能算4 X 4，所以我將其切成 2 | 3 4 5 6 3 | 4 1 2 4 先行計算3456 X 4124，最後再將其整合計算 所以假設 W = 34 X = 56 Y = 41 Z = 24 那麼 P = WY = 34 X 41 =1394 Q = XZ = 56 X 24 = 1344 R = (W+X)(Y+Z) = (34+56)(41+24) = (90)(65) = 5850 進行運算 P X 10^4 + (R-P-Q) X 10^2 + Q = 1394 X 10^4 + (5850-1394-1344) X 10^2 +1344 = 13940000+311200+1344 = 14252544 得到了14252544後，我要如何再傳回去跟還未計算的數字做Merge? 最終答案應該是800412544，目前小弟不太懂的就是 我要如何把目前的結果(14252544)，變成最終答案? 有請各位大大解惑，小弟感恩 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.169.77.33
→
01/07 23:50, , 1F
都說可以4x4了，為什麼還要拆開呢@@? 而既然都會拆開算了，
01/07 23:50, 1F
→
01/07 23:51, , 2F
剩下來的也一樣就行啦。(然後我不懂為啥要出現 R)
01/07 23:51, 2F
→
01/08 00:00, , 3F
回t大: 因為原組數是5 X 5，超過程式可計算範圍
01/08 00:00, 3F
→
01/08 00:00, , 4F
所以依照divid and conquer想法，將其拆成可算的門檻
01/08 00:00, 4F
→
01/08 00:01, , 5F
然後出現R，是因為該演算法中，有此項計算因子
01/08 00:01, 5F
→
01/08 00:02, , 6F
我是說連 4x4 的部份你也拆開變成 2x2 ?
01/08 00:02, 6F
→
01/08 00:04, , 7F
怎麼會到了 5x5 又不會拆了? 我想你會不會誤會題意把 PQR
01/08 00:04, 7F
→
01/08 00:04, , 8F
用錯地方了?
01/08 00:04, 8F
→
01/08 09:00, , 9F
回t大....分成wxyz並不是拆成2x2，而這樣正是4x4的演算格式
01/08 09:00, 9F
→
01/08 09:01, , 10F
因為書上，正是這樣說的且有舉範例
01/08 09:01, 10F
推
01/08 09:40, , 11F
用大數加法加回去. (a*10^i)(b*10^j)=(ab)*10^(i+j)
01/08 09:40, 11F
→
01/08 11:53, , 12F
能看懂4x4怎麼拆2x2，要拆5x5(當成8x8)並不是什麼難事
01/08 11:53, 12F
→
01/08 13:16, , 13F
上面有說到，假設只能算4X4。所以不能算5X5
01/08 13:16, 13F
→
01/08 13:16, , 14F
分割的技巧我會，目前比較不太了解如何做Merge
01/08 13:16, 14F
→
01/08 13:17, , 15F
Divide and Conquer的精神就在於此，而並非把所有數列分割
01/08 13:17, 15F
→
01/08 13:17, , 16F
而是要分割到門檻，計算後再逐一合併
01/08 13:17, 16F
→
01/08 13:21, , 17F
我目前不太了解就是合併，而不在於5x5或8x8的分割計算
01/08 13:21, 17F
推
01/08 13:22, , 18F
用大數加法加起來啊
01/08 13:22, 18F
→
01/08 13:23, , 19F
4x4的拆到2x2的,所以8x8的拆到4x4的啊
01/08 13:23, 19F
→
01/08 13:23, , 20F
恩 我現在有用了，只是單純回覆t大的回文
01/08 13:23, 20F
→
01/08 13:23, , 21F
啊弄完不是再加起來就好了
01/08 13:23, 21F
→
01/09 00:16, , 22F
非常感謝suhorng跟tkcn的指導，小弟現在會了
01/09 00:16, 22F
→
01/09 10:38, , 23F
除非是作業...私心覺得 自己想,直接模擬直式乘法就好...
01/09 10:38, 23F
→
01/09 20:51, , 24F
給s大 我在寫大數演算法程式，那天腦袋很渾沌
01/09 20:51, 24F
→
01/09 20:51, , 25F
突然有個地方誤解錯誤
01/09 20:51, 25F
→
01/09 20:52, , 26F
一直想不出來，目前是寫完了，但我用的也不是您上次提供
01/09 20:52, 26F
→
01/09 20:52, , 27F
給小弟的方法，不過你的建議有點醒我一個觀念
01/09 20:52, 27F
→
01/09 20:52, , 28F
我整理，如果可以的話，等等po上來Y
01/09 20:52, 28F
→
01/09 20:54, , 29F
然後回T大: 您給小弟的建議也正確，但我那天真的有點遲鈍了
01/09 20:54, 29F
‣ 更多 Raisto 的文章
文章代碼(AID): #1D9p1Pom (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Raisto 的文章
文章代碼(AID): #1D9p1Pom (Prob_Solve)