大家好,又见面了,我是你们的朋友全栈君。
问题描述
求两个不超过200位的非负整数的积。
输入数据
有两行,每行是一个不超过200位的非负整数,没有多余的前导0。
输出要求
一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。
输入样例
12345678900
98765432100
输出样例
1219326311126352690000
解题思路
在下面的例子程序中,用unsigned an1[200]和unsigned an2[200]分别存放两个乘数,用aResult[400]来存放积。计算的中间结果也都存在aResult中。aResult长度取400是因为两个200位的数相乘,积最多会有400位。an1[0], an2[0], aResult[0]都表示个位。
计算的过程基本上和小学生列竖式做乘法相同。为编程方便,并不急于处理进位,而将进位问题留待最后统一处理。
现以 835×49为例来说明程序的计算过程。
先算835×9。5×9得到45个1,3×9得到27个10,8×9得到72个100。由于不急于处理进位,所以835×9算完后,aResult如下:
接下来算4×5。此处4×5的结果代表20个10,因此要 aResult[1]+=20,变为:
再下来算4×3。此处4×3的结果代表12个100,因此要 aResult[2]+= 12,变为:
最后算 4×8。此处4×8的结果代表 32个1000,因此要 aResult[3]+= 32,变为:
乘法过程完毕。接下来从 aResult[0]开始向高位逐位处理进位问题。aResult[0]留下5,把4加到aResult[1]上,aResult[1]变为51后,应留下1,把5加到aResult[2]上……最终使得aResult里的每个元素都是1位数,结果就算出来了:
总结一个规律,即一个数的第i位和另一个数的第j位相乘所得的数,一定是要累加到结果的第i+j位上。这里i, j都是从右往左,从0开始数。
参考程序:
#include <stdio.h>
#include <string.h>
#define MAX_LEN 200
unsigned an1[MAX_LEN+10];
unsigned an2[MAX_LEN+10];
unsigned aResult[MAX_LEN * 2 + 10];
char szLine1[MAX_LEN+10];
char szLine2[MAX_LEN+10];
int main()
{
gets( szLine1); //gets函数读取一行
gets( szLine2);
int i, j;
int nLen1 = strlen( szLine1);
memset( an1, 0, sizeof(an1));
memset( an2, 0, sizeof(an2));
memset( aResult, 0, sizeof(aResult));
j = 0;
for( i = nLen1 - 1;i >= 0 ; i --)
an1[j++] = szLine1[i] - '0';
int nLen2 = strlen(szLine2);
j = 0;
for( i = nLen2 - 1;i >= 0 ; i --)
an2[j++] = szLine2[i] - '0';
for( i = 0;i < nLen2; i ++ ) { //每一轮都用an1的一位,去和an2各位相乘
//从an1的个位开始
for( j = 0; j < nLen1; j ++ ) //用选定的an1的那一位,去乘an2的各位
aResult[i+j] += an2[i]*an1[j]; //两数第i, j位相乘,累加到结果的第i+j位
}
//下面的循环统一处理进位问题
for( i = 0; i < MAX_LEN * 2; i ++ ) {
if( aResult[i] >= 10 ) {
aResult[i+1] += aResult[i] / 10;
aResult[i] %= 10;
}
}
//下面输出结果
bool bStartOutput = false;
for( i = MAX_LEN * 2; i >= 0; i -- )
if( bStartOutput)
printf("%d", aResult[i]);
else if( aResult[i] ) {
printf("%d", aResult[i]);
bStartOutput = true;
}
if(! bStartOutput )
printf("0");
return 0;
}
实现技巧
不一定一出现进位就马上处理,而是等全部结果算完后再统一处理进位,有时会方便些。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/137192.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...