高精度减法的OP写法

stone_juice石汁 · 2019-08-08 09:53:13 · 个人记录

高精度减法基础

\text{Blog} 阅读
题解界面阅读

高精度减法的 \text{OP} 写法

多重运算连击

通常来说，我们都是把高精度算法写在了 \text{main} 函数里面。

优点显而易见，这样写：直观，方便，写法简单，容易上手。

但是，在面对下面这种情况，这样写就有点难受了。

如果一道题目里，要求你进行多次高精度运算，怎么办？

例如 \text{a-b-c-d-.....}

这个时候，如果依然按照“简单写法”，先算 \text{a-b} ，然后 \text{b-c......} 这样写码量惊人，而且很容易出错。“简单写法”并不再简单。

这时候，我们可以进一步思考。既然需要多次运算，我们可以考虑直接写个高精度运算子函数，每次运算只需要调用即可。

这也是我比较推荐的做法。毕竟很少有题直接考高精度，通常高精度都是辅助工具，多次运算在所难免。

那么我们现在就来了解下这种做法：子函数中写高精度！
更加便捷的操作

既然我们要写子函数，那么必然会有返回值。

这里可能有些人就犯难了，这个子函数究竟返回什么好？

有些人可能会想到返回数组。但是不知道怎么写。

其实返回数组是可以的，当然，你不可能定义一个数组型变量(shenmegui)。取之而代的，你可以定义返回一个指针。因为指针在某些情况下确实可以当成数组使用。 利用指针传数组的值，也不是不可以。

但是！我并不喜欢用指针。
- 首先：指针是个强大的东西，但是就是因为它过于强大，所以经常指针会爆掉。爆空间越界一事那是经常发生，有时候莫名其妙就炸了也不是不可能。
- 第二：指针真的很不友好，知识点太多了，用不好就很容易出错。加上刚刚提到的那点，除非你用指针很小心，否则真的容易炸。
- ~~第三，因为我不会（迫真）~~
所以，我更加推崇字符串。因为我们输入的时候就是采用输入字符串的形式。把字符串放进子函数处理，再返回出来一个答案字符串，对于我们来说更加友好易懂方便。

于是我们定义一个 \text{string} 型的字符串。
```
string _minus(string a, string b)
{
    //代码
}
```
这样，如果要输出，我们直接输出 _\text{minus(a, b)} 即可。如果要重复运算也无妨，反正我们输进去是字符串形式，输出也是字符串，输出的字符串可以马上又作为下次运算的输入，没有繁琐的形式转化，完全可以应对复杂的处理。

那么这个子函数怎么写？

首先，我们所有的运算都是在子函数中进行的。在可能有多次运算的情况下，我们不选择把数组开成全局变量（开在函数外），开在外面共用数组可能会导致数字重复混淆。

当然你可以用开更多数组解决问题，但是既然这样，为何我们不选择开在函数内呢？

我先把代码扔下来：
```
#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
#define MAXN 10500 
using namespace std;
string a, b;

string _minus(string a, string b)
{
    int na[MAXN] = {0}, nb[MAXN] = {0}, ans[MAXN] = {0};
    string diff;

    if((a < b && a.size() <= b.size()) || b.size() > a.size())
        return "-" + _minus(b, a);

    for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0';
    for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0';

    int maxl = max(a.size(), b.size());

    for(int i = 1; i <= maxl; i ++)
    {
        if(na[i] < nb[i])
        {
            na[i + 1] --;
            na[i] += 10;
        }
        ans[i] = na[i] - nb[i];
    }
    while(ans[maxl] == 0)maxl --;//防止减后降位，多输出若干0
    if(maxl < 1)return "0";
    for(int i = maxl; i > 0; i --)diff += ans[i] + '0';//数组转化为字符串。 
    return diff;
}

int main()
{
    cin >> a >> b;
    cout << _minus(a, b);
    return 0;
}
```
可以看到：绝大多数，包括核心相减代码都没有变。

我们重点看下变化的部分。

1、数组

显而易见，我们把数组开在了里面。开在里面和开在全局变量有些不同，全局变量里的每个空间存的数默认为 0，但我不知道开在子函数里会不会影响，所以我还是初定义了一下。

如果写出 \text{a[MAXN]=0}，意思就是把 \text{a} 数组中的全部数设为 0。 这好像是 0 的特殊福利，因为如果是其他数，例如 \text{a[MAXN]=1}，\text{a} 数组只会把 \text{a[0]} 设为 1。

