猫史档案馆

今天我们就要来学习一下用kitten中两个强大的工具来制作作品，这两个工具就是——函数和列表。

很多萌新都不会使用函数和列表，其实它们的功能是非常强大的！

同样地，列表配合函数的使用能够实现很多特别的（并且很有用的）操作。

列表把很多变量放在了一起，是kitten中一个类似于数组的东西，但是可以随意插入、删除，也就是说聪明的官方把数组的基本操作已经提前编好，直接用就行了，不需要你手写。

 

 

列表

 

列表有以下基本操作：

 

 

还可以做到获取元素

 

 

判断长度

 

 

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

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

 

 

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

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

下面是过程解释：

 

 

 

然后再讲函数。

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

 

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

 

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

 

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

 

 

 

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

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

 

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

 

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

 

我们还是使用以下语句

 

传入参数5，然后可以用

来获取返回值。

 

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

 

最终得到的返回值为

 

 

 

然后还有递归函数。递归函数指的是在函数中调用自己。

递归函数必须要有边界条件，也就是说递归到某一程度后必须要有停止的条件，否则可以想象得到函数会一直调用下去，直到系统爆栈然后卡出Bug来。

 

 

 

 

讲完了函数，我们终于可以迎来我们这次的主角——数据结构中的栈(stack)。

 

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

 

 

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

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

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

 

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

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

 

 

 

kitten实现

 

但是我们的kitten编辑器里没有栈呀！怎么办呢？

那就要用到列表了。

 

把列表做成一个栈，我们只需要用到以下几个积木：

以及判断栈是否为空和获取栈顶元素，分别用

“Stack的最后一项”

和

“Stack的长度”

来实现。

 

 

 

作品实例

 

 

下面就是配合递归函数和栈来实现矩阵迷宫并且还能判断玩家走迷宫的能力大小的作品了！

 

以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就行了！

 

下面给出函数Search的积木

 

 

 

制作不易，谢谢大家的支持！

转载请附上原文链接。