前言

• 當(dāng)我們在利用計(jì)算機(jī)進(jìn)行一些計(jì)算時(shí)，可能會(huì)遇到這類問題 ： 有些計(jì)算要求精度高，希望計(jì)算的數(shù)的位數(shù)可達(dá)幾十位甚至幾百位，雖然計(jì)算機(jī)的計(jì)算精度也算較高了，但因受到硬件的限制，往往達(dá)不到實(shí)際問題所要求的精度。
• 這時(shí)我們就可以通過程序設(shè)計(jì)來解決這類問題，例如：創(chuàng)建一個(gè)數(shù)組，通過數(shù)組來存放高精度數(shù)的每一位上的數(shù)。

---

1.高精度加法

• 高精度加法是兩個(gè)位數(shù)很大的兩個(gè)數(shù)相加，例如1234567898756432123456789 + 66666666666666666666666，這時(shí)候我們用平常的整型或者長整型去存放數(shù)據(jù)都是會(huì)溢出導(dǎo)致數(shù)據(jù)丟失的，所以此時(shí)我們可以用一個(gè)數(shù)組來存放每個(gè)數(shù)相對(duì)應(yīng)位上的數(shù)（使用vector<int>， 假設(shè)這兩個(gè)高精度數(shù)都大于0）。

• 不過在C++中，直接將數(shù)輸入到vector中是不可取的，并且加法是從兩個(gè)數(shù)的低位開始相加一直加到高位，如果我們正常輸入從高位開始存放的話，對(duì)于后面程序的設(shè)計(jì)是不方便的，所以這里我們用string來表示相應(yīng)高精度數(shù)，然后將這個(gè)string從低位開始轉(zhuǎn)化成整數(shù)依次存放在vector<int>當(dāng)中，這樣兩個(gè)vector<int>就是我們想要的高精度數(shù)了。

• 同時(shí)我們需要另一個(gè)vector<int>來存放相加后的數(shù)，由于相加數(shù)的存放是倒著的，所以最終的結(jié)果也是倒著存放在vector<int>中的，此時(shí)打印就需要從后面往前面打印輸出。

• 加法不難，但要注意的是，如何在程序中表示進(jìn)位，我們都知道，每一位數(shù)相加超過10就要進(jìn)位1，表示這一位的前一位要+1。3和5相加為8不用進(jìn)位，而7和8相加要進(jìn)位，最后在這一位留下來的是（7 + 8）- 10 = 5，在程序中可以表示為（7 + 8）% 10。而這個(gè)%10就顯得格外重要了，如果你相加后的數(shù)小于10，它%10后，還是它本身，如果大于10，它就相當(dāng)于去掉一個(gè)10，剩下的數(shù)就放進(jìn)表示最終答案的vector<int>。

• 最后要注意的是，兩個(gè)位上的數(shù)相加后的結(jié)果要/=10,這是表示要除去這一位該留下的結(jié)果以及得到需要進(jìn)的位，例如：7 + 8 = 15 ，在該位應(yīng)該留下的最終結(jié)果為 15 % 10 = 5，最后 15 /= 10 得到1，表示要進(jìn)位1，該位的結(jié)果5除去。

下面是相關(guān)操作的代碼實(shí)現(xiàn)：

#include <iostream>
#include <vector>using namespace std;vector<int> add(vector<int>& A, vector<int>& B)
{vector<int> C;int tmp = 0;for (int i = 0; i < A.size() || i < B.size() || tmp; i++){if (i < A.size()) tmp += A[i];if (i < B.size()) tmp += B[i];C.push_back(tmp % 10);tmp /= 10;}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');auto C = add(A, B);for (int i = C.size() - 1; i >= 0; i--) cout << C[i];cout << endl;return 0;
}

代碼測試：

代碼細(xì)節(jié)解釋：

• 這里是將高精度數(shù)分別從低位到高位存放到兩個(gè)vector<int>中；

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

• 這個(gè)for循環(huán)便是相加的代碼，兩個(gè)if表示如果這個(gè)數(shù)的位數(shù)加完了，就停止加入tmp，判斷條件表示將tmp加完為止（也就是如果兩個(gè)數(shù)位數(shù)相同，最高位相加完后又進(jìn)了一位，此時(shí) tmp 為 1 并且不在加入數(shù)據(jù)，這個(gè)1 也是有效位，因此需要加入C中）

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

• 這個(gè)while表示去掉前導(dǎo)0，雖然加法不會(huì)出現(xiàn)前導(dǎo)0的情況，但不排除輸入的數(shù)據(jù)都為0的情況。

	while (C.size() > 1 && C.back() == 0) C.pop_back();

---

2.高精度減法