我们可以用已经定义好的数组继续运算。

2、字符串与返回值

由于我们函数设定的 \text{string} 类，所以返回值也必须是 \text{string}。

所以，我们在最后进行运算时，把普通的输出改成了数组转化为字符串。

呐，就是这句话：
```
string diff;//已经在子函数最上方定义
for(int i = maxl; i > 0; i --)diff += ans[i] + '0';//数组转化为字符串。 
return diff;
```
这句话的意思是，每次循环，就把 \text{a[i]} 转化为字符加到 \text{diff} 字符串的末尾。

我们把字符转化为数字时，由于 \text{ASCII} 码的存在，所以要减去 48 或 \text{'0'}。同理，数字转化为字符也需要加上 48 或 \text{'0'}。

最后，答案数组中的全部数字转化为字符，存在 \text{diff} 字符串中，直接返回出去。

3、\text{b>a} 与 \text{a-b=0} 的新写法

我们已经知道，在 \text{b>a} 和 \text{a-b=0} 这两种情况是要特判的。

①先聊聊 \text{b>a} 。我们一般处理方法是交换两数，在相减后最后在答案前打个负号。

交换两数目的是什么，无非就是把 \text{a-b} 变为 \text{b-a}。

我们现在就不用这种麻烦的方法了，我们现在有逼格十足的子函数！

既然你想要 \text{b-a}，行，子函数调用一遍 _\text{minus(b, a)}。在前面打上负号，直接 \text{return} 返回。

大概就是这么写：
```
if((a < b && a.size() <= b.size()) || b.size() > a.size())
    return "-" + _minus(b, a);
```
是不是比原来方便了很多？

②再论 \text{a-b=0}。 这个就很简单了，判断成立直接返回 0 即可，和原来的方法也相差无几
```
if(maxl < 1)return "0";
```
完整代码就是这个了：
```
#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
#define MAXN 10500 
using namespace std;
string a, b, c, d;

string _minus(string a, string b)
{
    int na[MAXN] = {0}, nb[MAXN] = {0}, ans[MAXN] = {0};
    string diff;

    if((a < b && a.size() <= b.size()) || b.size() > a.size())
        return "-" + _minus(b, a);

    for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] -     '0';
    for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] -     '0';

    int maxl = max(a.size(), b.size());

    for(int i = 1; i <= maxl; i ++)
    {
        if(na[i] < nb[i])
        {
            na[i + 1] --;
            na[i] += 10;
        }
        ans[i] = na[i] - nb[i];
    }
    while(ans[maxl] == 0)maxl --;//防止减后降位，多输出若干0
    if(maxl < 1)return "0";
    for(int i = maxl; i > 0; i --)diff += ans[i] + '0';//数组转化为字符串。 
    return diff;
}

int main()
{
    cin >> a >> b >> c >> d;
    cout << _minus(a, b) << endl;//直接调用
    cout << _minus(b, c) << endl;
    cout << _minus(c, d);
    //可以看到，这里不管算多少次，调用一下即可，非常方便 
    return 0;
}
```
100\% 数据满足 -10^{10086} \le a,b \le 10^{10086}

现在还有一个小小的拓展问题。

我们之前提到的“简单高精度”，它的数据范围并没有涉及 a,b < 0 的情况。一旦 a,b 出现负数，那么我们又无法处理了。

这时候，我们就需要借助高精度加法!

为什么高精度加法也掺和进来了.........

我们分3种情况讨论
- 1、a < 0 , b > 0 这种情况下，-a > 0 ，所以我们擦去 a 的负号，并使用 -a 运算，于是就有： - a - b = - (a + b)
- 2、a > 0 , b < 0 这种情况下，-b > 0 ，所以我们擦去 b 的负号，并使用 -b 运算，于是就有： a - (-b) = a + b （同上）
- 3、a < 0 , b < 0 这种情况下，-a > 0, -b > 0 ，所以我们擦去 a,b 的负号，并使用 -a, -b 运算，于是就有： - a - (-b) = b - a
有些人可能会说：使用 -a, -b 运算连正负都改变了，算出来肯定是错的啊？

其实不然。我们之前已经擦去了 a, b 的负号，也就是说我们已经把正负换过一遍了。 运算的时候我们不过换回来了而已。

可以看到，要解决上面三种情况，其中 1,2 情况都需要借助高精度加法。

