问题：
由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。
下面就是用分治算法解决“大数相乘”问题。
分治算法解题的一般步骤：
分解：将要解决的问题划分为若干个规模较小的同类问题求解：当子问题划分的足够小时，用较简单的方法解决合并：按原问题的要求，将子问题的解逐层合并构成原问题的解
#include<iostream>using namespace std;#include<string.h>#define MAXSIZE 1000int *result; //定义全局整型数组，存放结果 int Multipy(char*a,int ai,int aj,char*b,int bi,int bj,int move){if(aj-ai <=1 && bj-bi <= 1){//当子问题为两位数和两位数相乘或者更小时int t1,t2;t1 = a[ai] - 48;if(aj != ai)t1 = t1*10+(a[aj] - 48);t2 = b[bi] - 48;if(bj != bi)t2 = t2*10+(b[bj] - 48); result[move] += t1*t2;return 1;}int m = (ai+aj)/2;int n = (bi+bj)/2;int s = aj - m;int k = bj - n;Multipy(a,ai,m,b,bi,n,s+k+move); //对问题的分解Multipy(a,m+1,aj,b,n+1,bj,move);Multipy(a,m+1,aj,b,bi,n,k+move);Multipy(a,ai,m,b,n+1,bj,s+move);}int Arrange(int *a){//将result数组中的值进行整理，方便输出int i = 0;int t,p1,p2;while(a[i] != 10000){//以特殊数为终止条件 if(a[i] < 10);else if(a[i] < 100){t = a[i] % 10;p1 = a[i] / 10;a[i] = t;a[i+1] += p1;}else{t = a[i] % 10;p1 = a[i] / 10 % 10;p2 = a[i] / 100;a[i] = t;a[i+1] += p1;a[i+2] += p2;}i++;} }int main(){while(1){char a[MAXSIZE], b[MAXSIZE]; //以字符串形式存放两个大数 int a_len,b_len; //存放两个数的长度（不包括正负号） int minus = 0; //0,2代表结果为正，1代表结果为负 int len; //决定result数组实际存放数据的长度（不包括正负号） cout<<"请输入两个数，用空格隔开："<<endl;cin>>a>>b;a_len = strlen(a);b_len = strlen(b);len = a_len+b_len;if(a[0] == '-'){minus++;len--;} if(b[0] == '-'){minus++;len--;} result = new int(len+1); for(int i = 0; i <= len-1; i++){//result数组全置为0 result[i] = 0;}result[len] = 10000;//给result数组多一位存放特殊数（大于四位数的都可以） if(a[0] == '-'&&b[0] == '-')Multipy(a,1,a_len-1,b,1,b_len-1,0);else if(a[0] == '-'&&b[0] != '-')Multipy(a,1,a_len-1,b,0,b_len-1,0);else if(a[0] != '-'&&b[0] != '-')Multipy(a,0,a_len-1,b,0,b_len-1,0);else Multipy(a,0,a_len-1,b,1,b_len-1,0);Arrange(result);int end = len-1; while(result[end] == 0){//结果数的前面的位数为0时，把它们省略end -= 1;}if(minus == 1)cout<<'-';for(int i = end; i >= 0; i--){cout<<result[i];}if(end == -1)cout<<"0"; //这是结果为0的情况，以免没有输出cout<<endl; delete result;} }
参考资料：
《算法学习与应用 从入门到精通》张玲玲
【算法】大数乘法问题及其高效算法
百度百科 大数运算
百度百科 karatsuba乘法
大数相乘（分治法， C/C++）
如果觉得《大数相乘（C语言 分治算法）》对你有帮助，请点赞、收藏，并留下你的观点哦！
