[算法题]大数相乘

#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; } /*=============================================================== 将被乘数与乘数中一位数字的乘积结果计入res数组中 ==============================================================*/ 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