假设 _\text{add(a, b)} 是高精度相加函数，上述情况可以这样写：
```
string a,b;
cin>>a>>b;
if(a[0]=='-'&&b[0]=='-')  //当两个数字为负数 
{
    a.erase(0,1);
    b.erase(0,1);//擦掉a,b打头的负号再运算，下同
    cout<<_minus(b,a);    //-a-(-b)=-a+b=b-a 
    return 0;
}
else if(a[0]=='-')  //只有a为负数 
{
    a.erase(0,1);
    cout<<"-"<<_add(a,b);  //-a-b=-(a+b)
    return 0;
}
else if(b[0]=='-')  //只有b为负数 
{
    b.erase(0,1);
    cout<<_add(a,b);  //a-(-b)=a+b 
    return 0;
}
else cout<<_minus(a,b);
```
当然，刚刚写的东西都是放在主函数里的。 其实可以写的更简便，代码更短，但是这样分层写要好理解一些。

顺带一提，\text{a.erase(0,1);} 是字符串的一种语句，作用是把 \text{a[0]} 的那个字符消掉。如果为负，自然那个符号就是负号了。\text{b} 也是同理。

而且，上面介绍的把运算开在子函数里也帮了我们大忙，可以在代码中看出来，可谓是方便快捷。

高精度加法我就不赘述了，方法其实和减法一样，竖式运算，只不过要注意最大位进位而已，其他就没什么好说的了。

于是，我们现在有了一个究极 \text{AC} 代码。
究极代码横空出世了！

#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
#define MAXN 10500 
using namespace std;
string a, b;

string _add(string a, string b)//高精度相加 (为底下a或b为负数相减做铺垫)这个都会吧。 
{
    string sum;
    int na[MAXN] = {0}, nb[MAXN] = {0}, ans[MAXN + 1] = {0}; 

    for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0';
    for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0';

    int maxl = max(a.size(), b.size());
    for(int i = 1; i <= maxl; i ++)
    {
        ans[i + 1] = (ans[i] + na[i] + nb[i]) / 10;
        ans[i] = (ans[i] + na[i] + nb[i]) % 10; 
    }//相加 
    if(ans[maxl + 1] != 0)sum += "1";//特判 防止最大位进位 
    for(int i = maxl;i > 0; i --)sum += ans[i]+'0';
    return sum;
}

string _minus(string a, string b)
{
    int na[MAXN] = {0}, nb[MAXN] = {0}, ans[MAXN] = {0};
    string diff;

    if((a < b && a.size() <= b.size()) || b.size() > a.size())
        return "-" + _minus(b, a);

    for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0';
    for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0';

    int maxl = max(a.size(), b.size());

    for(int i = 1; i <= maxl; i ++)
    {
        if(na[i] < nb[i])
        {
            na[i + 1] --;
            na[i] += 10;
        }
        ans[i] = na[i] - nb[i];
    }
    while(ans[maxl] == 0)maxl --;//防止减后降位，多输出若干0
    if(maxl < 1)return "0";
    for(int i = maxl; i > 0; i --)diff += ans[i] + '0';//数组转化为字符串。 
    return diff;
}

int main()
{
    string a,b;
    cin >> a >> b;
    if(a[0] == '-' && b[0] == '-')  //当两个数字为负数 
    {
        a.erase(0, 1);
        b.erase(0, 1);//擦掉a,b打头的负号再运算，下同
        cout << _minus(b,a);    //-a-(-b)=-a+b=b-a 
        return 0;
    }
    else if(a[0] == '-')  //只有a为负数 
    {
        a.erase(0, 1);
        cout << "-" << _add(a, b);  //-a-b=-(a+b)
        return 0;
    }
    else if(b[0] == '-')  //只有b为负数 
    {
        b.erase(0, 1);
        cout << _add(a, b);  //a-(-b)=a+b 
        return 0;
    } 
    else cout << _minus(a, b);
    return 0;
}

尾声

到这里，我要讲的也差不多讲完了。

这篇题解，前前后后码了有 3 个小时，包括查资料和写框架。希望我的努力对大家有帮助。

欢迎大家指正错误，改良算法。
\color{#FAFAFA}\colorbox{#FAFAFA}{当然也不排斥大家点赞哈哈哈}
你们的支持是我最大的动力！

\text{My Blog}

高精度减法的OP写法

高精度减法基础

高精度减法的 \text{OP} 写法

多重运算连击

更加便捷的操作

100\% 数据满足 -10^{10086} \le a,b \le 10^{10086}

究极代码横空出世了！

尾声

\text{My Blog}