题目描述

给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数

算法1

简述：

1. 不直接进行判断A，B大小
2. 将A,B看作无符号数进行计算
3. 直接执行A-B，通过最高位借位符c是否为1，判断是溢出（即差为负）
4. 设置全局变量ex,发生溢出时(c==1)修改ex值，并交换被减数和减数
5. 在输出时，查看全局变量ex的值，来确定是否输出-
6. 整个过程最多交换一次被减数和减数的位置

C++ 代码

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

//全局变量，判断是否交换被减数和减数
bool ex = false;                                

//高精度减法
vector<int> sub(vector<int> &A, vector<int> &B){

    vector<int> target;                         //目标向量
    int c = 0;                                  //借位符
    int i = 0;                                  //扫描指针

    while(i<A.size() || i<B.size()){

        //取A的每一位为被减数，且减去上一位的借位符
        //取B的每一位为减数
        int x = i >= A.size() ? 0 : A[i]-c;     
        int y = i >= B.size() ? 0 : B[i];

        if(x<y) c = 1;                          //若(被减数)<(减数)，则借位
        else    c = 0;                          //否则，不借位

        int dif = c*10 + x - y;                 //当前位差
        target.push_back(dif);                  //插入到目标向量
        i++;
    }

    //如果执行结束后，最高位借位符为1，则说明(被减数A)<(减数B)则交换
    if(1 == c){
        ex = true;                              //记录交换
        return sub(B, A);                       
    }

    //消除前置0
    while(target.size() > 1 && target.back() == 0) target.pop_back();
    return target;
}

int main(){

    //变量
    string a, b;
    vector<int> A, B, C;

    //输入
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    //执行
    C = sub(A,B);

    //输出
    if(true == ex) cout<<'-';
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    cout << endl;
    return 0;
}

如有错误，请大佬帮忙指正！