【蓝桥杯C组】备赛基础篇之高精度算法
一、高精度加法
思路:
运用vector数组(c选手可用len来记录数组长度,数组去保存数字)将存入字符串里面的数字符倒叙保存,按照小学的加法列式,相加保存进位即可。具体参考代码。
详细代码解析:
#include<iostream> #include<string> #include<vector> using namespace std; //数据名称太长后面又要经常用到它,所以直接给他取个小名,就相当于c中的define typedef vector<int> 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<iostream> #include<string> #include<vector> using namespace std; //数据名称太长后面又要经常用到它,所以直接给他取个小名,就相当于c中的define typedef vector<int> 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<iostream> #include<string> #include<vector> using namespace std; typedef vector<int> 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<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; typedef vector<int> 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; }
高精度算法在历年蓝桥杯中出现过,所以要掌握。