大整数乘法

大整数乘法

c++实现

思想：竖式计算，整体考虑进位

835 * 49

a：

index：  2  1  0 

             8  3  5

 

 

b：

index:  2  1  0 

           0  4  9

 

 

 

结果数组r，835*9先不进位

r：

index:  2   1   0 

          72  27  45

 

 5*4在10位，r[1] += 20

r：

index:  2   1   0 

          72  47  45

 

3*4在百位，r[2] += 12

r：

index:  2   1   0 

          87  47  45

 

8*4在千位，r[3] += 32

r：

index: 3   2   1   0 

         32  84  47  45

 

乘法过程完毕，进行进位计算，得到最终结果

r：

index:4  3   2   1   0 

         4  0   9   1   5

 

具体实现：

#include<iostream>
using namespace std;

void main(){
	char a[201], b[201];
	int a1[402], b1[402], r[402];
	memset(a1, 0, sizeof(a1));
	memset(b1, 0, sizeof(b1));
	memset(r, 0, sizeof(r));
	cin >> a >> b;
	int len1 = strlen(a);
	int len2 = strlen(b);
	int i, j = 0, k = 0;
	for(i = len1 - 1; i >= 0; i --){
		a1[j ++] = a[i] - '0'; 
	}
	j = 0;
	for(i = len2 - 1; i >= 0; i --){
		b1[j ++] = b[i] - '0';
	}
	
	for(i = 0; i < len1; i ++){
		k = i;
		for(j = 0; j < len2; j ++){
			r[k ++] += a1[i] * b1[j];
		}
	}
	int n = 0;//表示进位
	int temp;
	for(i = 0; i < k; i ++){
		temp = r[i] + n;
		r[i] = temp % 10;		
		n = temp / 10;
	}
	if(n != 0)
		cout << n;
	for(i = k - 1; i >= 0; i --){
		cout << r[i];
	}
	cout << endl;


}