说明

大数乘法假如凭证数组一位对应数的一位来手动模仿乘法的进程是较量轻易的，只必要在每位相乘累加跋文得进位就行了，并不伟大，此时的进位也就是默认的满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;
}

（编辑：湖南网）

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