大整数相加和大整数相乘

大数问题是指操作数超过了计算机常用数据类型的存储范围,常常是用字符串来模仿整数相加和相乘运算来实现的,在模拟的过程中要注意考虑进位和边界条件。

1、大整数相加

先看一下加法的计算过程,如456+56789

   456

56789

---------

57245

     计算过程是从低位往高位开始计算,计算过程要加上进位,如,计算到5+8的时候要加上前面的进位1,得到14,然后14对10取余作为对应结果的第2位,进位为14对10取正,这样一直计算,直到有一个字符串结束,然后考虑进位和没计算完的另一个字符串相加。

边界条件:

    两个大整数相加,结果的长度可能与两个数中长度较大的一个相等,也可能比其大1(进位造成),如123+12=135,123长度为3,12长度为2,结果长度为3,再如99+1=100,结果长度为3比99的长度还大1。

    考虑到这样的边界条件,在申请内存的时候需要对结果至少申请长度较大的那个还要大1。

代码如下:

#include<iostream>
#include<string>
using namespace std;
//字符串倒置
void reverse(char *str)
{
    int len=strlen(str);
    for(int i=0;i<len/2;i++)
    {
        char temp=str[i];
        str[i]=str[len-i-1];
        str[len-i-1]=temp;
    }
}
//大数求和
void bignumsum(char * ope1,char * ope2,char * result)
{
    reverse(ope1);
    reverse(ope2);
    int len1=strlen(ope1);
    int len2=strlen(ope2);
    int max=len1;
    if(max<len2)
    {
        max=len2;
    }
    memset(result,'0',max+1);
    result[max+1]='\0';
    int acc=0;
    int i=0;
    while(i<len1 && i<len2)
    {
        int temp=ope1[i]-'0'+ope2[i]-'0'+acc;
        acc=temp/10;
        result[i]=temp%10+'0';
        i++;
    }
    if(i<len1)
    {
        while(i<len1)
        {
            int temp=ope1[i]-'0'+acc;
            acc=temp/10;
            result[i]=temp%10+'0';
            i++;
        }
    }
    if(i<len2)
    {
        while(i<len2)
        {
            int temp=ope2[i]-'0'+acc;
            acc=temp/10;
            result[i]=temp%10+'0';
            i++;
        }
    }
    //考虑到进位,所以result的长度有可能比ope1和ope2中最大的数据长度还多出一位
    if(acc)
    {
        result[i]=acc+'0';
    }
    else
    {
        result[i]='\0';
    }
    reverse(result);
}
int main()
{
    char num1[4]="456";
    char num2[5]="5678";
    char num3[6];
    bignumsum(num1,num2,num3);
    cout<<num3<<endl;

    char num4[4]="456";
    char num5[5]="678";
    char num6[6];
    bignumsum(num4,num5,num6);
    cout<<num6<<endl;

    char num7[4]="111";
    char num8[5]="2";
    char num9[6];
    bignumsum(num7,num8,num9);
    cout<<num9<<endl;
    return 0;
}

2、大整数相乘

乘法相对于加法稍微复杂一点,需要同时考虑乘法进位和加法进位,还要注意一下计算过程和结果中的对应关系。

如计算123*45

123

  45

------

 615

492

-------

5535

    计算过程是从低位往高位计算,第2个操作数中每一位都与第一个操作数中的所有的位计算一次,而每这样计算一次都进行一次结果的更新,结果先被初始化成全0。而计算过程和结果的规律是,每次计算的时候影响的结果位数是两个操作数位数的和,如上述例子中1是123中的第2位(从低位算起,个位按0位来算),4是45中的第1位,那么这两个数的计算过程将会产生影响的是结果中的第3位,计算过程是1*4+0(上一次乘法的进位)=4,4%10=4,这样就确定了492位置上的那个4,然后再利用加法进位和上一轮的结果来更新结果,结果为0(原来结果对应该位的值)+4(此轮乘法计算之后该位置上对应的值)+1(上一轮加法的进位值)=5

   边界条件:

   两个大整数相乘结果的长度最大为两个操作数长度之和,所以申请内存的时候要注意至少申请两个操作数长度之和的内存。

   代码如下:

#include<iostream>
#include<string>
using namespace std;

