题解 P2142 【高精度减法】

· · 题解

虽然我超菜，但这道题实在没有什么难度，主要是在这里介绍一种将高精度减法转换为高精度加法，巧妙避免减法借位的方法。 在特定情况下也能优化程序速度。

首先讲原理。 比如我们用253-76，假如直接做减法的话，从末尾开始减，3-6 = -3，需要向前面的5借位。5变成4，4-7=-3还需要借位，以此类推。最后结果是77

借位就很烦。有什么办法能避免借位呢？ 其实，253 - 76 = 253 + (999 - 76) + 1 - 1000; 这个应该不难理解，补了1+999，最后减去1000. 这么做的好处是，999-76的过程不需要进行借位。只要直接减就行了。 这样，我们就把一次减法转化为一次加法，一次不需要借位的减法。(-1000那个可以直接通过某些方法消除进位)

下面贴代码，代码里也有注释。

稍稍要注意的是，我们要求被减数比减数更大。这也不难，简单判断一下，如果不行就对调减数和被减数，并标记负号就行了。


#include<stdio.h>
#include<stdlib.h>
typedef unsigned char BYTE;

BYTE a[10005] = { 0 };
BYTE b[10005] = { 0 };
BYTE *pa = 0, *pb = 0;
int la, lb;
int sign;//标明结果正负号用的。 
int main()
{
    scanf_s("%s", a,10005);
    scanf_s("%s", b,10005);
    //通过strlen得出长度，长的那个数字大。一样长比较首位，再一样继续循环第二位直到比出大小。（有一个优化，如果有一位一样那么可以直接消掉）
    la = strlen((char *)a);
    lb = strlen((char *)b);

    //全部减去'0'
    int i;
    for (i = 0; i<la; i++)
    {
        a[i] -= '0';
    }
    for (i = 0; i<lb; i++)
    {
        b[i] -= '0';
    }
    if (la>lb)
    {
        //a大，正
        sign = 1;
    }
    else if (la < lb)
    {
        sign = 0;//负号 
    }
    else
    {
        //开始循环比较，有相等的就直接全部砍掉。
        sign = -1;//标记。如果出来还是-1，说明两数相等 
        int BitCheckTag;
        for (BitCheckTag = 0; BitCheckTag<la; BitCheckTag++)//这里la应该就是lb
        {
            if (a[BitCheckTag] > b[BitCheckTag])
            {
                //a > b
                sign = 1;
                break;
            }
            if (a[BitCheckTag] < b[BitCheckTag])
            {
                sign = 0;
                break;
            }
        }

        if (sign == -1)
        {
            printf("0");
            return 0;
        }
    }

    //这里应该已经标记好位数了。
    if (sign == 1)
    {
        pa = a;
        pb = b;
    }
    else
    {
        pa = b;
        pb = a;
        int buf;
        buf = la;
        la = lb;
        lb = buf;
    }
    //现在pa就是大的那个，开始减吧

    //为了避免借位，采用求补的方法。下面是例子

    //253 - 76 = 253 + (999 - 76) + 1 -1000 
    //我们要做的是对减数求补，位数以被减数的为准。

    //将 pb 后移，和 pa 的结尾对齐
    memmove(pb + la - lb, pb, lb);
    memset(pb, 0, la - lb);

    //按la的长度给pb做求补
    for (i = 0; i < la; i++)//la取不到？ 
    {
        pb[i] = 9 - pb[i];
    }

    pb[la - 1]++;
    //补上加一。如果有超过10也不用管，和被减数相加的时候会处理的。

    for (i = la - 1; i >= 0; i--)
    {
        pa[i] += pb[i];
        if (pa[i] >= 10)
        {
            pa[i] -= 10;
            if (i != 0)
            {
                pa[i - 1] ++;
            }
        }
    }

    for (i = 0; i<la; i++)
    {
        pa[i] += '0';
    }

    if (sign == 0)
    {
        printf("-");
    }
    //去除前导0
    for (i = 0; i<la; i++)
    {
        if (pa[i] != '0')
        {
            printf((char *)pa + i);
            return 0;
        }
    }

    return 0;
}