目錄

🌈前言：

📁 高精度的概念

📁 高精度加法和其模板

📁 高精度減法和其模板

📁 高精度乘法和其模板

📁 高精度除法和其模板

📁 總結(jié)

---

🌈前言：

? ? ? ? 這篇文章主要是準(zhǔn)備藍(lán)橋杯競(jìng)賽同學(xué)所寫，為你更好準(zhǔn)備藍(lán)橋杯比賽涉及的算法知識(shí)點(diǎn)。不知道你是否苦惱于不知算法從何學(xué)起，苦惱于網(wǎng)上資料稀少，或者復(fù)雜難懂，這篇文章就是幫助這部分同學(xué)的。

? ? ? ? 下面整理了藍(lán)橋杯考點(diǎn)大綱：
????????藍(lán)橋杯考點(diǎn)大綱

? ? ? ? 如果你對(duì)vecto數(shù)組r有興趣，也可以閱讀下面這篇文章，當(dāng)然沒了解vector數(shù)組也不影響閱讀本篇文章

和C++STL中vector的初次見面，vector常見用法和操作（零基礎(chǔ)/小白）-CSDN博客

? ? ? ? 上圖是大學(xué)C組需要掌握的，對(duì)于B組的同學(xué)也是需要向下掌握的。本文主要是幫助藍(lán)橋杯B/C為主體的大部分同學(xué)，所以講解相對(duì)基礎(chǔ)。本文是以C++為主要語言，但是C語言的同學(xué)也不需要擔(dān)心，大部分語法是相通的，只不過是加了STL內(nèi)容一個(gè)內(nèi)容，也是會(huì)進(jìn)行講解的。

? ? ? ? 因?yàn)檎Z法特性，變量等原因，對(duì)于JAVA，Python同學(xué)來說是不需要掌握高精度的。

? ? ? ? 同時(shí)本文將提供做題模板，方便你在考試中更好的做題，以及日常的刷題。

📁 高精度的概念

? ? ? ? 我們用C/C++創(chuàng)建變量時(shí)，變量類型是有取值范圍的，對(duì)于最常用unsigned int來說，它最多有-2147483648 ~?2147483647,即-(2^31)~(2^31-1），也就是說最多有31位, 那我們想存長(zhǎng)度為10^6的數(shù)呢，這是我們就不能用C/C++語法規(guī)定的變量來存儲(chǔ)了，我們就必須用數(shù)組來存儲(chǔ)。

? ? ? ? 總結(jié)一下，高精度就是通過數(shù)組模擬四則運(yùn)算來計(jì)算長(zhǎng)度非常長(zhǎng)的數(shù)字。

? ? ? ??本文只講解比較常見的四種高精度算法，如兩個(gè)高精度數(shù)相加，兩個(gè)高精度數(shù)相間，高精度數(shù)乘低精度數(shù)，高精度數(shù)除以低精度數(shù)。

? ? ? ? 通常來說，高精度灰常大，如10^6，低精度數(shù)10000以內(nèi)。

? ? ? ? 對(duì)于高精度數(shù)這么多位數(shù)來說，我們首先想到的是整數(shù)數(shù)組來存儲(chǔ)，可是有一個(gè)問題是存儲(chǔ)呢是從后往前存儲(chǔ)，還是從前往后存儲(chǔ)？比如123，下標(biāo)0是在1的位置，還是3的位置呢？

????????如果從1開始那么計(jì)算是否方便，很顯然這是不方便的，如果感興趣，可以自己嘗試一下?？墒菍?duì)于從3開始存儲(chǔ)，一開始我們?cè)趺磿?huì)知道他有多少位數(shù)呢？相信你一定知道數(shù)組還有一種叫做字符數(shù)組的，我們可以先將字符數(shù)字存儲(chǔ)在字符數(shù)組中，再將字符數(shù)字逆序存儲(chǔ)成整數(shù)數(shù)組中進(jìn)行計(jì)算，這樣大大減少了運(yùn)算時(shí)進(jìn)位的難度。（數(shù)組從前往后遍歷如果遇到進(jìn)位時(shí)，只需要下一個(gè)位置的數(shù)+1即可）

