前言

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

---

1.高精度加法

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

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

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

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

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

下面是相關(guān)操作的代碼實現(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ù)分別從低位到高位存放到兩個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');

• 這個for循環(huán)便是相加的代碼，兩個if表示如果這個數(shù)的位數(shù)加完了，就停止加入tmp，判斷條件表示將tmp加完為止（也就是如果兩個數(shù)位數(shù)相同，最高位相加完后又進了一位，此時 tmp 為 1 并且不在加入數(shù)據(jù)，這個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;}

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

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

---

2.高精度減法

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

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

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

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

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

下面是相關(guān)操作的代碼實現(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兩個高精度數(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 這是因為：// 當(dāng)tmp<0時，說明這一位A的小于B的，因此要借位//    所以tmp+10后就相當(dāng)于借位后的數(shù)，%10后便是留在這一位的最終結(jié)果// 當(dāng)tmp>0時，說明這一位A的大于B的，盡管加了10//    但%10后加10與不加10是一樣的（可腦補一下）C.push_back((tmp + 10) % 10);// 如果tmp<0,表示這一位A的小于B的，因此將tmp置為1，下一次循環(huán)的第一步減去一if (tmp < 0) tmp = 1;else tmp = 0;}// 由于高位會出現(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é)完高精度加法和減法后，對于高精度乘法理解起來是很快的，這里我們規(guī)定，輸入的第一個數(shù)為高精度數(shù)，第二個數(shù)為int范圍內(nèi)的數(shù),并且兩個數(shù)都是正整數(shù)。

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

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

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

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

下面是相關(guān)操作的代碼實現(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的個位C.push_back(tmp % 10);// 丟棄個位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.高精度除法

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

• 對于整個相除的過程，肯定也是需要一個循環(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ù)為零，則這個表達式結(jié)果為0。

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

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

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

下面是相關(guān)操作的代碼實現(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 則會有余數(shù) ，所以下一次循環(huán)將這個余數(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());// 除法會出現(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)建一個變量r來儲存余數(shù)int b, r = 0;cin >> a >> b;// A用來儲存高精度數(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);// 打印還是與前面一樣，因為div中結(jié)果逆置了for (int i = C.size() - 1; i >= 0; i--) cout << C[i];// 這里打印余數(shù)cout << endl << r << endl;return 0;
}

代碼測試：

選取測試案例圖解：

輸入

128
8

輸出

16
0

寫在最后

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

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