# [算法题] 大数相乘

#include "oj.h"
#include <stdio.h>
#include <string>
#define OK     0
#define ERROR -1

/* 函数声明 */
void calc1(char* pcStrA, int iLenA, int* piTmp, int num);
void accumulate(int iIndex, int *piResult, int iLenResult, int *piTemp, int iLenTemp);
char* BignumMultiply(char* pcNumA,int iLenA,char* pcNumB,int iLenB,char* pcResult,int iLenResult);

/*===============================================================
调用calc1和accumulate函数计算大数相乘
===============================================================*/
char* BignumMultiply
(
char* pcNumA,
int iLenA,
char* pcNumB,
int iLenB,
char* pcResult,
int iLenResult
)
{
int i     = 0;
int j     = 0;
int num   = 0;
int index = 0;
int *piTmp    = NULL;
int *piResult = NULL;

/* 分配临时结果的存放空间 */
piTmp=(int*)malloc((iLenA+1)*sizeof(int));
piResult=(int*)malloc(iLenResult*sizeof(int));
memset(piTmp, 0, (iLenA+1)*sizeof(int));
memset(piResult, 0, iLenResult*sizeof(int));

for (i = iLenB - 1; i>=0; i--)
{
/* 获取乘数pcNumB中第i位的值 */
num = pcNumB[i] - '0';

/* 计算被乘数与第i位的乘积,结果保存在piTmp整型数组中 */
calc1(pcNumA,iLenA,piTmp,num);

/* 将piTmp数组中的值加到piResult数组中 */
index++;
accumulate(index,piResult,iLenResult,piTmp,iLenA+1);
}
printf("\n%s\n", pcResult);

/* 去掉piResult中第一个非零数字前的零 */
i = 0;
while (piResult[i++]==0);

/* 将整形数组piResult中的值转化成字符串存入pcResult中 */
index = 0;
for (j = i - 1; j < iLenResult; j++, index++)
pcResult[index] = piResult[j] + '0';
if (iLenResult == i - 1)
{
pcResult[1] = '\0';
}
else
{
pcResult[index] = '\0';
}

free(piTmp);
free(piResult);
return pcResult;
}

/*===============================================================
计算被乘数与乘数的某一位的乘积
===============================================================*/
void calc1
(
char *pcStrA,
int iLenA,
int *piTmp,
int num
)
{
/* d两个位的乘积结果,remainder余数,carry进位 */
int i         = 0;
int result    = 0;
int remainder = 0;
int carry     = 0;

/* 从被乘数字符串'\0'的前一位算起 */
for (i = iLenA - 1; i >= 0; i--)
{
result = pcStrA[i] - '0';
result *= num;
remainder = (result + carry) % 10;
carry = (result + carry) / 10;
piTmp[i+1] = remainder;
}
if (carry)
piTmp[0] = carry;
else
piTmp[0] = 0;
}

/*===============================================================

==============================================================*/
void accumulate
(
int iIndex,
int *piResult,
int iLenResult,
int *piTemp,
int iLenTemp
)
{
int i = 0;
int j = 0;
int m = 0;
int n = 0;
int remainder = 0;    //余数
static int carry=0;
for (j = iLenTemp - 1, i = 0; j >= 0; j--, i++)
{
m = piTemp[j];
n = piResult[iLenResult-iIndex-i];
if (m + n + carry >= 10)
{
remainder = (m + n + carry) % 10;
carry = 1;
}
else
{
remainder = m + n +carry;
carry = 0;
}
piResult[iLenResult - iIndex - i] = remainder;
}
}

/*****************************************************************************
Prototype    : multiply
Description  : 两个任意长度的长整数相乘, 输出结果
Input Param  :
const std::string strMultiplierA  乘数A
const std::string strMultiplierB  乘数B
Output       :
std::string strRst            乘法结果
Return Value :
int                       0  正确
-1  异常
*****************************************************************************/
int multiply (const std::string strMultiplierA,const std::string strMultiplierB, std::string &strRst)
{
int i = 0;
int j = 0;
int lenA = 0;
int lenB = 0;
int lenResult = 0;
char *pcNumA = NULL;
char *pcNumB = NULL;
char *pcResult = NULL; /* 计算两个字符串的长度,及存储结果所需要的空间 */

lenA = (int)strMultiplierA.length();
lenB = (int)strMultiplierB.length();
if (0 == lenA || 0 == lenB)
{
return ERROR;
}

pcNumA = (char*)strMultiplierA.c_str();
pcNumB = (char*)strMultiplierB.c_str();
lenResult = lenA + lenB + 1; /* 分配并初始化字符串数组 */
pcResult = (char*)malloc(lenResult * sizeof(char));
memset(pcResult, 0, lenResult);
for (i = 0; i < lenResult-1; i++)
*(pcResult + i) = '0'; /* 计算并输出计算结果 */

printf("The result is: %s",BignumMultiply(pcNumA,lenA,pcNumB,lenB,pcResult,lenResult));
for (i = 0; i < (int)strlen(pcResult); i++)
{
strRst += pcResult[i];
}
//printf("\n%s\n", pcResult);
free(pcResult);
return OK;
}
View Code

|
2月前
|

16 0
|
8月前
|

45 0
|
10月前
|

【经典算法问题 一】海量数据中找出前k大数（topk问题）
【经典算法问题 一】海量数据中找出前k大数（topk问题）
112 0
|
11月前
|

【每日算法Day 82】面试经典题：求第K大数，我写了11种实现，不来看看吗？
【每日算法Day 82】面试经典题：求第K大数，我写了11种实现，不来看看吗？
78 0

leetcode：415. 字符串相加题链 这是一个校招面试时候，手写频率比较高的一个算法题，这里给大家分享三种方法： 一个常规解法，两个清奇的思路
193 0

102 0
|

1631 0

1124 0
|

|