首页 > 专题系列 > C基础练习 > C语言程序设计-大整数乘法[数组应用]
2013
11-19

C语言程序设计-大整数乘法[数组应用]

大整数乘法

【问题描述】求两个不超过200位的非负整数的积。

【输入形式】有两行,每行是一个不超过200位的非负整数,没有多余的前导。

【输出形式】一行,即相乘后的结果。结果不能有多余的前导0,即如果结果是342,那么就不能输出为0342。

【样例输入】12345678900

                     98765432100

【样例输出】1219326311126352690000

【样例说明】这两个大整数相乘所得的结果是1219326311126352690000。

【评分标准】本题共4个测试点,每个测试点0.25分,全部通过得1.0分。

#include <stdio.h>
char strnum1[210], strnum2[210];
int num1[210], num2[210], ans[40000];
int main(){
	gets(strnum1);
	gets(strnum2);
	int m = 0, n = 0;

	//将字符串转化为数字
	while (strnum1[m]){
		num1[m] = strnum1[m] - '0';
		m++;
	}
	while (strnum2[n]){
		num2[n] = strnum2[n] - '0';
		n++;
	}
	int up; //进位
	int tmp ; //临时变量
	int k, p, i, j; // k,p 记录计算的位置
	for (i = m - 1, k = 0; i >= 0; i--, k++){
		tmp = 0, up = 0;
		for (j = n - 1, p = 0; j >= 0; j--, p++){
			tmp = num1[i] * num2[j] + up + ans[k + p];
			ans[k + p] = tmp % 10;
			up = tmp / 10;
		}
		if (up > 0)
			ans[k + p] = up;
	}
	int len = m * n;
	while (ans[len--] == 0);
	//逆序输出
	for (int i = len + 1; i >= 0; i--)
		printf("%d", ans[i]);
	return 0;
}

 


  1. 有bug,应为:ans[40000] = {0}样例输出错误:【样例输入】1234567890098765432100【样例输出】108215210126352690000不是1219326311126352690000

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  3. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。