猫史档案馆

       

大家好！这里是Kitten进阶教程与实战的第三期。相信跟着爵士来，大家的Kitten创作水平会大大提高。

我们将在这些教程里学习一些适合进阶深造的算法和技巧。

我今（明（后（此处可看见爵士的鸽性）））天终于能够介绍搜索了！恭喜大家不用d喵我了（逃

注：已调大文字响应护眼活动

 

       

       还记得第二期讲的函数吗？不记得了建议回去再看一遍（）

       今天我们讲递归和栈。

 

 

                目录

       递归

       应用实例

       数据结构：栈

       表达式求值

 

 

       一、递归

       

       递归，即自己调用自己，通常用函数实现。

 

       对于一个待求解的问题，我们在有些小范围或特殊情形下的部分答案是已知的。如果我们能将其扩展，并且扩展的每一步都是相似的，我们能用递归求解。

       我们通过“原问题”出发，尝试把状态空间推移到“问题边界”，然后再反向回来回溯的遍历方式为递归。

       

       我们在递归时，每次让程序执行三个操作：

       1. 缩小问题状态空间的规模，即寻找“原问题”与“问题边界”的变换路线。

       2. 尝试求解缩小规模后的问题。

       3. 若求解缩小规模后的问题成功了，则得到答案后扩展到当前问题；若不成功，寻找其他变换路线，直到确定一个答案或确定当前问题无法求解。

       

       总结以上步骤，我们在递归时有数点重要的内容：

       1. 由于子问题和原问题的相似性，我们在用程序时显示可以将子问题视作新的原问题继续求解。即自身调用自身；

       2. 如果求解子问题失败，则称需要重新回到当前问题去寻找其他变换路线，因此前一次的操作和影响应当全部失效，即回溯时还原现场。

       

       很多递归能够转化为迭代。例如，在快速傅里叶变换中，我们利用蝴蝶变换优化，就成功地递归转为了迭代。

       

 

       二、应用举例

       

       这里举一些很常见且具有代表性的递归例子。

 

       递归实现指数型枚举

       

       从 1~n 这 n 个数中选取任意多个，输出所有可能的选择方案。

       稍微有一点离散数学基础就能够知道

       

       因此这是个指数型的枚举。

       这算是很能体现递归思想的一个举例了，大家珂以敲出简单的C++程序

       

int n;
vector<int> chosen; // 被选择的数
void calc(int x) {
	if (x == n + 1) { // 问题边界
		for (int i = 0; i < chosen.size(); i++)
			printf("%d ", chosen[i]);
		puts("");
		return;
	}
    //"不选x"分支
	calc(x + 1); // 求解子问题
	//"选x"分支
	chosen.push_back(x); // 记录x已被选择
	calc(x + 1); // 求解子问题 
	chosen.pop_back(); // 准备回溯到上一问题之前，还原现场
}
int main() {
	cin >> n;
	calc(1);  // 主函数中的调用入口
}

 

       我们用Kitten实现，即

       

       

       

       递归实现排列型枚举

       

       把1~n这n个整数排成一行后随机打乱顺序，输出所有可能的结果。

       

       这也是一个典型应用。

       我们敲出C++程序如下

      

int n;
int order[20]; // 按顺序依次记录被选择的整数
bool chosen[20]; // 标记被选择的整数
void calc(int k) {
	if (k == n + 1) { // 问题边界
		for (int i = 1; i <= n; i++)
			printf("%d ", order[i]);
		puts("");
		return;
	}
	for (int i = 1; i <= n; i++) { 
		if (chosen[i]) continue;
		order[k] = i;
		chosen[i] = 1;
		calc(k + 1); 
		chosen[i] = 0;
		order[k] = 0; // 这一行可以省略
	}
}
int main() { 
	cin >> n;
	calc(1);  // 主函数中的调用入口
}

 

       此处我希望各位能够自己搭出积木。作为一个习题，留给大家。

       下面给出参考积木：

       

       

       三、数据结构：栈

       

       栈是一种后进先出的数据结构。

       站只有一段能够进出元素，我们一般称为栈顶；另一端则为栈底。

       

       

栈（stack）中，从栈顶（top）压入元素的操作称为进栈（push），弹出元素的操作称为出栈（pop）。

       

       Kitten如何实现栈的操作？

 

       我们用Kitten实现进栈如下：

       

       

       用Kitten实现出栈如下：

       

     

        用Kitten实现获取栈顶元素如下：

       

       

       如何用Kitten实现判断栈是否为空？

       这里用到了一个简单的条件判断的技巧。

       

       此函数的用途为：如果栈为空，则返回True；否则返回False。
       因此返回了布尔变量，若长度为0，则反会的布尔变量值为True，否则为False。
       这是一个比较常用的返回方式。

       

       

       四、表达式计算

       

       如果我们要做一个作品，让用户输入一串算式，我们要给出解答。

       众所周知，Kitten那么一点点的积木是根本做不到直接算出结果的。我们该怎么办？

       

       方法1：递归

       

       目标：求解S[1~N]的值

       子问题：求解子区间S[L~R]的值。

       

       1. 若[L~R]中没有不被括号包含的运算符

       （1）若存在加减号，选其中最后一个，分成左右两半递归，结果相加减，返回；

       （2）若存在乘除号，选其中最后一个，分成左右两半递归，结果相乘除，返回.

       

       2. 若[L~R]中不存在没有不被括号包含的运算符

       （1）区间中本身没有运算符，说明是一个数，返回；

       （2）若区间中有运算符，则递归求解括号内 的运算符，并返回结果。

       

       珂以敲出C++程序如下，时间复杂度为 O(n²)。

       

 

