大数相乘算法

简介:
#include <stdio.h>
#include <string.h>

#define MAX_LENGTH 1000

/************************************************************************/
/* 功能:计算两个超大数的乘积
/* 参数:source1:被乘数,字符型数组,长度最大为MAX_LENGTH
/*       source2:乘数,字符型数组,长度最大为MAX_LENGTH
/*       result:计算结果,并返回
/************************************************************************/
void Multiply(char *source1, char *source2, char *result)
{
	int i, j, k, m, n, temp;
	char tempArr[MAX_LENGTH + 1];
    int length1, length2;
	int carryBit = 0;
	int start = 0;

	length1 = strlen(source1);
	length2 = strlen(source2);

	for (i = 0; i < MAX_LENGTH; i++)
	{
		result[i] = '0';
	}

	for (i = length1 - 1; i >= 0; i--)
	{
		k = 0;
		carryBit = 0;
		for (j = length2 - 1; j >= 0; j--) 
		{
			temp = (source2[j] - '0') * (source1[i] - '0') + carryBit;
			tempArr[k++] = temp % 10 + '0';
			carryBit = temp / 10;
		}
		while (carryBit != 0)
		{
			tempArr[k++] = carryBit % 10 + '0';
			carryBit /= 10;
		}

        for (m = start, n = 0; n < k; m++, n++)
        {
			temp = result[m] - '0' +  tempArr[n] - '0' + carryBit;
			carryBit = temp / 10;
			result[m] = temp % 10 + '0';	
        }
		while (carryBit)
		{
			result[++m] = carryBit % 10 + '0';
			carryBit /= 10;
		}
		start++;
	}
    result[++m] = '\0';
}

int main()
{
	char source1[MAX_LENGTH];
	char source2[MAX_LENGTH];
	char result[MAX_LENGTH];
	int i, begin;

	scanf("%s%s", source1, source2);
	Multiply(source1, source2, result);

	// 找到最后一个前导0的位置
	begin = strlen(result) - 1;
	for (i = begin; i >= 0; i--)
	{
		if (result[i] == '0')
		{
			begin--;
		}
		else
		{
			break;
		}
	}

	for (i = begin; i >= 0; i--)
	{
		printf("%c", result[i]);
	}
	putchar(10);

	return 0;
}

目录
相关文章
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询
22 0
|
6天前
|
存储 算法 数据挖掘
LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】
LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】
|
10月前
|
存储 算法
算法之字符串问题(第415题字符串相加、第43题字符串相乘、第316题去除重复字母)
算法之字符串问题(第415题字符串相加、第43题字符串相乘、第316题去除重复字母)
56 0
|
8月前
|
算法
【每日挠头算法(4)】字符串相加|字符串相乘
【每日挠头算法(4)】字符串相加|字符串相乘
|
10月前
|
算法
基础算法(大数操作 前缀和 差分)
基础算法(大数操作 前缀和 差分)
51 0
|
12月前
|
分布式计算 算法 搜索推荐
【经典算法问题 一】海量数据中找出前k大数(topk问题)
【经典算法问题 一】海量数据中找出前k大数(topk问题)
131 0
|
算法 C++ Python
【每日算法Day 82】面试经典题:求第K大数,我写了11种实现,不来看看吗?
【每日算法Day 82】面试经典题:求第K大数,我写了11种实现,不来看看吗?
|
算法
【Day24】 LeetCode算法题 (注释详细+解题思路)[43. 字符串相乘 ] [1800. 最大升序子数组和]
学习 (注释详细+解题思路)[43. 字符串相乘 ] [1800. 最大升序子数组和]。
115 0
【Day24】 LeetCode算法题 (注释详细+解题思路)[43. 字符串相乘 ] [1800. 最大升序子数组和]
|
算法
经典算法题-大数相加&数字字符串相加
leetcode:415. 字符串相加题链 这是一个校招面试时候,手写频率比较高的一个算法题,这里给大家分享三种方法: 一个常规解法,两个清奇的思路
算法零基础——大数四则运算
算法零基础——大数四则运算
算法零基础——大数四则运算