高精度加法,其实就是模拟我们普通算式的步骤,比如是267+58,首先个位相加,7 + 8 = 15 , 1给到十位(也就是进位),留下5,然后算十位,同样的步骤直到算完。通过这个步骤我们直到了我们每次循环(个位到十位到百位……)都需要一个t来充当进位,使用数组来存储或者使用vector(容器),我这里选择了vector,因为vector是不受下标控制的,感觉操作起来会比较简单。
还有一个需要注意的,如果我们用int来放数据,那么就需要用公式(获得百位十位个位),而且每一轮循环的公式都不一样,也就代表着我们可能需要几个变量来放各位数据,所以这里推荐用string来放题目给的数据,在计算的时候转变成int就好了(这里应该形成一个常识,题目如果有查询之类的字眼应该用string而不是char[],string某种程度等于char[],但是很多时候使用string比使用char[]好,如果给的是一个int数据,也可以使用string来放的,只要变成int就可以了)。
这里是代码:
#include <iostream> #include <vector> using namespace std; const int N = 100010;//其实N是为了数组,这里可以不用写的,但是我习惯了 //这里补充一下吧,其实我思考了一下,为什么不用int呢,因为我总觉得自己不能 //单独写出来,又重新写了一遍,一开始就在思考这个问题了 //如果是int,肯定要/和%吧,如果使用数组,那么就和输入不太符合,使用字符串 //,因为字符串同样可以使用数组的表达方法,而且字符串的char也可以通过-'0' //改成整数,然后我对c++的语法(比如c++和java一样有string类型我是有点惊讶的) //不太熟悉,嗯 //注意整体是倒着计算的 vector<int> add(vector<int> & A,vector<int> &B){ if(A.size() < B.size()) return add(B,A); 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; } if(t) C.push_back(t);//a = 123456 A=654321 ,后面的pushback,不是1,就是0 //也就是最高位的进位 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'); auto C = add(A,B); for(int i = C.size() - 1 ; i >= 0 ; i --) cout << C[i]; cout << endl; return 0; }
参考链接:AcWing 791. 高精度加法--海绵宝宝来喽 - AcWing(海绵大佬的题解有的话一定会看,我最喜欢他的背包问题的题解,从头讲到尾的清晰)
时间复杂度:数据规模n为最大位的数位次,只有一个循环,时间复杂度是O(n)。