算法总结——大整数乘法

算法总结——大整数乘法问题描述求两个不超过200位的非负整数的积。输入数据有两行,每行是一个不超过200位的非负整数,没有多余的前导0。输出要求一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。 输入样例1234567890098765432100输出样例1219326311126352690000解题思路在下面的例子程序中,用

大家好,又见面了,我是你们的朋友全栈君。

问题描述

求两个不超过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账号...

(0)


相关推荐

  • Android应用程序启动过程源代码分析(4)

    Android应用程序启动过程源代码分析(4)

  • web安全(入门篇)

    web安全的概念太过于宽泛,博主自知了解的并不多,还需要继续学习。但是又想给今天的学习进行总结,所以今天特分享一篇关于web安全的文章,希望对初次遇到web安全问题的同学提供帮助。SQL注入数据库表出现场景当开发登录模块的时候,如果我们使用是mysql操作php,并非使用mysqli、PDO等;当查询用户是否存在的SQL是这样写的,select*fromuserwherename=

  • pytest运行_pytest执行多个py文件

    pytest运行_pytest执行多个py文件前言pytest运行完用例之后会生成一个.pytest_cache的缓存文件夹,用于记录用例的ids和上一次失败的用例。方便我们在运行用例的时候加上–lf和–ff参数,快速运行上一

  • 【数据分享】历次人口普查数据(一普到七普)[通俗易懂]

    【数据分享】历次人口普查数据(一普到七普)[通俗易懂]【数据分享】历次人口普查数据(一普到七普)

  • read函数的用法

    read函数的用法原文出自:https://blog.csdn.net/zbk840901528/article/details/7849644非常感谢网友的分享,对本人很有帮助,谢谢!!!read的用法read函数可以读取文件。读取文件指从某一个已打开地文件中,读取一定数量地字符,然后将这些读取的字符放入某一个预存的缓冲区内,供以后使用。使用格式如下:number=read(handle,buff…

  • 基于java的项目开发过程_软件开发项目管理整个流程图

    基于java的项目开发过程_软件开发项目管理整个流程图完整项目开发过程原型的设计有产品经理负责。界面的美化有专门的美工负责。前端有专门的前端开发人员负责。研发:研发主要工作就是根据项目的需求文档设计系统架构、设计数据库、编写调试程序代码。对于普通的码农来说,主要的就是编写和调试程序。基于Java的项目开发:1、要想编写程序,需要一个能编写源代码的编辑工具。例如:Notepad++;2、要想测试程序,需要一个编译、执行

    2022年10月26日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号