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潛規則