• 高精度減法是兩個(gè)很高位數(shù)的數(shù)相減，值得注意的是，減法需要借位，并且相減會(huì)出現(xiàn)結(jié)果為正還是負(fù)的情況，因此，高精度減法的程序比高精度加法的程序稍復(fù)雜。

• 對(duì)于結(jié)果是正還是負(fù)的情況，我們可以寫一個(gè)cmp函數(shù)對(duì)存放兩個(gè)高精度數(shù)的string進(jìn)行比較，然后規(guī)定sub函數(shù)第一個(gè)參數(shù)為大的那個(gè)數(shù)，我們只要將大的那個(gè)傳入第一個(gè)參數(shù)即可。如果是第二個(gè)輸入的高精度數(shù)較大，在打印結(jié)果的時(shí)候先打印一個(gè)‘ - ’即可。

• 在進(jìn)行相減的時(shí)候，我們可以先定義一個(gè)標(biāo)記借位的變量tmp(初始化為0)，如果一位上相減為負(fù)數(shù)，說明需要向前借一位，所以在減的循環(huán)中第一條語句可以為：tmp = big[i] - tmp;，如果結(jié)果小于零，將tmp置為1，等進(jìn)入下一次循環(huán)，第一條語句就自動(dòng)減一，起到借位的效果。

• 那么結(jié)果小于0，我們該如何確定這一位的最終答案呢？我們只需要在push_back時(shí)，里面的參數(shù)設(shè)為（tmp + 10）% 10,這樣就可以處理tmp所有的情況了（詳細(xì)點(diǎn)看代碼注釋）。

• 由于我們是通過將高精度數(shù)的每一位存入數(shù)組來計(jì)算的，并且減法會(huì)出現(xiàn)最高位依次連續(xù)是0的情況，因此作為答案的數(shù)組，高位可能存放有0，在打印的時(shí)候這些0都會(huì)被打印出來，所以這里要有刪去高位0的操作。

下面是相關(guān)操作的代碼實(shí)現(xiàn)：

#include <iostream>
#include <vector>
using namespace std;bool cmp(vector<int>& A, vector<int>& B)
{if (A.size() != B.size()) return A.size() > B.size();// 這一步說明A，B兩個(gè)高精度數(shù)長度相等，此時(shí)從最高位依次比較for (int i = A.size() - 1; i >= 0; i--)if (A[i] != B[i])return A[i] > B[i];return true;
}vector<int> sub(vector<int>& A, vector<int>& B)
{vector<int> C;int tmp = 0; // 用來標(biāo)記借位// 這里A要大，所以 i < A.size()for (int i = 0; i < A.size(); i++){tmp = A[i] - tmp; // 表示上一步有沒有借位if (i < B.size()) tmp -= B[i];// (tmp + 10) % 10 這是因?yàn)?#xff1a;// 當(dāng)tmp<0時(shí)，說明這一位A的小于B的，因此要借位//    所以tmp+10后就相當(dāng)于借位后的數(shù)，%10后便是留在這一位的最終結(jié)果// 當(dāng)tmp>0時(shí)，說明這一位A的大于B的，盡管加了10//    但%10后加10與不加10是一樣的（可腦補(bǔ)一下）C.push_back((tmp + 10) % 10);// 如果tmp<0,表示這一位A的小于B的，因此將tmp置為1，下一次循環(huán)的第一步減去一if (tmp < 0) tmp = 1;else tmp = 0;}// 由于高位會(huì)出現(xiàn)0的情況(22226 - 22223 = 3)，所以這里要去前導(dǎo)0while (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');if (cmp(A, B)){auto C = sub(A, B);for (int i = C.size() - 1; i >= 0; i--) cout << C[i];}else{auto C = sub(B, A);cout << '-';for (int i = C.size() - 1; i >= 0; i--) cout << C[i];}return 0;
}

代碼測試：

3.高精度乘法

• 在學(xué)完高精度加法和減法后，對(duì)于高精度乘法理解起來是很快的，這里我們規(guī)定，輸入的第一個(gè)數(shù)為高精度數(shù)，第二個(gè)數(shù)為int范圍內(nèi)的數(shù),并且兩個(gè)數(shù)都是正整數(shù)。

• 有了上面的規(guī)定，接下來的操作就簡單了，我們只需要關(guān)注如何乘，如何push,以及去前導(dǎo)0即可。

• 相乘前的準(zhǔn)備與高精度加減類似，只不過輸入的其中一個(gè)參數(shù)變?yōu)榱?code>int 。

• 整個(gè)相乘的過程：定義一個(gè)tmp ，將高精度數(shù)的每一位與int數(shù)相乘加入tmp(每一次循環(huán)將每一位相乘后的結(jié)果加入tmp)，然后每一次循環(huán)中，將tmp%10（每次取出個(gè)位上的數(shù)）push_back，再tmp/=10丟掉個(gè)位上的數(shù)，直到高精度的每一位數(shù)都乘過或者tmp為0循環(huán)結(jié)束，這樣就完成了高精度的乘法。

