目錄
??前言：
?? 高精度的概念
?? 高精度加法和其模板
?? 高精度減法和其模板
?? 高精度乘法和其模板
?? 高精度除法和其模板
?? 總結(jié)
??前言：
? ? ? ? 這篇文章主要是準(zhǔn)備藍(lán)橋杯競賽同學(xué)所寫，為你更好準(zhǔn)備藍(lán)橋杯比賽涉及的算法知識點(diǎn)。不知道你是否苦惱于不知算法從何學(xué)起，苦惱于網(wǎng)上資料稀少，或者復(fù)雜難懂，這篇文章就是幫助這部分同學(xué)的。? ? ? ? 下面整理了藍(lán)橋杯考點(diǎn)大綱：
????????藍(lán)橋杯考點(diǎn)大綱? ? ? ? 如果你對vecto數(shù)組r有興趣，也可以閱讀下面這篇文章，當(dāng)然沒了解vector數(shù)組也不影響閱讀本篇文章
和C++STL中vector的初次見面，vector常見用法和操作（零基礎(chǔ)/小白）-CSDN博客
? ? ? ? 上圖是大學(xué)C組需要掌握的，對于B組的同學(xué)也是需要向下掌握的。本文主要是幫助藍(lán)橋杯B/C為主體的大部分同學(xué)，所以講解相對基礎(chǔ)。本文是以C++為主要語言，但是C語言的同學(xué)也不需要擔(dān)心，大部分語法是相通的，只不過是加了STL內(nèi)容一個(gè)內(nèi)容，也是會(huì)進(jìn)行講解的。
? ? ? ? 因?yàn)檎Z法特性，變量等原因，對于JAVA，Python同學(xué)來說是不需要掌握高精度的。
? ? ? ? 同時(shí)本文將提供做題模板，方便你在考試中更好的做題，以及日常的刷題。
?? 高精度的概念
? ? ? ? 我們用C/C++創(chuàng)建變量時(shí)，變量類型是有取值范圍的，對于最常用unsigned int來說，它最多有-2147483648 ~?2147483647,即-(2^31)~(2^31-1），也就是說最多有31位, 那我們想存長度為10^6的數(shù)呢，這是我們就不能用C/C++語法規(guī)定的變量來存儲(chǔ)了，我們就必須用數(shù)組來存儲(chǔ)。
? ? ? ? 總結(jié)一下，高精度就是通過數(shù)組模擬四則運(yùn)算來計(jì)算長度非常長的數(shù)字。
? ? ? ??本文只講解比較常見的四種高精度算法，如兩個(gè)高精度數(shù)相加，兩個(gè)高精度數(shù)相間，高精度數(shù)乘低精度數(shù)，高精度數(shù)除以低精度數(shù)。
? ? ? ? 通常來說，高精度灰常大，如10^6，低精度數(shù)10000以內(nèi)。
? ? ? ? 對于高精度數(shù)這么多位數(shù)來說，我們首先想到的是整數(shù)數(shù)組來存儲(chǔ)，可是有一個(gè)問題是存儲(chǔ)呢是從后往前存儲(chǔ)，還是從前往后存儲(chǔ)？比如123，下標(biāo)0是在1的位置，還是3的位置呢？
????????如果從1開始那么計(jì)算是否方便，很顯然這是不方便的，如果感興趣，可以自己嘗試一下?？墒菍τ趶?開始存儲(chǔ)，一開始我們怎么會(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()可以理解為對數(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。
? ? ? ? 以上，我們就對高精度加法模板有了了解，下面我們展示完整代碼：
#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；對于第1種情況，我們直接輸出A-B即可，對于第二種情況我們輸出 - (B - A);
? ? ? ? 對于模板，我們只需要確保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;
else
t = 0;
}
while(C.size() > 1 && C.back() == 0)
C.pop_back();
return C;
}? ? ? ?(t+10)%10,是為了保證減不開的情況，對于相減大于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;
else
t = 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;
}?? 高精度除法和其模板
? ? ? ? 除法相對于上面三個(gè)有點(diǎn)不同，高精度數(shù)A是從最高位開始計(jì)算的，我們數(shù)組C存儲(chǔ)也是從最高位開始存儲(chǔ)，但是我們?yōu)榱撕蜕厦姹３忠恢?，即輸出都是從后往前輸出，所以我們最后逆置?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()你可以先簡單理解為首元素位置，尾元素位置，將這兩個(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é)
????????以上，我們就對高精度在藍(lán)橋杯中的知識點(diǎn)進(jìn)行了講解，并針對性的講解了例題，當(dāng)然這也只是幫你更好的理解這些算法知識，想要學(xué)好算法，還需要不斷地刷題練習(xí)，這里推薦到洛谷，acwing等網(wǎng)站進(jìn)行練習(xí)，比如你看完了這篇文章，做回了例題習(xí)題，就可以上這些網(wǎng)站進(jìn)行想應(yīng)的練習(xí)。
? ? ? ? 如果你有哪里疑惑，歡迎在評論區(qū)留言，也歡迎大家指出文中錯(cuò)誤。最后，希望大家在評論區(qū)積極討論，點(diǎn)贊，收藏，關(guān)注ヾ(??▽?)ノ文章來源：http://www.zghlxwxcb.cn/news/detail-801264.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-801264.html
到了這里，關(guān)于藍(lán)橋杯備賽 day 3 —— 高精度（C/C++，零基礎(chǔ)，配圖）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