// 递归法求中缀表达式的值，O(n^2)
int calc(int l, int r) {
	// 寻找未被任何括号包含的最后一个加减号
	for (int i = r, j = 0; i >= l; i--) {
		if (s[i] == '(') j++;
		if (s[i] == ')') j--;
		if (j == 0 && s[i] == '+') return calc(l, i - 1) + calc(i + 1, r);
		if (j == 0 && s[i] == '-') return calc(l, i - 1) - calc(i + 1, r);
	}
	// 寻找未被任何括号包含的最后一个乘除号
	for (int i = r, j = 0; i >= l; i--) {
		if (s[i] == '(') j++;
		if (s[i] == ')') j--;
		if (j == 0 && s[i] == '*') return calc(l, i - 1) * calc(i + 1, r);
		if (j == 0 && s[i] == '/') return calc(l, i - 1) / calc(i + 1, r);
	}
	// 首尾是括号
	if (s[l] == '('&&s[r] == ')') return calc(l + 1, r - 1);
	// 是一个数
	int ans = 0;
	for (int i = l; i <= r; i++) ans = ans * 10 + s[i] - '0';
	return ans;
}

 

 

       方法2：栈

       

       此部分作为拓展提升的内容。

       

       前置芝士：后缀表达式。

       我们常用的表达式是中缀表达式，即 A op B；我们的后缀表达式为 A B op，即先给出参与运算的元素，再给出运算符。

       举个栗子，5 3 +，即常说的5+3；

       举个复杂的栗子，4 5 3 + 2 - *。

       此处我们先将第一个加号转换成中缀：4 (5+3) 2 - *

       然后将后面的减号转换：4 [(5+3)-2] *

       现在就明了了，把最终的乘号再转换一下：{4*[(5+3)-2]}=24

       珂以发现，后缀表达式不需要任何括号，这就是其优越性所在，因此可以用栈实现。

       

       如何中缀转后缀？这是个好问题。请大家对照以下程序思考模拟。

       

 

// 中缀表达式转后缀表达式，同时对后缀表达式求值 
int solve(string s) {
	nums.clear();
	ops.clear();
	int top = 0, val = 0;
	for (int i = 0; i < s.size(); i++) {
		// 中缀表达式的一个数字 
		if (s[i] >= '0' && s[i] <= '9') {
			val = val * 10 + s[i] - '0';
			if (s[i+1] >= '0' && s[i+1] <= '9') continue;
			// 后缀表达式的一个数，直接入栈 
			nums.push_back(val);
			val = 0;
		}
		// 中缀表达式的左括号 
		else if (s[i] == '(') ops.push_back(s[i]);
		// 中缀表达式的右括号 
		else if (s[i] == ')') {
			while (*ops.rbegin() != '(') {
				// 处理后缀表达式的一个运算符 
				calc(*ops.rbegin());
				ops.pop_back();
			}
			ops.pop_back();
		}
		// 中缀表达式的加减乘除号 
		else {
			while (ops.size() && grade(*ops.rbegin()) >= grade(s[i])) {
				calc(*ops.rbegin());
				ops.pop_back();
			}
			ops.push_back(s[i]);
		} 
	}
	while (ops.size()) {
		calc(*ops.rbegin());
		ops.pop_back();
	}
	// 后缀表达式栈中最后剩下的数就是答案 
	return *nums.begin();
}

 

       其中我们还需要额外处理一些内容，比如优先级

       

       

       以及我们需要对后缀中单个运算符进行处理操作

       

 

// 处理后缀表达式中的一个运算符 
void calc(char op) {
	// 从栈顶取出两个数 
	int y = *nums.rbegin();
	nums.pop_back();
	int x = *nums.rbegin();
	nums.pop_back();
	int z;
	switch (op) {
	case '+':
		z = x + y;
		break;
	case '-':
		z = x - y;
		break;
	case '*':
		z = x * y;
		break;
	case '/':
		z = x / y;
		break;
	}
	// 把运算结果放回栈中 
	nums.push_back(z);	
}

 

       此部分较容易，仅给出C++程序，请大家自己将其实现为Kitten。

       

       

       结语

 

       本期教程就到这里了，有任何疑问珂以在评论区回复。

       看到了题目为“第三期·1”，说明这一期还有另一部分。我们将会从搜索学习到图的连通性问题，部分内容珂能会花费您的一些时间，如有条件，可以先对此作一定的了解。