• 如果輸入的兩個(gè)數(shù)有0，那么結(jié)果終究會(huì)是0，所以高精度乘法也要有去除前導(dǎo)零的操作。

下面是相關(guān)操作的代碼實(shí)現(xiàn)：

#include <iostream>
#include <vector>using namespace std;vector<int> mul(vector<int>& A, int b)
{vector<int> C;int tmp = 0;for (int i = 0; i < A.size() || tmp; i++){// 如果A沒有遍歷完就一直將每一位與b相乘加入tmpif (i < A.size()) tmp += A[i] * b;// （tmp % 10）是push tmp的個(gè)位C.push_back(tmp % 10);// 丟棄個(gè)位tmp /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a;int b, flag = 1;cin >> a >> b;vector<int> A;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--) cout << C[i];return 0;
}

代碼測試：

選取測試案例圖解：

4.高精度除法

• 高精度除法與高精度乘法相比，多了一個(gè)變量r用來儲(chǔ)存余數(shù)，其余的輸入與乘法相同，但最后輸出要把r打印。同樣的，這里我們規(guī)定，兩個(gè)數(shù)都是正整數(shù)，并且int范圍內(nèi)的那個(gè)數(shù)不能為0(一個(gè)高精度數(shù)除以一個(gè)int范圍內(nèi)的整數(shù))。

• 對(duì)于整個(gè)相除的過程，肯定也是需要一個(gè)循環(huán)的。我們都知道，每一位相處的余數(shù)，都要相當(dāng)于乘以10與下一位相加，由于r初始為0,因此循環(huán)的第一句可以寫為r = r * 10 + A[i] ,A[i]為當(dāng)前位的數(shù)，r*10表示上一位數(shù)相除得到的余數(shù)，如果上一位數(shù)余數(shù)為零，則這個(gè)表達(dá)式結(jié)果為0。

• 執(zhí)行完上一條語句后便得到了被除數(shù)，此時(shí)就可以push:r / 除數(shù)，表示當(dāng)前位的結(jié)果，最后再r %= 除數(shù) 除去除完的除數(shù)，這樣整個(gè)過程就設(shè)計(jì)完成了。

• 由于main函數(shù)打印正確答案是從尾開始將每一位打印到頭的，并且正確答案是由高位到低位從數(shù)組的頭依次存放的，因此下一步需要逆置一下結(jié)果數(shù)組。

• 最后，除法會(huì)有高位為0的情況,因此還要有一步去除前導(dǎo)0的操作。

下面是相關(guān)操作的代碼實(shí)現(xiàn)：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 要改變main函數(shù)里的余數(shù)r，因此要引用
vector<int> div(vector<int>& A, int b, int& r)
{vector<int> C;// 根據(jù)除法的過程，從高位開始除for (int i = A.size() - 1; i >= 0; i--){// r開始為0，則第一次循環(huán)就為A的最高位與b相除// 如果 r>b 則會(huì)有余數(shù) ，所以下一次循環(huán)將這個(gè)余數(shù) 乘以10+A[i] 便是第二次循環(huán)要除的數(shù)// 如果 r<b 則余數(shù)就是r本身，第三條語句 r%=b 就相當(dāng)于沒執(zhí)行過r = r * 10 + A[i];C.push_back(r / b); // push 這一次除b的結(jié)果，如果r<b，則push:0r %= b;}// 由于得到的結(jié)果是從高位向低位開始存的，所以這里逆置一下，便于去除前導(dǎo)0reverse(C.begin(), C.end());// 除法會(huì)出現(xiàn)0的情況，因此這里要處理前導(dǎo)0while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a;// b為int范圍內(nèi)的數(shù)// 創(chuàng)建一個(gè)變量r來儲(chǔ)存余數(shù)int b, r = 0;cin >> a >> b;// A用來儲(chǔ)存高精度數(shù)vector<int> A;for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');auto C = div(A, b, r);// 打印還是與前面一樣，因?yàn)閐iv中結(jié)果逆置了for (int i = C.size() - 1; i >= 0; i--) cout << C[i];// 這里打印余數(shù)cout << endl << r << endl;return 0;
}

代碼測試：

選取測試案例圖解：

輸入

128
8

輸出

16
0

寫在最后

上述可以說都是高精度計(jì)算的基礎(chǔ)模板，實(shí)際上在很多題目中都可以用到這一模板，比如某些鏈表的題。所以我們要增強(qiáng)對(duì)這一類模板的熟練度，以便在后面的刷題中遇到能用此模板解決的問題能夠想起來有這一模板可以用。

感謝閱讀本小白的博客，錯(cuò)誤的地方請嚴(yán)厲指出噢！