void reverse(char *str)
{
    int len=strlen(str);
    for(int i=0;i<len/2;i++)
    {
        char temp=str[i];
        str[i]=str[len-i-1];
        str[len-i-1]=temp;
    }
}
void bignummultiply(char *ope1,char *ope2,char *result)
{
    reverse(ope1);
    reverse(ope2);
    int len1=strlen(ope1);
    int len2=strlen(ope2);
    memset(result,'0',len1+len2);//因为len1和len2两个长度的整数相乘结果最大为len1+len2
    result[len1+len2]='\0';
    int acc=0;//加法进位
    int mcc=0;//乘法进位
    for(int i=0;i<len2;i++)
    {
        acc=0;
        mcc=0;
        for(int j=0;j<len1;j++)
        {
            int temp1=(ope1[j]-'0')*(ope2[i]-'0')+mcc;
            mcc=temp1/10;
            temp1=temp1%10;
            int temp2=result[i+j]-'0'+temp1+acc;
            acc=temp2/10;
            result[i+j]=temp2%10+'0';
        }
        result[i+len1]=acc+mcc+'0';
    }
    //这里有一个去除后面0的程序,如78900\0将变成789\0,这样倒过来之后就会使987,而不是00987
    int k=len1+len2-1;
    while('0'==result[k] && k>=0)
    {
        result[k--]='\0';
    }
    //最后经result倒置回来得到最终结果
    reverse(result);
}
int main()
{
    char n1[5]="12";
    char n2[5]="2";
    char n3[10];
    bignummultiply(n1,n2,n3);
    cout<<n3<<endl;

    char n4[5]="9";
    char n5[5]="9";
    char n6[10];
    bignummultiply(n4,n5,n6);
    cout<<n6<<endl;

    char n7[5]="888";
    char n8[5]="66";
    char n9[10];
    bignummultiply(n7,n8,n9);
    cout<<n9<<endl;
    return 0;
}

    以上加法和乘法的计算过程都先使用reverse将字符串倒置,然后再将结果倒置回来计算的,这样是为了更直观的计算,但是,这样会使程序运行效率稍低。实际可以不用倒置,而靠逻辑去写。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据

以大数据之名,变身!——In big data we trust

先关注一则旧闻11月20日,德国联邦网络局禁止在该国销售儿童智能手表,穿戴设备的麦克风,可让家长听到孩子的环境,涉嫌侵犯他人隐私。另10月,挪威消费者理事会在报...

22260
来自专栏企鹅号快讯

交通部:明年将制定无人驾驶政策

12月25日,全国交通运输工作会议在京召开,明确了2018年交通行业18项工作重点。其中,会议明确将组织开展自动驾驶等前沿技术研究与跟踪,研究制定促进自动驾驶发...

20590
来自专栏存储

你真的很熟分布式和事务吗?

微吐槽 hello,world. 不想了,我等码农,还是看看怎么来处理分布式系统中的事务这个老大难吧! 本文略长,读者需要有一定耐心,如果你是高级码农或者架构师...

25290
来自专栏企鹅号快讯

区块链与数字货币是什么关系呢?

我们都知道,区块链技术具有去中心化、稳定、安全等特点,我们一直探讨的问题是区块链技术的运用领域和运用手段,在银链原子链开发的项目中,区块链技术得到良好的施展平台...

43390
来自专栏企鹅号快讯

关于智慧城市的十大反思(上)

一、与历史积累的城市智慧共容 能够生存下来的城市都有智慧。 1.1 不能否定历史上的城市智慧 “智慧城市”起源于IBM的宣传,但是IBM将“Smart City...

26490
来自专栏大数据

聊一聊大数据的问题和缺陷

多亏了大数据和云计算,可以让企业使用超级计算机的力量。而人们面临的问题是用来分析和应用大数据的工具通常有一个致命的缺陷。人们进行的大部分数据分析都是基于错误的模...

25280
来自专栏人工智能

2017奇葩机器人大盘点:Sophia想生孩子,Atlas后空翻,贝佐斯骑高达

编者注:本文来源于科技媒体The Verge,作者是James Vincent。 废话不多说。现在,我就来盘点一下,今年出现的这些又好又坏,还很奇怪的机器人们。...

23580
来自专栏大数据

大数据安全问题分析及对策建议

图片来自网络 作者简介:王竹欣,硕士,毕业于北京航空航天大学电子信息工程学院,现任职于中国信息通信研究院信息通信安全研究所,主要研究方向为网络安全、数据安全。陈...

47660
来自专栏企鹅号快讯

麻省理工学院通过新型人工智能系统用电脑可以合成新材料

即使在缺少试验数据的情况下,设备学习系统也可以在材料“配方”中找到相应的模式。 上个月,麻省理工学院的三位材料科学家及其同事发表了一篇论文,讲述了一种新型人工智...

311100
来自专栏企鹅号快讯

未来AI可能会淘汰180万个工作岗位,你感到恐惧了吗

根据科研公司Gartner的一项新研究,到2020年,人工智能(AI)和机器学习可能会淘汰180万个工作岗位,但同时创造230万个新岗位。在这种情况下,消失和创...

19750

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励