(坚持每天写算法)基础算法复习与学习part1基础算法1-7——高精度减法(处理t=1和t>1代码的写法,t为操作次数)

发布时间 2024-01-13 17:28:14作者: 程序计算机人

  题目:

  思路:这一道题其实和高精度加法的思路是差不多的,都是使用算式进行模拟。

  重点:关于代码怎么写,在高精度加法那里还看不太出来(我也没有写),但是在高精度减法这里就完全可以看出来了。我们在加法算式里面,一般是A[i]+B[i]+t,但是也可以这么写:t+A[i]+B[i],我们可以先写进位,然后之后对进位t进行处理就行了,而在刚开始的时候我们只要将t设置成0就可以了,0没有进位为0,那么t+A[i]+B[i]就是通用的式子,所以高精度加法可以这么写: 

 vector<int> C;
 int t = 0 ;
 for(int i = 0 ; i < A.size() || i <B.size(); i ++){
     if(i < A.size()) t += A[i];
     if(i < B.size()) t += B[i];
     C.push_back(t % 10);
     t /= 10;
 }

  那么在高精度加法里面也可以是同个思路,我们一般是A[i]-B[i]-t,但是我们可以换成:A[i]-t-B[i],在刚开始我们将借位t设为0即可,而我们的借位是怎么来的呢?就是在每一轮中(A[i]-t-B[i])<0我们的t就会变换,所以我们的代码可以这么写:

vector<int> C;
int t = 0;
    
for(int i = 0 ; i < A.size() || i < B.size() ; i ++){
    t = A[i] - t;
    if(i < B.size() ) t -= B[i];
    C.push_back((t + 10) % 10 );
    if(t < 0) t = 1;
    else t = 0;//if-else是为了借位
}

  (注意,接下来一段由于没有图很难理解相当于自言自语,可以不用观看)

  在得出通用式子,或者想要想要获得通用情况的时候,往往需要处理第一次情况,在这个例子里面就是将t设置为0,类似的处理还有:如果第一次和之后的流程不一样,直接用if来特指第一种情况;如果某变量在整个过程都需要更新尤其需要在第一次赋值更新,那么使用for条件筛选掉第一次情况在for后面添加第一次情况即可。(很抽象,如果遇到了那种代码,这里还会更新的)

  在上面A[i]-t-B[i]的思路里,我们都是默认A大于B,如果是类似于5-23或者23-24这种就要将A和B的地位互换了,这里是图解:

   这里是代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

//虽然说本题目的减法借位可以做出来,但是我按照A.size() - B.size() 然后分别做出来的数不是一样的,只要位数太大了,那么我的代码就会失败
//所以反而是cmp函数需要注意
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;//等于的话也要true
}


vector<int> sub (vector<int>&A , vector<int>&B ){//别忘了地址符
    vector<int> C;
    int t = 0;

    for(int i = 0 ; i < A.size() || i < B.size() ; i ++){
        t = A[i] - t;
        if(i < B.size() ) t -= B[i];
        C.push_back((t + 10) % 10 );
        if(t < 0) t = 1;
        else t = 0;//if-else是为了借位
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main(){
    string a , b;
    cin >> a >> b;

    vector<int> 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), cout << '-';

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;
    return 0;

}

  补充:关于为什么要将A,B的数字反着存储这件事情,因为我们常见的数组(数据结构,vector也算)都是从左往右算(这里不考虑队列可以使用头插法),而算式是从右往左算,故将A,B的数字反着存储。

  时间复杂度:观察一下代码,发现还是取决于A的位数,核心代码只有一个循环,无递归,如果A的位数是n,那么时间复杂度就是O(n)。