分析

大数乘法如果按照数组一位对应数的一位来手动模拟乘法的过程是比较容易的，只需要在每位相乘累加后记得进位就行了，并不复杂，此时的进位也就是默认的满10进位，当数组元素大于10时需要进位。这样做可以很快的计算出来。在本文中主要是讨论满100,1000或者10000进位时该如何计算，也就是说将大数按照2位、3位、4位划分为块时，进行计算，只不过块之间直接相乘（int32类型最大为2^32 约等于 4*10^9，满10000进位时，也就块最大值为9999，块相乘< 10^8，故int32块最大为10000，超过9999则相乘int32保存不下），如下所示为满100进位的图示：

程序实现如下：

/*************************************************************************
    > File Name: maxNumMultiple.cpp
    > Author: 
    > Created Time: Thu 07 Apr 2016 04:13:38 PM CST
 ************************************************************************/

#include<iostream>
#include<cmath>
using namespace std;

const int seg = 3;  // 分块大小，取值为1,2,3,4，分别代表满10,100,1000,10000进位模式

int Multiplier[100],Multiplicand[100];
int result[1000];

//前向分块，如将1234分为(12),(34),数组下标序号和数值的高低位反向的，也a[0]=(12),a[1]=(34)
//[0,n-1)
int ChunkForward(int a[],int n)
{
	int sum=0,gap=0;
	gap = n%seg; 
	gap = gap == 0? seg: gap;	
	int j =1,count = 0;
	for(int i=0; i<n; i++)
	{
		sum = sum*10+a[i]; 
		if(j == gap)
		{
			a[count++] = sum;
			sum = 0; gap = seg; j = 1;
		}
		else
			j++; 
	}
	return count;
}
//后向分块后进行交换，如将1234分为(34),(12)即a[0]=(34),a[1]=(12)，原始数据为a[]={1,4},int 1234;
//步骤{1,12,34}---> {34,34},返回长度为2
int chunkBackwardAndSwap(int a[],int n)
{
	int sum = 0;
	int end= n;
	int i,j;
	int temp = 1;
	for(i=n-1,j=0; i>=0; i--)
	{
		if(j == seg)
		{
			a[--end] = sum;
			sum = a[i];
			j = 1;
			temp = 10;
		} 
		else
		{
			sum = sum + a[i]*temp;
			temp *= 10;
			j++;
		}
	}
	a[--end] = sum;

	int count = n-end;
	for(n--,i=0; n>=end&&n>i;)
	{
		a[i++] = a[n--];
	}

	return count;
}
// [0,Ci),[0,Cj)
// 从后往前进行相乘，如int aa = 1234,bb =5678; a[]={12,34} b[]={56,78}
// 循环n-->0，第一步为a[1]*b[1]=34*78

int bigIntMultipleBackword(int a[],int Ci,int b[],int Cj) 
{
	Ci--,Cj--;
	int segValue = pow(10,seg);
	int count = 0; int i,j; 
	for(i=Ci; i>=0 ;i--)
		for(j=Cj; j>=0; j--)
		{
			int value = a[i]*b[j];
			int k = Ci+Cj-i-j;
			value += result[k];
			while(value >= segValue)
			{
				result[k++] = value%segValue;
				value /= segValue;
				value += result[k];
			}
			result[k] = value;
			if(k>count) count=k;
		}

	return count;
}

// 从前往后计算，inta aa=1234,bb=5678,分块数组a[]={34,12} b[]={78,56}
// 相乘 a[0]*b[0]=34*78
int bigIntMultipleForward(int a[],int Cj)
{
	int segValue = pow(10,seg);
	int i=0,j=0;
	int count = 0;
	for(; i<Ci; i++)
		for(j=0; j<Cj; j++)
		{
			int value = a[i]*b[j];
			int k = i+j;
			value = result[k] + value;
			while(value >= segValue)
			{
				result[k++] = value%segValue;
				value /= segValue;
				value += result[k];
			}
			result[k] = value;
			if(k > count) count = k;
		}
	return count;
}

// 输出结果，当分块>1时，得注意输出0的情况，如结果1201直接输出会是121，错误
void printBackword(int count)
{
	int gap = pow(10,seg-1);
	cout << result[count--];
	while(count >=0)
	{
		if(seg > 1)
		{
			int value = result[count--];
			int tmp = gap;
			while(value < tmp)
			{
				cout << "0";
				tmp /= 10;
			}
			if(value != 0) cout << value;
		}
		else
			cout << result[count--];
	}
	cout << endl;
}
//
int main(void)
{
	char c;
	int Ci = 0,Cj = 0;
	int mode = 0;

	//选择计算模式
	cout << "please select algorithm mode(0,1)" << endl;
	cin >> mode; cin.get(c);

	// 输入乘数，被乘数注意不要有空格，按回车结束
	cout << "Input the multiplier" << endl;
	// cin >> c stop when encounter 'n'
	while(cin.get(c) && c != 'n')
	{
		Multiplier[Ci++] = c-'0';
	}

	if(mode)
	{
		if(seg > 1)
			Ci = ChunkForward(Multiplier,Ci);
	}
	else
		Ci = chunkBackwardAndSwap(Multiplier,Ci);

	cout << "Input the multiplicand" << endl;
	while(cin.get(c) && c != 'n')
	{
		Multiplicand[Cj++] = c-'0';
	}
	if(mode)
	{
		if(seg > 1)
			Cj = ChunkForward(Multiplicand,Cj);
	}
	else
		Cj = chunkBackwardAndSwap(Multiplicand,Cj);

	int count = 0;
	if(mode)
		 count = bigIntMultipleBackword(Multiplier,Ci,Multiplicand,Cj);
	else
		 count = bigIntMultipleForward(Multiplier,Cj);

	printBackword(count);

	return 0;
}

（编辑：厦门网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!