大整数加法,也就是A+B的高精.. 这道追根到一年前的万恶题(在openjudge中做过 但是WA告终) 在上星期4上午刷题的时候碰到. 结果还是懵逼先放一边了. 没想到下午的acm选拔赛就出了a+b高精…. 结局当然还是做不出来. 还好最终还是被选拔上了, 不然大概要后悔好久. 于是赛后好好研究了a+b的高精..

题目描述:

高精度加法,x相当于a+b problem,不用考虑负数

输入格式:

分两行输入a,b <= 10^500

输出格式:

输出只有一行, 代表A+B的值

几样特别点的输入数据

1. 0001 1000
2. 0 0
3. 000 0000
4. 9999 1
5. 1 9999
6. 99900 00999
7. 00999 99900
8. 112233445566778899 998877665544332211

这道题目在luogu或hdu上的数据都较弱 上述很多极端的数据都没有出现,因为想要AC其实还算轻松, 但是当然还是要追求完美.. 于是在处理上述数据的时候碰到一大堆坑


1.前导0的处理 (像 00001 1 这种数据 结果就不能是00002了)
2.如何处理相加的过程
3.怎么把结果输出出来

前导0的处理

以前考虑这个的时候, 是先直接相加后 然后在输出的时候添加判断去除前导0的 现在发现那样做的话实在是太麻烦 容易导致错误. 于是现在把这一部分放在最开头..

    int n1 = strlen(s1),n2 = strlen(s2);
    int m1,m2;
    for(int i = 0;i < n1;i ++)
    {
        if(s1[i] != '0' && s1[i] != NULL)
        {
            m1 = i;
            break;
        }
        else if(s1[i] == '0' && i == n1 - 1)
        {
            m1 = 0;
            n1 = 1;
            break;
        }
    }
    for(int i = 0;i < n2;i ++)
    {
        if(s2[i] != '0' && s2[i] != NULL)
        {
            m2 = i;
            break;
        }
        else if(s2[i] == '0' && i == n2 - 1)
        { 
            m2 = 0;
            n2 = 1;
            break;
        }
    }

n1 n2 分别为两个字符串的长度
然后从头开始遍历两个字符串, 直到碰到非0并且不是’\0′ 用新的变量m1/m2 记录当前下标 break跳出循环

或者如果遍历到最后一个元素时候还为0 也就是像 0 00000 这种情况 把m1/m2设为数组的第一个坐标(也就是0) 并把长度n1/n2改为1 然后跳出 (因为只需要一个0即可 即使是00000… 和0也没有任何区别

在这里 n1,n2 还是字符串原先的长度(除非全部都为0时,只看作为1个0) 而m1,m2为实际字符串的头下标(去掉了前面多余的0后 即是这个数的真正的最高位

如何处理相加的过程

一开始我的思路是用3个字符数组解决, 但是这样操作的话实在是太麻烦了. 特别是在进位的时候, 需要不断的转换类型. 搞的太乱还做的不对.

于是思路应该是 再定义3个int类型的数组,把字符串转换成数字再进行运算就不用纠结转换的问题了

    char s1[1000] = {},s2[1000] = {}; // 存放输入字符串
    int a[1000] = {},b[1000] = {},c[1000] = {}; // 分别存 两个输入和输出
    for(int i = n1 - 1,j = 0;i >= m1;i --,j ++)
    {
        a[j] = s1[i] - '0';
    }
    for(int i = n2 - 1,j = 0;i >= m2;i --,j ++)
    {
        b[j] = s2[i] - '0';
    }

上述代码的存储是逆着存的 也就是先把原先在数组后面的低位存到前面. 当然也可以正着存 只是这样逆着存在相加的时候处理起来简单多.

    int len = max(n1-m1,n2-m2);

    for(int i = 0;i < len;i ++)
    {
        c[i] = a[i] + b[i] + c[i];
        c[i + 1] = c[i] / 10;
        c[i] %= 10;
    }

为了能够完整的进行加法运算, 需要知道两个数最大的位数 (实际位数)
因此 (nx-mx) 就能得到啦 (字符串长度-实际字符串的头下标) 再用一下max函数得到len

由于已经存到整数数组里了, 因此像平时加法运算一样处理即可. 但每个数组元素只能存一个位数 当大于等于10的时候 让下一位变为1(+1也是一样 因为下一位还是为0) 然后取模10 并且也是反方向存储的 (最后输出的时候从后往前输出即可)

怎么把结果输出出来

细心的话已经发现了, 因为len的原因只会运算到位数最高的时候, 而此时可能会进位. 因此结果的长度会是为len + 1 举个例子
123456789
987654321 这里len为9
1111111110 而结果会为10 因此在输出结果之前先做个判断

if(c[len] == 0)
{
    len --;
}

判断len + 1是否为0 如果不是0 也就是有进位 (下标之所以为len 是因为数组下标从0开始 这个应该很好懂2333) 如果没有进位, 那就len自减 那么c[len]就表示为结果的最高位的数字了 反之亦然

for(int i = len;i >= 0;i --)
{
    printf("%d",c[i]);
}

然后开始反向输出! 即是答案了~

完整代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main()
{
    char s1[1000] = {},s2[1000] = {};
    int a[1000] = {},b[1000] = {},c[1000] = {};

    scanf("%s %s",s1,s2);

    int n1 = strlen(s1),n2 = strlen(s2);
    int m1,m2;
    for(int i = 0;i < n1;i ++)
    {
        if(s1[i] != '0' && s1[i] != NULL)
        {
            m1 = i;
            break;
        }
        else if(s1[i] == '0' && i == n1 - 1)
        {
            m1 = 0;
            n1 = 1;
            break;
        }
    }
    for(int i = 0;i < n2;i ++)
    {
        if(s2[i] != '0' && s2[i] != NULL)
        {
            m2 = i;
            break;
        }
        else if(s2[i] == '0' && i == n2 - 1)
        { 
            m2 = 0;
            n2 = 1;
            break;
        }
    }

    for(int i = n1 - 1,j = 0;i >= m1;i --,j ++)
    {
        a[j] = s1[i] - '0';
    }
    for(int i = n2 - 1,j = 0;i >= m2;i --,j ++)
    {
        b[j] = s2[i] - '0';
    }

    int len = max(n1-m1,n2-m2);

    for(int i = 0;i < len;i ++)
    {
        c[i] = a[i] + b[i] + c[i];
        c[i + 1] = c[i] / 10;
        c[i] %= 10;
    }
    if(c[len] == 0)
    {
        len --;
    }
    for(int i = len;i >= 0;i --)
    {
        printf("%d",c[i]);
    }

    return 0;
}

第一次使用markdown写 什么都不懂还是感觉写的怪怪的(

Categories: OIer

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

OIer

P3371 单源最短路径 (最短路4种算法总结)

经过一星期的努力,总算把图论最短路的4个算法弄懂(可能) 其中包括Di Read more…

OIer

P2935 最好的地方 BestSpot

这是即hdu2066后的第3题Floyd题目, 第二题因为过水而没什么 Read more…

OIer

hdu2066 一个人的旅行 (Floyd)

初学图论, 其实还是dp的知识( 因为学校算法课讲dp讲到了floyd Read more…