前言
今天的主题是递归，主播给大家带来了递归的两道经典问题和一道比较偏向数学的题目。
带分数
分析
主播现在才发现其实以前做的很多“水题”并不是真正的“水题”，就比如这道题，要让主播写一个组合数主播肯定是能写出来的。这道题也很明显和组合数有关，但是主播最开始却并没有从组合数的角度去看待这道题，而是写的暴力，没有丝毫悬念超时了……
后来看了题解才发现大家都是先求组合数，随后在枚举划分区间求解的。主播认为这就是技巧，分析题目的技巧。
题目中要求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;
}