大整数的乘法.cpp

递归和分治法解一系列经典算法

//大整数的乘法（十进制）

#include<string.h>
#include<stdio.h>
#define MAXSIZE 10000

void  Multiply(int *R,int *A,int *B,unsigned int N)
{
	int i, j;
	int posR;
	for(i=0;i<2*MAXSIZE+1;i++) R[i]=0;
	for(i=N-1; i>=0; --i)
	{
        //0参与计算，结果为0，直接跳过
		if(A[i] == 0) continue;
		int carry = 0;
		for(j=N-1; j>=0; --j)
		{
			//计算结果存放的位置
			posR = 2*MAXSIZE+1 - N- N + 1 + i + j;
			//带进位乘法计算，并放入相应的R数组中
			R[posR] += A[i] * B[j] + carry;
			//判断相乘的结果是否大于10,并对结果进行处理
			carry = R[posR] / 10;
			//计算并保存本次进位
			R[posR] %= 10;
		}
		//存储最后一次计算的进位
		R[posR-1] = carry;
	}
	i=0;
	//去掉C数组中的前导0，并打印结果
	while(i<2*MAXSIZE+1-1 && R[i]==0 ) ++i;
	printf("R=");
	for(i; i<2*MAXSIZE+1; ++i) printf("%d",R[i]);
	printf("\n");
}

void main()
{
    //定义两个数组存放乘数和被乘数a和b，
    //并将结果转化为整型后存放在A和B两个整型数组中，两个数组的长度相同
	char a[MAXSIZE],b[MAXSIZE];
	int A[MAXSIZE],B[MAXSIZE];
    int C[2*MAXSIZE+1];  //存放A和B的乘积
	int LenA,LenB,i;
	//输入第一个乘数，并进行有效性判断
    printf("Please input the first number:");
	scanf("%s",a);
	LenA=strlen(a);
	for(i=0;i<=LenA-1;i++)
	{
        if((a[i]-'0')<0||(a[i]-'0')>9)
		{
			printf("Error,please input the first number again\n");
			scanf("%s",a);
			LenA=strlen(a);
			i=-1;
		}
	}
	//输入第二个乘数，并进行有效性判断
	printf("Please input the second number:");
	scanf("%s",b);
	LenB=strlen(b);
	for(i=0;i<=LenB-1;i++)
		if((b[i]-'0')<0||(b[i]-'0')>9)
		{
			printf("Error,please input the second number again\n");
			scanf("%s",b);
			LenB=strlen(b);
			i=-1;
		}
	for(i=0;i<LenA;i++) A[i]=a[i]-'0';
	//显示A数组中的值
	printf("The data are:\n");
	printf("A=");
	for(i=0;i<LenA;i++) printf("%d",A[i]);
	printf("\n");
	//将b中的每一个字符都转化为数字，保存在B数组中
	for(i=0;i<LenB;i++) B[i]=b[i]-'0';
	printf("B=");
	for(i=0;i<LenB;i++) printf("%d",B[i]);
	printf("\n");
	Multiply(C,A,B,LenA);  //A和B相乘，结果放C数组中
}