Skip to content

Latest commit

 

History

History
103 lines (73 loc) · 8.6 KB

5.md

File metadata and controls

103 lines (73 loc) · 8.6 KB
Raw

第 5 节

本节最后修改于 2022 / 11 / 12

MP模块的递归

上节中我们讲了带参数调用MP模块。有人立马会想到：可调用 + 带参数 = 能递归。

——递归是什么？其实就是自己调用自己。那不就成死循环了吗？其实不是，因为递归到了一定程度会停止继续递归，这个程度叫边界条件。之所以在某种程度上可以说：可调用 + 带参数 = 能递归，是因为“可调用”意味着能自己调用自己；“带参数”意味着能判断边界条件来防止变成死循环——

调用MP模块实际上就是满足某个条件，而MP模块会循环检查这个条件，根据其是否满足来决定是否执行命令。所以MP模块的递归其实就是在执行完一次命令后，条件仍然满足自己再执行一次。直到MP模块遇到边界条件才会修改实体使其不满足激活条件。

但是由于MP模块的参数是“全局”的，而基岩版我的世界中又没有二维的计分板没法实现计分板堆栈，MP模块调用自己会丢失现在的计分板参数，所以只能实现尾递归或者用一些奇技淫巧。

定量给东西

定量给东西可以说是最简单的递归形式了。它不需要返回计分板值，而且貌似很有用，可以说是非常经典了。

# 例子
# 实现一个定量给鸡蛋模块，入口计分板为GE_eggNeed
# 对于一个GE_eggNeed的值为n的人，在运行结束后要让他的背包里有n个鸡蛋

[+,X,-,0] give @a[scores={GE_eggNeed=1..}] egg
[+,L,-,0] scoreboard players remove @a[scores={GE_eggNeed=1..}] GE_eggNeed 1
[+,L,-,0] scoreboard players reset @a[scores={GE_eggNeed=0}] GE_eggNeed

定量给东西有二分法的实现，感兴趣的读者可以了解一下，在此我们就不对其深入研究了。

等差数列

除了给鸡蛋这种简单的没有返回值的MP模块，修改计分板这种有返回值的MP模块更复杂一些。例如获取数列特定项的MP模块。

等差数列意思就是一个数列，任意相邻两项的差相同。例如 $1,3,5,7,9$ 或者 $5,4,3,2,1$ 。求等差数列是很好的一个尾递归的例子。

求数列第 $n$ 项，一般来说有两种方法。

一种是把 $n$ 代入到通项公式里。例如 $1,3,5,7,9$ 的通项公式为 $a_n=2n-1$ ，求第 $10$ 项就是 $2\times 10-1=19$ 。

但是世界上有很多数列并没有通项公式，这时可以使用第二种方法叫递推公式。递推公式就是根据前面项得出后面项的公式。例如 $5,4,3,2,1$ 的递推公式就是 $a_n=a_{n-1}-1$ ，求第 $10$ 项就得求第 $9$ 项，就得求第 $8$ 项……直到我们发现第 $1$ 项是 $5$ ，那么第 $2$ 项就是 $4$ ，第 $3$ 项就是 $3$ ……最终得到第 $10$ 项就是 $-4$ 。

这就是一种递归，我们在不断的调用递推公式，只不过每次的参数都不一样：第一次我们代入的 $n=10$ ，发现 $a_{n-1}$ 也就是 $a_9$ 的值不知道！于是我们调用第二次，这时 $n=9$ ，发现 $a_8$ 的值又不知道；于是第三次， $n=8$ ……云云。直到 $n=1$ 时，就是边界条件，我们知道 $a_1$ 就是 $5$ ，所以没有不知道的值了，就不用再调用什么东西了。这时别忘了，之前调用的公式还等着我们的值呢！于是我们开始返回结果。第一次返回 $a_1$ 的值是 $5$ ，于是 $a_2=a_1-1=4$ ，继而 $a_3=a_2-1=3$ ……直到 $a_10=a_9-1=-4$ 。

我们要练习MP模块的递归，于是我们就假装不知道等差数列的通项公式吧。

# 例子
# 实现一个等差数列模块，入口计分版为AP_n，出口计分板为AP_value
# 对于一个AP_n的值为n的人，要使其AP_value为数列5,4,3,2,1,...的第n项

[+,X,-,0] tag @a[scores={AP_nNow=1..}] add AP_inited //初始化部分开始
[+,L,-,0] scoreboard players set @a[scores={AP_n=1..},tag=!AP_inited] AP_value 5 //还没开始算的人的值为5
[+,L,-,0] scoreboard players set @a[scores={AP_n=1..},tag=!AP_inited] AP_nNow 1 //还没开始算的人现在算到了第1项
[+,L,-,0] tag @a[tag=AP_inited] remove AP_inited //初始化部分结束
[+,L,-,0] execute @a[scores={AP_n=1..}] ~~~ scoreboard players operation @s AP_diff = @s AP_n //边界处理部分开始
[+,L,-,0] execute @a[scores={AP_n=1..}] ~~~ scoreboard players operation @s AP_diff -= @s AP_nNow //如果AP_diff为0说明已经算到了该算到的项，就是算完了
[+,L,-,0] scoreboard players set @a[scores={AP_diff=0}] AP_n 0 //算完的人清空入口计分板
[+,L,-,0] scoreboard players reset @a[scores={AP_diff=0}] AP_nNow //算完的人重置临时计分板
[+,L,-,0] scoreboard players reset @a[scores={AP_diff=0..}] AP_diff //重置临时计分板，边界处理部分结束
[+,L,-,0] scoreboard players remove @a[scores={AP_n=1..}] AP_value 1 //正在算的人的值-1
[+,L,-,0] scoreboard players add @a[scores={AP_n=1..}] AP_nNow 1 //正在算的人多算了一项

