【五十九】【算法分析与设计】高精度加法和高精度减法

高精度加法

高精度加法，也称为大数加法，是一种能够处理超过标准数据类型（如 int 或 long）允许范围的大数字的算法。

高精度数字通常无法使用单一的标准数据类型来存储。一个常见的方法是使用数组或字符串来表示每一位数字。例如，数字 "123456789" 可以被存储为一个数组 [1,2,3,4,5,6,7,8,9]。

迭代可以看作是只有递的递归。没有归的递归，不需要回溯，因此每个节点的信息，存放的是上个节点的信息。

节点信息，定义i表示当前a的下标，定义j表示当前b的下标，定义carry表示当前节点对应的进位，定义sum表示当前节点的累加和。

怎么判断有没有下一个节点，如何进入下一个节点。

我们的目标是填充c字符串，如果c字符串需要填充，那就进入下一个节点。

如何进去下一个节点，i--，j--即可，下一个节点对应a，b下一个位置。

static string add(const string& a, const string& b) { // 定义一个静态函数，接受两个字符串a和b，返回一个字符串
    string c; // 用于存储结果的字符串
    int sum = 0; // 当前位的总和（包括上一位的进位）
    int carry = 0; // 进位值
    int i = a.size() - 1; // 指向字符串a的最后一个字符的索引
    int j = b.size() - 1; // 指向字符串b的最后一个字符的索引
    while (i >= 0 || j >= 0 || sum / 10) { // 当任一字符串还有字符未处理，或者最高位有进位时循环
        int numa = i >= 0 ? a[i] - '0' : 0; // 从a中取出一个数字，如果i已经小于0，则取0
        int numb = j >= 0 ? b[j] - '0' : 0; // 从b中取出一个数字，如果j已经小于0，则取0
        carry = sum / 10; // 上一轮的和大于等于10，产生的进位
        sum = numa + numb + carry; // 计算当前总和
        c.push_back(sum % 10 + '0'); // 将当前总和的个位数转为字符后添加到结果字符串中

        i--, j--; // 移动索引到下一位
    }
    reverse(c.begin(), c.end()); // 反转字符串，因为数字是从最低位开始添加的，所以最终结果要反转过来
    return c; // 返回结果字符串
}

高精度减法

高精度减法，或称为大数减法，是计算机科学中用于处理超过标准数据类型限制的大数字相减的方法。

与高精度加法类似，大数通常使用数组或字符串来存储每一位数字。例如，数字 "987654321" 可以存储为数组 [9, 8, 7, 6, 5, 4, 3, 2, 1]，每个数组元素代表一位数字。

定义carry表示进位，定义sum表示当前累加和，定义i表示a字符串的下标，定义j表示b字符串的下标。

默认a>=b，如果a<b只需要计算b-a，然后在前面添加负号即可。

节点信息存放的上一个节点的信息。

where用于判断有没有下一个节点，要不要进入下一个节点。

i--，j--控制进入下一个节点。

怎么判断a字符串和b字符串的大小？

自定义一个compare函数用于判断，因为string内置的compare函数只能判断第一个不同的字符的大小，对于字符串长度相同的时候可以判断，但是如果字符串长度不同就不能进行判断。

如果a的长度大于b的长度，那么a一定大于b。

如果a的长度等于b的长度，那么用内置函数进行判断即可。

如果a的长度小于b的长度，a一定小于b。

封装subtract函数，如果a>=b，正常计算a-b，如果a<b，计算b-a的值，然后在前面添加负号。

减法操作计算完需要去掉尾部的'0'，否则反转之后会有前导0。

static string _subtract(const string& a, const string& b) { // 定义一个静态函数，用于处理a减b的操作（假设a大于b）
    string c; // 结果字符串
    int carry = 0; // 借位
    int sum = 0; // 当前位相减的结果，含借位
    int i = a.size() - 1; // 指向字符串a的最后一个字符的索引
    int j = b.size() - 1; // 指向字符串b的最后一个字符的索引
    while (i >= 0 || j >= 0) { // 当任一字符串还有字符未处理时循环
        carry = sum < 0 ? -1 : 0; // 根据上一位的结果决定是否需要借位
        int numa = i >= 0 ? a[i] - '0' : 0; // 从a中取出一个数字，如果i已经小于0，则取0
        int numb = j >= 0 ? b[j] - '0' : 0; // 从b中取出一个数字，如果j已经小于0，则取0
        sum = carry + numa - numb; // 计算当前位的结果，含借位

        c.push_back(sum < 0 ? sum + 10 + '0' : sum + '0'); // 处理借位，将结果字符添加到结果字符串中
        i--, j--; // 移动索引到下一位
    }
    while (c.size() > 0 && c.back() == '0') c.pop_back(); // 去除结果字符串末尾的所有'0'
    if (c.size() == 0) c.push_back('0'); // 如果结果字符串为空，则添加'0'（结果为0）
    reverse(c.begin(), c.end()); // 反转字符串，因为数字是从最低位开始添加的，所以最终结果要反转过来
    return c; // 返回结果字符串
}
static string subtract(const string& a, const string& b) { // 定义一个静态函数，用于返回两个字符串a和b的相减结果
    if (compare(a, b) == 1) return _subtract(a, b); // 如果a大于b，直接计算a减b
    else return "-" + _subtract(b, a); // 如果b大于或等于a，计算b减a并在结果前加负号
}
static int compare(const string& a, const string& b) { // 定义一个静态函数，用于比较两个字符串的大小
    if (a.size() > b.size()) return 1; // 如果a的长度大于b的长度，返回1（a大于b）
    else if (a.size() == b.size()) return a.compare(b) == -1 ? -1 : 1; // 如果长度相同，使用字符串比较，返回比较结果
    else return -1; // 如果a的长度小于b的长度，返回-1（a小于b）
}