一、算法描述
高精度問(wèn)題是指兩個(gè)數(shù)字非常大，超過(guò)了int，甚至long long的范圍，數(shù)字的位數(shù)甚至能達(dá)到\(10^5\)，那么如果要實(shí)現(xiàn)這樣兩個(gè)大數(shù)字的運(yùn)算，需要解決以下兩個(gè)問(wèn)題：
如何存儲(chǔ)？
這樣的兩個(gè)數(shù)字相加是不可能用普通類型來(lái)存儲(chǔ)的，所以我們第一個(gè)要解決的問(wèn)題就是如何存儲(chǔ)高精度數(shù)。
-
首先讀入兩個(gè)高精度數(shù)一定是先讀入字符串，因?yàn)閯e的類型存儲(chǔ)不了，另外為了方便我們計(jì)算這兩個(gè)數(shù)，要轉(zhuǎn)化為用數(shù)組來(lái)存儲(chǔ)這兩個(gè)數(shù)。
-
由于普通的靜態(tài)數(shù)組是無(wú)法改變長(zhǎng)度的，這就導(dǎo)致初始長(zhǎng)度開(kāi)小了計(jì)算不了，開(kāi)大了會(huì)浪費(fèi)，所以我們采用一種可以變長(zhǎng)的數(shù)組
vector來(lái)存儲(chǔ)。 -
另外數(shù)組在前面操作不方便，而在尾部操作更加方便，所以逆序存儲(chǔ)數(shù)字，例如數(shù)字為 \(1234\) ，那么第 \(0\) 位應(yīng)該存儲(chǔ) \(4\) ，第 \(1\) 位應(yīng)該存儲(chǔ) \(3\) ，依此類推。
代碼如下：
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'); //注意逆序存儲(chǔ)
for (int i = b.size() - 1; i >= 0; --i) B.push_back(b[i] - '0');
如何計(jì)算？
解決了存儲(chǔ)問(wèn)題接下來(lái)就可以討論如何實(shí)現(xiàn)高精度的加法了。
-
其實(shí)高精度問(wèn)題就是一個(gè)模擬問(wèn)題，比如小學(xué)列豎式計(jì)算兩個(gè)數(shù)的加法，計(jì)算機(jī)就是在模擬這個(gè)過(guò)程。
-
遍歷兩個(gè)數(shù)組，只要沒(méi)有超過(guò)當(dāng)前數(shù)的位數(shù)，就加上當(dāng)前位數(shù)上的數(shù)，即，
t += A[i]或者t += B[i]，也別忘了加上剛計(jì)算的可能產(chǎn)生的進(jìn)位。 -
將這個(gè)計(jì)算出來(lái)的和模 \(10\) 后，
t % 10加入答案數(shù)組中，并除等于 \(10\) 表示下一位的進(jìn)位，t /= 10。 -
最后產(chǎn)生的一位進(jìn)位有可能超過(guò)這兩個(gè)高精度數(shù)的位數(shù)，也別忘了加入答案數(shù)組中。
-
這里函數(shù)傳參的時(shí)候使用的是引用傳遞，直接在原參數(shù)上操作，不會(huì)拷貝一份，用于提高效率。
經(jīng)過(guò)優(yōu)化之后代碼如下：
vector<int> add(vector<int> &A, vector<int> &B)
{
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);
return t;
}
二、題目描述
給定兩個(gè)正整數(shù)（不含前導(dǎo) \(0\)），計(jì)算它們的和。
輸入格式
共兩行，每行包含一個(gè)整數(shù)。
輸出格式
共一行，包含所求的和。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-711590.html
數(shù)據(jù)范圍
\(1≤整數(shù)長(zhǎng)度≤100000\)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-711590.html
輸入樣例：
12
23
輸出樣例：
35
三、題目來(lái)源
四、源代碼
#include <iostream>
#include <vector>
using namespace std;
const int N = 100010;
vector<int> add(vector<int> &A, vector<int> &B)
{
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);
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 = add(A, B);
for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
return 0;
}
到了這里，關(guān)于高精度加法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
