前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十四讲：数论【习题】
本篇博客所包含习题有：
👊最大比例
👊C 循环
👊正则问题
数论【例题】见博客：蓝桥杯第十四讲–数论【例题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
最大比例
来源： 第七届蓝桥杯省赛C++A/B组
题目要求
题目描述：
输入格式：
输出格式：
一个形如 A / B 的分数，要求 A 、B 互质，表示可能的最大比例系数。
数据范围：
输入样例1：
3 1250 200 32
输出样例1：
25/4
输入样例2：
4 3125 32 32 200
输出样例2：
5/2
输入样例3：
3 549755813888 524288 2
输出样例3：
4/1
思路分析
代码
#include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 110; int n; LL a[N], b[N], x[N]; LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } LL gcd_sub(LL a, LL b) { if (a < b) swap(a, b); if (b == 1) return a; return gcd_sub(b, a / b); } int main() { cin >> n; for (int i = 0; i < n; i ++ ) cin >> x[i]; sort(x, x + n); int cnt = 0; for (int i = 1; i < n; i ++ ) if (x[i] != x[i - 1]) { LL d = gcd(x[i], x[0]); a[cnt] = x[i] / d; b[cnt] = x[0] / d; cnt ++ ; } LL up = a[0], down = b[0]; for (int i = 1; i < cnt; i ++ ) { up = gcd_sub(up, a[i]); down = gcd_sub(down, b[i]); } cout << up << '/' << down << endl; return 0; }
C 循环
题目要求
题目描述：
对于 C 语言的循环语句，形如：
for (variable = A; variable != B; variable += C) statement;
请问在 k 位存储系统中循环几次才会结束。
若在有限次内结束，则输出循环次数。否则输出死循环。
输入格式：
多组数据，每组数据一行四个整数 A , B , C , k 。
读入以 0 00 0 结束。
输出格式：
若在有限次内结束，则输出循环次数。
否则输出FOREVER。
数据范围：
输入样例：
3 3 2 16 3 7 2 16 7 3 2 16 3 4 2 16 0 0 0 0
输出样例：
0 2 32766 FOREVER
思路分析
本题用到了 扩展欧几里得算法，具体原理可见博客：数学知识：扩展欧几里得算法
代码
#include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; LL exgcd(LL a, LL b, LL &x, LL &y) { if (b == 0) { x = 1, y = 0; return a; } LL d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int main() { LL a, b, c, k; while (cin >> a >> b >> c >> k, a || b || c || k) { LL x, y; LL z = 1ll << k; LL d = exgcd(c, z, x, y); if ((b - a) % d) cout << "FOREVER" << endl; else { x *= (b - a) / d; z /= d; cout << (x % z + z) % z << endl; } } return 0; }
正则问题
来源： 第八届蓝桥杯省赛C++A组,第八届蓝桥杯省赛JAVAA组
题目要求
题目描述：
输入格式：
一个由 x ( ) ∣ 组成的正则表达式。
输出格式：
输出所给正则表达式能接受的最长字符串的长度。
数据范围：
输入长度不超过 100 ，保证合法。
输入样例：
((xx|xxx)x|(x|xx))xx
输出样例：
6
思路分析
本图来自：https://www.acwing.com/user/myspace/index/1099/
网络异常，图片无法展示
|
代码
#include <cstring> #include <iostream> #include <algorithm> using namespace std; int k; string str; int dfs() { int res = 0; while (k < str.size()) { if (str[k] == '(') // 处理 (......) { k ++ ; // 跳过 '(' res += dfs(); k ++ ; // 跳过 ')' } else if (str[k] == '|') { k ++ ; // 跳过 '|' res = max(res, dfs()); } else if (str[k] == ')') break; else { k ++ ; // 跳过 'x' res ++ ; } } return res; } int main() { cin >> str; cout << dfs() << endl; return 0; }
