前言
今天的主题是递归，主播给大家带来了递归的两道经典问题和一道比较偏向数学的题目。
带分数
分析
主播现在才发现其实以前做的很多“水题”并不是真正的“水题”，就比如这道题，要让主播写一个组合数主播肯定是能写出来的。这道题也很明显和组合数有关，但是主播最开始却并没有从组合数的角度去看待这道题，而是写的暴力，没有丝毫悬念超时了……
后来看了题解才发现大家都是先求组合数，随后在枚举划分区间求解的。主播认为这就是技巧，分析题目的技巧。
题目中要求1 ~ 9分别出现且只出现一次，这其实就是1 ~ 9的组合数。组合数的代码我给大家贴下来了，其实就是回溯的应用。
int dfs() //分类讨论放在哪里
{for(int i = 1; i <= 9; i++)if(!read[i]){read[i] = true;dfs();read[i] = false;}
}所有我们枚举组合数，随后用隔板法枚举每个区间的长度。
注意这里有一个小细节，按照题目的意思每一个部分都是没有0的，这其实也就是说每一部分都不是0。
代码
#include<iostream>
#include<vector>
using namespace std;
const int N = 10;
int n;bool read[N]; //每个位置有没有用
vector<int> vtr;int toInt(int l, int r)
{int cnt = 0;for(int i = l; i <= r; i++){cnt *= 10;cnt += vtr[i];}return cnt;
}int dfs() //分类讨论放在哪里
{int l = 0;if(vtr.size() == 9) //选完了{for(int i = 0; i < 8; i++)for(int j = i + 1; j < 8; j++){int x = toInt(0, i);int y = toInt(i + 1, j);int z = toInt(j + 1, 8);if(x * z + y == n * z) l++;}}else{for(int i = 1; i <= 9; i++){if(!read[i]){read[i] = true;vtr.push_back(i);l += dfs();read[i] = false;vtr.pop_back();}}}return l;
}int main()
{scanf("%d", &n);printf("%d", dfs());return 0;
}正则问题
分析
如果是工程上的话肯定就去写数字栈和符号栈和优先级表了，主包最开始也是这样想的，但是这是一道算法题，算法追求的是什么，快准狠啊。
所以主播毅然决然的放弃了栈写法，选择了递归……
递归写法和栈写法略有不同，原因在于递归更加的灵活，可以跳过栈的一些写法表示出来。
代码我就直接贴出来了，主播觉得比较难想的地方就是将字符串的加法分配给左括号，这应该也算是一种经验吧，主播最开始是想着将拼接供给右括号的，但是发现最终没有办法实现，至于为什么要分配给左括号是因为左括号可以更方便的处理拼接（主播认为其实左括号和右括号都可以，因为左括号方便处理而选择了左括号）
代码的思路是将括号和符号作为分界点，数字作为基本元素。
代码
/*中缀表达式运算
*/
#include<iostream>
#include<stack>
using namespace std;
const int N = 110;
char s[N];
int cnt = 0;
int dfs(char s[], int &cnt)
{int res = 0;while(s[cnt]){if(!s[cnt]) return 0;if(s[cnt] == '('){res += dfs(s, ++cnt);cnt++;}else if(s[cnt] == ')')break;else if(s[cnt] == '|')res = max(res, dfs(s, ++cnt));else{cnt++;res++;}}return res;
}int main()
{scanf("%s", s);printf("%d", dfs(s, cnt));return 0;
}有序分数
分析
这道题暴力的话是很好想的，我们枚举分子和分母，随后将分子分母互质的数字存起来，最后排序输出就可以了。
不过这不符合今天的主题，用递归怎么写呢？最开始主播百思不得其解，随后看了题解后才发现——这不是一道数学题吗？
我们是借助一种结构来解题的——[Stern-Brocot Tree]。
理论上可以计算出区间内所有的有理数，不过我们知道这基本上是不可能的，所以是理论上。原理是什么呢？
我们举个例子，比如[0, 1]的这个区间，表示成分数。
[0/1, 1/1]
随后分子加分子，分母加分母得到1/2，最后再用这个数划分区间，用分治去遍历左右两边。
[0/1, 1/2] [1/2, 1/1]
随后一直重复此操作进行下去，每次枚举的中间点就是区间内的一个有理数。
可能有的小伙伴发现了这不是一颗完全二叉树吗？既然是树，我们若想按照顺序遍历就要使用中序遍历。
对于本题来说我们限制一下分母的范围即可。
代码
// SBtree，一种可以遍历区间内所有有理数的算法
#include<iostream>
using namespace std;
int n;void dfs(int x1, int y1, int x2, int y2)
{if(y1 + y2 > n) return; dfs(x1, y1, x1 + x2, y1 + y2);printf("%d/%d\n", x1 + x2, y1 + y2);dfs(x1 + x2, y1 + y2, x2, y2);
}
int main()
{scanf("%d", &n);printf("%d/%d\n", 0, 1);dfs(0, 1, 1, 1);printf("%d/%d\n", 1, 1);return 0;
}