猫史档案馆

【kitten教程分享】列表、函数与递归、三角函数、坐标系上的进阶操作！

 

 

 

列表

 

 

列表有以下基本操作：

 

 

还可以做到获取元素

 

 

判断长度

 

 

那么实际上以上几个操作都可以自己手写来完成，以插入元素为例。

插入元素100到第100项的积木如下：

 

 

并不难理解，大家自己画一下图就行了。

思路是把从100项开始的每一个元素都向后移一位，然后再把第100项替换为100。

下面是过程解释：

 

函数

 

函数就是把一些语句封装在一起，放便以后直接食用。函数有参数（可以为空）、返回值（可以没有）。

 

参数就是函数在运行中需要参与运行的变量。为了更好地理解参数的作用和传递，我们看一下下面这个很简单的函数，这个函数只有一个参数：步数。

 

以下是调用函数以及参数传递的积木：

 

它表示运行函数“跑步”，其中步数为5。以上函数及其调用的效果等同于

 

 

 

返回值是函数计算后得到的结果，该结果会返回到调用它的语句中。

当你的函数出现返回值的时候，会多出这么个积木：

 

这个积木的含义是获取函数“跑步(0)”的返回值。

 

在对上面的“跑步(步数)”函数增添返回值，可以这么写：

 

我们还是使用以下语句

 

传入参数5，然后可以用

来获取返回值。

 

为了显示返回值，我们可以用变量“返回”来存储返回值，积木如下：

 

最终得到的返回值为

 

 

递归

 

递归就是在函数中调用自己。

有递归必然有回溯的过程。

递归的过程形成一棵树，递归的起始就是这棵树的根，递归的边界就是这棵树的叶子节点。

如下图：

（鼠标画的图片请谅解）

上图中展现了深度为三层递归（根节点算第0层）。

 

递归过程可以用栈来存储。栈是一种线性数据结构，用于优化算法处理而不是作为模型用来描述。

栈是一种后进先出的数据结构。你可以把它想象成一个开口的杯子，最后放入的元素在最上面，因此这个元素也最先被取出来。

 

 

由于递归函数的调用过程完全符合栈的操作，因此递归都是由系统栈来维护的。

因此，在递归过程中，可以很好地利用栈来帮助记录。比如DFS(深度优先搜索)就是配合栈来使用的。

（当然也不是说递归过程中就不能用其他数据结构了）

 

下面是C++语句的实现：

Stack.empty();         //如果栈为空则返回true, 否则返回false;
Stack.size();          //返回栈中元素的个数
Stack.top();           //返回栈顶元素, 但不删除该元素
Stack.pop();           //弹出栈顶元素, 但不返回其值
Stack.push();          //将元素压入栈顶

 

前面提到的搜索（Search），就能够用递归来实现（当然循环模拟递归或递推也可以）。

我们在对元素进行搜索的时候，会按照访问的优先顺序形成一棵搜索树。

这是我在讲解递归的时候放的一张图片。其实它就是搜索树的形状。

搜索树中的每个节点存储着一个时间戳。时间戳代表了第一次访问到这个节点时是第几个被访问的。

 

同样我们还有DFS序。它存储了每个节点在被搜索和回溯的时候是第几次操作。

 

// 深度优先遍历框架
void dfs(int x) {
	v[x] = 1;
	for (int i = head[x]; i; i = next[i]) {
		int y = ver[i];
		if (v[y]) continue;
		dfs(y);
	}
}

// DFS序
void dfs(int x) {
	a[++m] = x;
	v[x] = 1;
	for (int i = head[x]; i; i = next[i]) {
		int y = ver[i];
		if (v[y]) continue;
		dfs(y);
	}
	a[++m] = x;
}

 

我们的栈还有很多的用途。结合递归，我们可以做到括号匹配。

单调栈是一个重要的工具。

 

// 递归法求中缀表达式的值，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;
}

// ----------------------------------------------------
// 后缀表达式转中缀表达式，同时求值，O(n)

// 数值栈 
vector<int> nums; 
// 运算符栈 
vector<char> ops;

// 优先级 
int grade(char op) {
	switch (op) {
	case '(':
		return 1;
	case '+':
	case '-':
		return 2;
	case '*':
	case '/':
		return 3;
	}
	return 0;
}

// 处理后缀表达式中的一个运算符 
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);	
}

// 中缀表达式转后缀表达式，同时对后缀表达式求值 
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();
}

// ----------------------------------------------------
// 单调栈
a[n + 1] = p = 0;
for (int i = 1; i <= n + 1; i++) {
	if (a[i] > s[p]) {
		s[++p] = a[i], w[p] = 1;
	} else {
		int width=0;
		while (s[p] > a[i]) {
			width += w[p];
			ans = max(ans, (long long)width * s[p]);
			p--;
		}
		s[++p] = a[i], w[p] = width + 1;
	}
}

 

 

 

现在让我们的关注点回到kitten上来。

让我们实现一个简单的例子。这个例子简单到根本不需要二维数组。

这是个迷宫的例子。我们让程序自动走迷宫，并且走出最优秀的路径。

然后我们让用户自己走一遍，判断玩家走迷宫的过程是否优秀。

以5*5迷宫为例。

 

下面是建图：

 

首先，我们需要用一个长度为49的列表，排列成如下的样子（弄成矩阵的样子只是为了看着方便，实际上这个列表就只有一行，49个元素）

 

{1,1,1,1,1,1,1}
{1,0,0,0,0,0,1}
{1,0,0,0,0,0,1}
{1,0,0,0,0,0,1}
{1,0,0,0,0,0,1}
{1,0,0,0,0,0,1}
{1,1,1,1,1,1,1}

