問題描述：如標題所示，就是兩個大整數相乘，有時候如果數值過大，計算機是不能直接計算出來的，就需要使用到分支的思想，
分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同，求出子問題的解，就可得到原問題的解，即一種分目標完成程式演算法，一般情況都會用二分來解決（網上資料很多，此處不再贅述），
情景假設：假設有兩個大整數X、Y，分別設X=1234、Y=6789，現在要求X*Y的乘積，小學的演算法就是把X與Y中的每一項去乘，但是這樣的乘法所需的時間復雜度為O(N^2)，(因為每一位要逐個去乘)，所以效率比較低下，那我們可以采用分治的演算法，將X、Y拆分成四部分，如下圖:
這樣X可以表示為
Y同理，所以Y=C*10^(n/2)+D;
(有的資料書上寫的是X=A**2^(n/2)+B,因為它是表示的二進制，此處寫的是十進制，)
所以現在將一個大的整數分成了兩部分，問題規模減小，這樣直接相乘就會寫成
但是這樣你會發現，最后還是要計算4次n/2位整數的乘法，以及三次加法，根據master定理最后會發現T(n)=O(n^2);所以說這其實沒有改進成功，要改進成功，就需要通過將算式變形來減少乘法的次數，對此，我們寫成如下形式：
這樣就能減少乘法的次數，（只做了AC,BD (A-B)(D-C)三次乘法）,由master定理可得T（n）=O(n^log3),優化成功，
測驗代碼如下：
#include<cstdio>
#include<cmath>
using namespace std;
#define SIGN(A) ((A > 0) ? 1 : -1)
int divideConquer(int X, int Y, int n) {
int sign = SIGN(X) * SIGN(Y);
int x = abs(X);
int y = abs(Y);
if (x == 0 || y == 0) {
return 0;
}
else if (n == 1) {
return sign * x * y;
}
else {
int A = (int)x / pow(10, (int)(n / 2));
int B = x - A * pow(10, n / 2);
int C = (int)y / pow(10, (int)(n / 2));
int D = y - C * pow(10, n / 2);
int AC = divideConquer(A, C, n / 2);
int BD = divideConquer(B, D, n / 2);
int ABDC = divideConquer((A - B), (D - C), n / 2) + AC + BD;
return sign * (AC * pow(10, n) + ABDC * pow(10, (int)(n / 2)) + BD);
}
}
int main() {
int x, y, n;
scanf_s("%d%d%d", &x, &y, &n);
printf("x 和 y的乘積為：%d", divideConquer(x, y, n));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/128056.html
標籤：其他