# [算法题] 大数相乘

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

152 篇文章41 人订阅

0 条评论

## 相关文章

### echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1442

### 2018年SCI期刊最新影响因子排行，最高244，人工智能TPAMI9.455

2018年6月26日，最新的SCI影响因子正式发布，涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹，其影响因子今年再创新高，达244.585...

1482

### Html5模拟通讯录人员排序（sen.js）

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

6426

### Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1192

### Dataset 列表：机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1831

1953

### Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1876

2608

63111

### 高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分，其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4