其中1表示墙。

 

其次，我们还需要生成一个起点，一个终点，可以用随机数积木来做到。我们把起点标记为2，终点标记为3。比如元素9为起点，元素41作为终点，这个列表就变成了

{1,1,1,1,1,1,1}
{1,2,0,0,0,0,1}
{1,0,0,0,0,0,1}
{1,0,0,0,0,0,1}
{1,0,0,0,0,0,1}
{1,0,0,0,0,3,1}
{1,1,1,1,1,1,1}

 

然后我们再随机生成障碍物，标记为4.这里要加一个特判，保证起点和终点不被障碍物覆盖到。比如下面这个迷宫：

{1,1,1,1,1,1,1}
{1,2,0,0,0,4,1}
{1,0,4,4,0,0,1}
{1,0,0,0,0,4,1}
{1,4,4,0,0,0,1}
{1,0,0,0,4,3,1}
{1,1,1,1,1,1,1}

 

规则如下

那么，可以利用栈和递归函数来实现让玩家走迷宫来判断玩家的走迷宫能力的作品，并且告诉玩家最优走法。

 

比如这个迷宫

{1,1,1,1,1,1,1}
{1,2,0.1,0.2,0.3,4,1}
{1,0.5,4,4,0.1,0.2,1}
{喵}
{1,4,4,0.2,0.2,0.4,1}
{1,0.2,0.1,0.6,4,3,1}
{1,1,1,1,1,1,1}

 

规定一个格子只能走一次，并且走到每个格子都要花费一定的精力(就是非1，2，3，4的格子所显示的小数数值)，问如何走花费的精力最小？

 

首先，我们可以看到，如果你往下方走，你的格子编号就会增加7，往上走会少7，往左走会少1，往右走会增加1。因此我们的向各个方向走之后位置的转移就确定了。

 

 

我们定义

 

定义列表A用来存储迷宫

定义函数void Search(int Number)

定义栈Stack

定义列表B用来操作

定义栈Answer来存储最优路径

定义变量ANS来存储当前代价

定义变量Ans来存储最优代价

 

思路是这样的

 

1，复制迷宫列表A到列表B，把Ans赋值为无穷大

2，我们在搜索每一个可以走到的格子（就是转移后是小数）的时候，把那个格子压入栈Stack，并把ANS加上当前编号的元素的值，然后把这个格子的值标记为4（就是没法再走了）

3，当没地方可走的时候，就回溯，并且把当前编号弹出栈Stack，然后再把当前编号的列表B的元素重新替换为同编号的列表A的元素的值，再把ANS减去这个值

4，到达终点的时候，如果Ans>ANS，那么把Ans赋值为ANS，随后把栈Stack复制到栈Answer

5，如此重复直至所有路都搜索完，递归结束，返回至主函数，得到最优解

 

随后就可以让玩家自己来走啦，喵家花费的精力和最优解对比一下，就能得出玩家的走迷宫的本

领强不强了，然后再输出Stack就行了！

以下是到达终点后的操作：

 

至于向下一节点递归，这个不难理解。因此我讲一讲回溯。

下面是回溯部分的积木，也就是遍历完这个节点的子树（包括自身）之后，取消标记，返回父节点，然后父节点遍历其他兄弟节点及其子树。

下面给出完整积木供大家参考。

 

 

现在，我们的关于搜索和递归的内容告一段落。

 

还记得我的三角函数吗？

我当时在我的三角函数教程中提到，慕斯用泰勒公式实现了精确的三角函数算法，比kitten给你的精确了1000到10000倍。这是如何做到的？

 

先来回顾一下有关三角函数化简求值的内容：

我们现在就要用这个“泰勒公式”来求值了。

众所周知泰勒公式是近似，所以我们要先把输入的变量放在可控的范围内。然后我们要转弧度制。

像这样即可：

 

然后我们把这个“弧度x”放到泰勒公式里面去。

这就好啦qaq！！

来回顾一下我的教程当时是怎么说的：

 

 

现在你们能解决用Kitten这些问题了吗？

 

 

kitten关于坐标的一些进阶知识技巧

 

其中我们遇见了很多公式，这里

 

 

 

如何做到瞬移到两个物体中间？这是个值得讨论的问题。

我们知道两个数的平均数

(a+b)/2

在数轴上的意义就是两个点的中点或线段的中点。

我们略微拓展一下下，将两者坐标分别平均，得到了中点公式。

 

上面就是kitten的实现。

几何上来说就是中位线：

 

我们通过上图可以看到，两个点x，y坐标分别平均之后就是中点。

 

回到三角函数，我们还可以应用于飞机大战。

敌机飞的路径可不可以是正弦波呢？

我们很多人坐飞机大战的时候都不知道小型敌机的飞行方式该怎么做。

这里举个例子，相信大家都明白了：

这是我在坐飞机大战的时候写的一段积木。

大家可以看到，我用余弦函数的正弦波模拟了飞机的飞行路径。这样非常省事，而且还很自然。

回顾一下正弦波的图像，你或许就明白了：

 

那么我们接着看：如果我们想要让某个角色跟着鼠标移动，并且不改变方向？

这似乎很简单。更进一步：我想让角色离鼠标越远就移动的越快，离鼠标越近就移动的越慢。这该如何办？

 

我们还是要用到一个工具：两者的坐标差。

现在我想大家都很明了了：每次增加两者坐标差的二分之一、十分十一、五十分之一等等距离。

这里的速度可以自由控制。

下面是一个实例：

（这其实也是我做飞机大战的时候的）