📁 高精度加法和其模板

? ? ? ? 我們首先來看一下，普通的加法怎么計(jì)算。

? ? ? ? 加法運(yùn)算就是從個(gè)位開始相加，相加大于10就向前進(jìn)1位，即向前一位+1。前面我們說了，高精度是通過數(shù)組來模擬計(jì)算的，如下圖所示。

? ? ? ? 通過上圖我們就可以得出模板：

vector<int> add(vector<int> A,vector<int> B)
{vector<int> C;int t = 0;    //t是進(jìn)位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;}

? ? ? ? 這里為了更好照顧C(jī)語言同學(xué)，講解一下什么是vector<int> , 可以理解為數(shù)組，每個(gè)元素類型是int，即整數(shù)數(shù)組。

? ? ? ? .size()可以理解為對(duì)數(shù)組的操作，求數(shù)組元素個(gè)數(shù)；.push_back()也是同理，向數(shù)組C插入元素的。

? ? ? ? 整體通讀一遍模板代碼，先創(chuàng)建數(shù)組C存儲(chǔ)結(jié)果，當(dāng)然是從個(gè)位先開始存儲(chǔ)的。t是進(jìn)位，如果Ai，Bi在i位置上有數(shù)，就加到t中，t就是相加結(jié)果，如果大于10，保留個(gè)位數(shù)，向前+1，t%10。

最后判斷最大位數(shù)相加是否向前進(jìn)1位，就是判斷t，這里t只能取到0或者1。

? ? ? ? 以上，我們就對(duì)高精度加法模板有了了解，下面我們展示完整代碼：

#include <iostream>
#include <vector>using namespace std;vector<int> add(vector<int> A, vector<int> B)
{vector<int> C;int t = 0;		//進(jìn)位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');            //將 字符數(shù)字 -> 整數(shù)數(shù)字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;
}

? ? ? ? 如果我們要使用vector數(shù)組的話，要引用頭文件。

📁 高精度減法和其模板

??????????????

? ? ? ? A-B，我們要分兩種情況，即A>=B,和 A < B；對(duì)于第1種情況，我們直接輸出A-B即可，對(duì)于第二種情況我們輸出 - (B - A);

? ? ? ? 對(duì)于模板，我們只需要確保A>=B即可。

vector<int> sub(vector<int> A,vector<int> B)
{vector<int> C;int t = 0;        //借位for(int i=0;i<A.size();i++){t = A[i] + t;if(i < B[i])t -= B[i];C.push_back((t + 10) % 10);if(t < 0)t = -1;elset = 0;    }while(C.size() > 1 && C.back() == 0)C.pop_back();return C;
}

? ? ? ?(t+10)%10,是為了保證減不開的情況，對(duì)于相減大于0的數(shù)不影響。

????????最后的while循環(huán)是為了保證一種情況，例如，127-120，在數(shù)組C中存儲(chǔ)的是300,最后打印007了，所以我們要將前面兩個(gè)0刪去，當(dāng)然如果是127-127，是要保留1個(gè)0的。

? ? ? ? 下面展示完整代碼：

? ? ? ? 當(dāng)然，我們下面還寫了一個(gè)函數(shù)check，作用就是判斷A是否大于等于B的。

#include <iostream>
#include <vector>using namespace std;bool check(vector<int> A, vector<int> B)
{if (A.size() > B.size())return true;for (int i = 0;i < A.size();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 t = 0;for (int i = 0;i < A.size();i++){t = A[i] + t;if (i < B.size())t -= B[i];C.push_back((t + 10) % 10);if (t < 0)t = -1;elset = 0;}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');if (check(A, B)){vector<int> C = sub(A, B);for (int i = C.size() - 1;i >= 0;i--)cout << C[i];}else{vector<int> C = sub(B, A);cout << '-';for (int i = C.size() - 1;i >= 0;i--)cout << C[i];}return 0;
}

📁 高精度乘法和其模板

? ? ? ? 下圖便是高精度與低精度整數(shù)想乘的運(yùn)算方式，將每一位數(shù)乘低精度數(shù)b + 上一位的進(jìn)位，余數(shù)就是這位上的數(shù)，進(jìn)位等于相除的結(jié)果。

? ? ? ? 得出模板為：

vector<int> mul(vector<int> A, int b)
{vector<int> C;int t = 0;for (int i = A.size() - 1;i >= 0 || t; i--){if(i < A.size())t += A[i] * b;C.push_back(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0)C.pop_back();return C;
}

? ? ? ? 當(dāng)然最后還是要保證A*0的話只能有1個(gè)0。

????????下面展示完整代碼：

#include <iostream>
#include <vector>using namespace std;vector<int> mul(vector<int> A, int b)
{vector<int> C;int t = 0;for (int i = A.size() - 1;i >= 0 || t; i--){if(i < A.size())t += A[i] * b;C.push_back(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0)C.pop_back();return C;
}int main()
{string a;cin >> a;int b;cin >> b;vector<int> A;for (int i = a.size() - 1;i >= 0;i--)A.push_back(a[i] - '0');vector<int> C = mul(A, b);for (int i = C.size() - 1;i >= 0;i--)cout << C[i];return 0;
}

📁 高精度除法和其模板

? ? ? ? 除法相對(duì)于上面三個(gè)有點(diǎn)不同，高精度數(shù)A是從最高位開始計(jì)算的，我們數(shù)組C存儲(chǔ)也是從最高位開始存儲(chǔ)，但是我們?yōu)榱撕蜕厦姹３忠恢?#xff0c;即輸出都是從后往前輸出，所以我們最后逆置數(shù)組。

? ? ? ? 這里為什么從0開始計(jì)算呢，是從1開始計(jì)算的，上一位的補(bǔ)下來是0，所以1/3=1，余數(shù)是1,，依次類推。理解了這里，高精度除法也就懂了。

? ? ? ? 下面展示模板：

vector<int> div(vector<int> A, int b, int& r)
{vector<int> C;for (int i = A.size()-1;i >=0;i--){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(),C.end());while (C.size() > 1 && C.back() == 0)C.pop_back();return C;
}

? ? ? ? reverse()函數(shù)就是將數(shù)組元素逆置，其中begin(),end()你可以先簡(jiǎn)單理解為首元素位置，尾元素位置，將這兩個(gè)參數(shù)傳給reverse函數(shù)。函數(shù)是包含在頭文件<algorithm>中

? ? ? ? 下面展示完整代碼：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<int> div(vector<int> A, int b, int& r)
{vector<int> C;for (int i = A.size()-1;i >=0;i--){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(),C.end());while (C.size() > 1 && C.back() == 0)C.pop_back();return C;
}int main()
{string a;cin >> a;int b;cin >> b;vector<int> A;for (int i = a.size() - 1;i >= 0;i--)A.push_back(a[i] - '0');int r = 0;vector<int> C = div(A,b,r);for (int i = C.size() - 1;i >= 0;i--)cout << C[i];cout << endl << r << endl;return 0;
}

? ? ? ??

📁 總結(jié)

????????以上，我們就對(duì)高精度在藍(lán)橋杯中的知識(shí)點(diǎn)進(jìn)行了講解，并針對(duì)性的講解了例題，當(dāng)然這也只是幫你更好的理解這些算法知識(shí)，想要學(xué)好算法，還需要不斷地刷題練習(xí)，這里推薦到洛谷，acwing等網(wǎng)站進(jìn)行練習(xí)，比如你看完了這篇文章，做回了例題習(xí)題，就可以上這些網(wǎng)站進(jìn)行想應(yīng)的練習(xí)。

? ? ? ? 如果你有哪里疑惑，歡迎在評(píng)論區(qū)留言，也歡迎大家指出文中錯(cuò)誤。最后，希望大家在評(píng)論區(qū)積極討論，點(diǎn)贊，收藏，關(guān)注ヾ(?ﾟ▽ﾟ)ノ