这个模块的调用方法：给实体设置AP_n分数。获取返回值方法：当实体AP_n=0时，获取实体AP_value的分数并重置AP_value和AP_n。

斐波那契数列

用点奇技淫巧也可以做出不是尾递归的递归。

众所周知，斐波那契数列 $\{\ Fi_n\ \}$ 是一个数列，每一项等于前两项之和，而且 $Fi_0=Fi_1=1$ 。例如前 $7$ 项就是 $1,1,2,3,5,8,13$ 。想要知道第 $n$ 项就必须得知道第 $n-1$ 和第 $n-2$ 项。这里我们用MP模块的递归（with奇技淫巧）来实现。

不难发现，斐波那契数列不能只通过上一项来求出这一项，所以无法简单地写成尾递归的形式。这里我们采用的奇技淫巧是使用两个计分板，一个存储上一项的值，一个存储上上一项的值。我们将这一项求出来后，将这一项的值覆盖到存储上上一项的计分板上。这样子对于下一次调用模块来说，这两个计分板仍然是一个存储上一项，一个存储上上一项。根据调用次数的奇偶，两个计分板，哪个是上一项哪个是上上一项也不同。这是使用有限的计分板把结果存储了起来。

# 例子
# 实现一个斐波那契模块，入口计分板为Fi_n，出口计分板为Fi_value
# 对于一个Fi_n的值为n的人，要使其Fi_value为斐波那契数列的第n项
# 玩家_2的计分板C_num的值为2，用以取模判断奇偶

[+,X,-,0] tag @a[scores={Fi_nNow=1..}] add Fi_inited //初始化部分开始
[+,L,-,0] scoreboard players set @a[scores={Fi_n=1..},tag=!Fi_inited] Fi_valueAno 1
[+,L,-,0] scoreboard players set @a[scores={Fi_n=1..},tag=!Fi_inited] Fi_value 1 //还没开始算的人的前面两项都为1
[+,L,-,0] scoreboard players set @a[scores={Fi_n=1..},tag=!Fi_inited] Fi_nNow 2 //还没开始算的人现在算到了第2项
[+,L,-,0] tag @a[tag=Fi_inited] remove Fi_inited //初始化部分结束
[+,L,-,0] execute @a[scores={Fi_n=1..}] ~~~ scoreboard players operation @s Fi_type = @s Fi_nNow //获取调用奇偶部分开始
[+,L,-,0] execute @a[scores={Fi_n=1..}] ~~~ scoreboard players operation @s Fi_type %= _2 C_num //获取调用奇偶部分结束
[+,L,-,0] execute @a[scores={Fi_n=1..}] ~~~ scoreboard players operation @s Fi_diff = @s Fi_n //边界处理部分开始
[+,L,-,0] execute @a[scores={Fi_n=1..}] ~~~ scoreboard players operation @s Fi_diff -= @s Fi_nNow //如果Fi_diff为0说明已经算到了该算到的项，就是算完了
[+,L,-,0] scoreboard players set @a[scores={Fi_diff=..0}] Fi_n 0 //算完的人清空入口计分板
[+,L,-,0] scoreboard players reset @a[scores={Fi_diff=..0}] Fi_nNow //算完的人重置临时计分板
[+,L,-,0] execute @a[scores={Fi_diff=..0,Fi_type=0}] ~~~ scoreboard players operation @s Fi_value = @s Fi_valueAno //偶数调用次数的人设置Fi_value为真正的上一项的值
[+,L,-,0] scoreboard players reset @a[scores={Fi_diff=..0}] Fi_valueAno //重置临时计分板
[+,L,-,0] scoreboard players reset @a[scores={Fi_diff=-1..}] Fi_diff //重置临时计分板，边界处理部分结束
[+,L,-,0] execute @a[scores={Fi_n=1..,Fi_type=0}] ~~~ scoreboard players operation @s Fi_value += @s Fi_valueAno //正在算的偶数调用次数的人覆盖Fi_value为这一项的值
[+,L,-,0] execute @a[scores={Fi_n=1..,Fi_type=1}] ~~~ scoreboard players operation @s Fi_valueAno += @s Fi_value //正在算的奇数调用次数的人覆盖Fi_valueAno为这一项的值
[+,L,-,0] scoreboard players add @a[scores={Fi_n=1..}] Fi_nNow 1 //正在算的人多算了一项
[+,L,-,0] scoreboard players reset @a[scores={Fi_type=0..}] Fi_type //重置临时计分板

这个模块的调用方法：给实体设置Fi_n分数。获取返回值方法：当实体Fi_n=0时，获取实体Fi_value的分数并重置Fi_value和Fi_n。

下一节