487      阿里云  技术社区[云栖]

大数相乘算法

#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;
}

最后更新：2017-04-03 18:52:03

  上一篇： telerik安装教程

  下一篇： App Store潜规则