算法基础课笔记（三）

高精度减法：

例题：acwing.792. 高精度减法（模板题）

给定两个正整数，计算它们的差，计算结果可能为负数。

输入格式
共两行，每行包含一个整数。

输出格式
共一行，包含所求的差。

数据范围
1≤整数长度≤10^5
输入样例：
32
11
输出样例：
21

首先复习一下整数的笔算减法。

然后用数组来模拟笔算的过程。

 1 2 3
-  8 9
--------
   3 4   

对于A和B的每一位的减法计算，实际上是三个数Ai、Bi和t（借位）的差。

y总代码。

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

// 判断是否有 A >= B，A和B是反着存的，不能用string比较
bool cmp(vector<int> &A,vector<int> &B){
    if (A.size() != B.size()) return A.size() > B.size();
    // 从高位开始逐位判断
    for (int i = A.size()-1;i >= 0;i--){
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}
// C = A - B，A和B都是正整数，保证了 A >= B
vector<int> sub(vector<int> &A,vector<int> &B){
    vector<int> C;
    for (int i = 0,t = 0;i < A.size();i++){
        t = A[i] - t;
        if (i < B.size()) t -= B[i];// B的位数<=A的位数，需要判断是否存在
        C.push_back((t + 10) % 10);// 统一处理Ai-Bi-t大于等于0小于0的两种情况
        if (t < 0) t = 1;// <0借一位
        else t = 0;// 否则不借位
    }
    // 需要处理前导零，C至少是2位才可能出现前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main(){
    string a,b;
    vector<int> A,B;

    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');

    vector<int> C;
    if (cmp(A,B)){
        C = sub(A,B);
    }
    else{
       C = sub(B,A);
       printf("-");
    }
    for (int i = C.size()-1;i >= 0;i--) printf("%d",C[i]);

    return 0;
}

高精度乘法：

例题：acwing.793. 高精度乘法（模板题）

给定两个正整数 A 和 B，请你计算 A×B 的值。

输入格式
共两行，第一行包含整数 A，第二行包含整数 B。

输出格式
共一行，包含 A×B 的值。

数据范围
1≤A的长度≤100000,
0≤B≤10000
输入样例：
2
3
输出样例：
6

高精度乘法：大数A和小数b（位数小）运算。

把a看作一个整体，用A的每一位与b作乘法运算，得到C的每一位，最终结果就是答案。

高精度乘法和高精度加法类似。

y总代码。

#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
// C = A * b，A >= 0,b >= 0
vector<int> mul(vector<int> &A,int b){
    vector<int> C;
    for (int i = 0,t = 0;i < A.size() || t;i++){
        // 循环退出条件相比加法多了|| t，就不用额外判断最后的进位
        t += A[i]*b; // 理论上最好加上 if (i < A.size()) 判断，但是C++对数组越界检查不严格
        C.push_back(t % 10);
        t /= 10;
    }
    // 去除前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main(){
    vector<int> A;
    int b;
    string  a;
    
    cin >> a >> b;
    for (int i = a.size()-1;i >= 0;i--) A.push_back(a[i] - '0');
    auto C = mul(A,b);
    for (int i = C.size()-1;i >= 0;i--) printf("%d",C[i]);
    return 0;
}

高精度除法：

例题：acwing.794. 高精度除法（模板题）

给定两个非负整数 A，B，请你计算 A/B 的商和余数。

输入格式
共两行，第一行包含整数 A，第二行包含整数 B。

输出格式
共两行，第一行输出所求的商，第二行输出所求余数。

数据范围
1≤A的长度≤100000,
1≤B≤10000,
B 一定不为 0
输入样例：
7
2
输出样例：
3
1

高精度除法相对要复杂一点。

大数A和小数b（位数小）运算。

先回顾一下笔算除法。

y总代码。

#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
// A / b = C ... r,A >= 0,b > 0
vector<int> div(vector<int> &A,int b,int &r){
    vector<int> C;
    // 注意：除法是从高位开始计算的，和加减乘法不一样
    for (int i = A.size()-1;i >= 0;i--){
        r = r*10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(),C.end());// 计算得到的商是正着的，需要翻转一下低位从0开始
    // 因为C++的vector只能从back插入删除
    // 去除前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main(){
    vector<int> A;
    int b;
    string  a;
    
    cin >> a >> b;
    for (int i = a.size()-1;i >= 0;i--) A.push_back(a[i] - '0');
    
    int r = 0;
    auto C = div(A,b,r);
    for (int i = C.size()-1;i >= 0;i--) printf("%d",C[i]);
    puts("");
    printf("%d",r);
    return 0;
}