[算法题] 大数相乘

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

【工具】SAS数据整理的16个技巧

1、修改属性   attrib 2、根据条件删除记录   if条件 then delete; 3、分拆数据集 data mastermissing; me...

2835
来自专栏ml

Java 基础知识点(必知必会其二)

   1.如何将数字输出为每三位逗号分隔的格式,例如“1,234,467”?    1 package com.Gxjun.problem; 2 3 i...

3665
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第3章 Kotlin语言基础第3章 Kotlin语言基础《Kotlin极简教程》正式上架:参考资料

学习任何东西,都是一个由表及里的过程。学习一门编程语言也一样。对于一门编程语言来说,“表” 就是基本词汇(关键字、标识符等)、句子(表达式)和语法。

942
来自专栏java一日一条

UML类图五种关系与代码的对应关系

注意1: Water类的生命期,它是当Animal类的GrounUp方法被调用的时候,才被实例化。

411
来自专栏写代码的海盗

维多利亚的秘密 golang入坑系列

原文在gitbook,字字原创,版权没有,转载随意。 在写本文的前一天,2017维密在上海开始了。 为了纪念屌丝界的盛世,特为本节起名维多利亚的秘密。现在的社会...

3378
来自专栏北京马哥教育

Python练手题,敢来挑战吗?

这到题用到了字符串的所有字母大写和所有字母小写和字符串拼接,复制,用到的函数有 json 将列表中的内容按照指定字符连接成一个字符串,

670
来自专栏应兆康的专栏

遇见 Kotlin 先导篇:Kotlin 相比 Java 好在哪里?

Kotlin 是一种为现代多平台应用而诞生的静态编程语言相比于Java而言,它有很多优点,待会笔者会就几个写一下,并给出实际例子。

3394
来自专栏GreenLeaves

C# String.Format的格式限定符与Format方法将多个对象格式化一个字符串原理

Format方法将多个对象格式化成一个字符串Format方法解析格式字符串的原理:

492
来自专栏企鹅号快讯

一文搞懂宏程序的编程基础,快速入门秘笈

引领机械前沿、机械视频,汽车、加工技术、3D打印、自动化、机器人、生产工艺、轴承、模具、机床、钣金等行业前沿在这里等你 1. 什么场合会用到宏程序编程? 其实说...

1798
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day07-代码题-自定义数据类型;ArrayList集合

Java基础-day07-代码题-自定义数据类型&ArrayList集合 1.饭店结账程序. 定义菜品类,属性为名称,价格,数量. 集合中添加若干菜品对象. 遍...

2724

扫码关注云+社区