【蓝桥杯CC++组】备赛基础篇之高精度算法

⼀、⾼精度加法

思路：

运⽤vector数组（c选⼿可⽤len来记录数组长度，数组去保存数字）将存⼊字符串⾥⾯的数字符倒叙保存，按照⼩学的加法列式，相加保存进位即可。具体参考代码。

详细代码解析：#include#include#include

using namespace std;

//数据名称太长后⾯⼜要经常⽤到它，所以直接给他取个⼩名，就相当于c中的definetypedef vector vi;vi add(vi& a, vi& b) { vi c;//存结果的数组

for (int i = 0, t = 0;i < a.size() || i < b.size() || t;i++) {

//加法就是让所有的数字加到没有为⽌；还有保存进位的要储存到c中。 if (i < a.size()) t += a[i]; if (i < b.size()) t += b[i]; c.push_back(t % 10);

//每次存储个位，这也就解释了为什么条件要加⼀个t！=0，因为可能两个数字都加完了，还有进位的数字没有加进去。 t /= 10; } return c;}

int main() { vi a, b, c;

string str1, str2; cin >> str1 >> str2;

//倒序保存，注意字符与数字之间的转换。

for (int i = str1.size() - 1;i >= 0;i--) a.push_back(str1[i] - '0'); for (int i = str2.size() - 1;i >= 0;i--) b.push_back(str2[i] - '0'); c = add(a, b);

//倒序输出

for (int i = c.size() - 1;i >= 0;i--) cout << c[i]; return 0;}

⼆、⾼精度减法

思路：

运⽤竖式减法，⼤的减⼩的，⼩的减⼤的需要转换成⼤的减⼩的再天上负号；减不过就向后⼀个借1。

详细代码解析：#include#include#include

using namespace std;

//数据名称太长后⾯⼜要经常⽤到它，所以直接给他取个⼩名，就相当于c中的definetypedef vector vi;

bool cmp(vi& a, vi& b) {

//⽐较位数，位数⼤的数值肯定⼤。

if (a.size() != b.size()) return a.size() > b.size(); //位数相同，从⾼位往低位⽐较每个位置的数值。 for (int i = a.size() - 1;i >= 0;i--) if (a[i] != b[i]) return a[i] > b[i]; return true;}

void sub(vi& a, vi& b, vi& c) {

for (int i = 0, t = 0;i < a.size();i++) {

//a是⼤的数字，所以以a的位数作为结束 t += a[i];

//看看是否需要-1，前⽅的数值有⽊有借位。 if (i < b.size()) t -= b[i];

//看看是否还有b，有的话就相减 //没有的话直接存⼊位数中。 c.push_back((t + 10) % 10);

//加10模10防⽌a[i]⼩了，不够，减成了负号 if (t < 0) t = -1;

//t带了负号，说明借了位，变为-1记录借了位。 else t = 0;

//不是负号，初始化为0，什么事也没发⽣。 }

while (c.size() > 1 && !c.back()) c.pop_back(); //去掉前置零。}

int main() {

string str1, str2; vi a, b, c;

cin >> str1 >> str2;

//倒序保存

for (int i = str1.size() - 1;i >= 0;i--) a.push_back(str1[i] - '0'); for (int i = str2.size() - 1;i >= 0;i--) b.push_back(str2[i] - '0'); if (cmp(a, b)) sub(a, b, c);

//减不过，就只能添负号，让b-a。 else sub(b, a, c), cout << \"-\";

//倒序输出

for (int i = c.size() - 1;i >= 0;i--) cout << c[i]; return 0;}

三、⾼精度乘法

思路：

运⽤竖式法则的算法，由于这个算法是⾼精度乘以低精度，所以不⽤⼀个⼀个的乘，只需让⾼精度中的每⼀个数乘以整个低精度就⾏。

详细代码解析：#include#include#include

using namespace std;typedef vector vi;

vi mul(vi& a, int& b) { vi c;

for (int i = 0, t = 0;i < a.size() || t;i++) { if (i < a.size()) t += a[i] * b; c.push_back(t % 10); t /= 10; }

//处理前置零

while (c.size() > 1 && !c.back()) c.pop_back(); return c;}

int main() { string str; int b; vi a, c;

cin >> str >> b; //倒序存储

for (int i = str.size() - 1;i >= 0;i--) a.push_back(str[i] - '0'); c = mul(a, b); //倒序输出

for (int i = c.size() - 1;i >= 0;i--) cout << c[i];

return 0;}

四、⾼精度除法

思路：

标准除法运算，适合于 ⾼/低 。

详细代码解析：#include#include#include#includeusing namespace std;typedef vector vi;

vi div(vi& a, int& b, int& r) { vi c;

//由于除法是从⾼位开始计算，所以我们要倒序访问 for (int i = a.size() - 1;i >= 0;i--) {

r = r * 10 + a[i];//余数乘10+下⼀位数 c.push_back(r / b); r %= b;//余数2取模 }

//由于倒序访问，存储的结果也就是正序的，我们为了将其统⼀保存格式，所以要将他反过来。 //统⼀格式的话便于将四则运算联合起来⽤。 reverse(c.begin(), c.end());

while (c.size() > 1 && !c.back()) c.pop_back(); return c;}

int main() { int b, r = 0; string str; vi a, c;

cin >> str >> b;

for (int i = str.size() - 1;i >= 0;i--) a.push_back(str[i] - '0'); c = div(a, b, r);

for (int i = c.size() - 1;i >= 0;i--) cout << c[i]; cout << endl << r << endl; return 0;}

⾼精度算法在历年蓝桥杯中出现过，所以要掌握。