大整數乘法
分治法
將一個規模為N的問題，分解成K個規模較小的子問題，這些子問題相互獨立且月原問題性質相同，求解出子問題的解，合并得到原問題的解
分治演算法特征分析
分治法能解決的問題一般具有以下幾個特征：
-
該問題的規模縮小到一定程度就可以容易的解決；
-
該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；
-
利用該問題分解出子問題的解，可以合并為該問題的解；
-
該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題；
大整數乘法：十進制
解法一（分治法）
將兩個整數分別一分為二：
X = A*10^(n/2) + B
Y = C*10^(n/2) + D
XY = (A10^(n/2) + B)( C10^(n/2) + D) = AC10^n + AD10^(n/2) + BC10^(n/2) + B*D
但是這樣做并沒有減少直接相乘的的時間復雜度，所以要繼續減少乘法的次數
XY = (A10^(n/2) + B)( C10^(n/2) + D)
= A*C*10^n + A*D*10^(n/2) + B*C*10^(n/2) + B*D
= A*C*10^n + ((A+B)(C+D) – A*C – B*D)*10*(n/2) + B*D
或者：= AC10^n + ((A-B)(D-C) + AC + BD)10(n/2) + B*D
然后利用上面的公式寫遞回就好了
解法二
模擬乘法
將兩個數分別存入兩個陣列，然后根據乘法規則兩層for回圈分別讓數字相乘，并存入一個新的陣列，大致為這樣：result[a+b] += num1[a]*num2[b];，現在這個result里存盤的就是一個非個位數的臨時結果，只需要做后將這個臨時結果分別進位便可得到最終結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/142658.html
標籤：其他
上一篇：誰有音樂播放器的源代碼，求賜教
下一篇：怎么指定他跳轉網址的ip