汉诺塔（Tower of Hanoi）：LAMBDA函数递归的一种解法

shaowu459

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。


汉诺塔是学习各种编程语言递归时的典型案例，但在Office 365之前，工作表函数中无法实现递归计算，因此工作表函数应该是无法解决汉诺塔递归运算的。现在有了LAMBDA函数，可以通过定义名称实现递归，因此，我们也可以尝试使用LAMBDA函数来实现一下汉诺塔的解法。

shaowu459

准备工作1：如何使用LAMBDA函数实现递归运算

在工作表中使用递归运算，需要将LAMBDA自定义的公式定义名称，下面我们以最简单的1-100自然数求和为例进行说明。

首先，在名称管理器中定义名称fx，公式如下：

1. =LAMBDA(n,IF(n=1,1,n+fx(n-1)))

复制代码

然后，在任意空单元格中输入下面的公式即可得到1-100的自然数合计值（其中100为变量，可调整）：

1. =fx(100)

复制代码

公式运算的过程是这样的：
1）初始fx的参数n=100，进入IF断后，由于n不等于1，所以返回n+fx(n-1)=100+fx(100-1)=100+fx(99)，这部分的意思是：要求1-100的合计值，只需要知道1-99的合计值然后再加上100就就可以了，而1-99的合计值可以用fx(99)来计算。
2）继续往下，f(99)=99+f(98)，f(98)=98+f(97)……f(2)=2+f(1)。到最后一步f(1)的时候，IF函数判断n=1，因此返回1，也即确定了f(1)的值。
3）因为已知f(1)=1，所以f(2)=2+f(1)=2+1=3也就确定了，f(3)=3+f(2)也就确定了。这样一直往上，fx(99)也就知道了，因此f(100)=100+f(99)也就计算出来了。

在这个计算过程中，没有达到n=1（递归循环的退出条件）前，公式将重复调用fx本身，这就是递归的运算过程和特点。

有兴趣的话，也可以看下论坛公众号上的一篇文章：LAMBDA函数中的递归用法，你用过吗

shaowu459

准备工作2：SORTBY函数

SORTYBY函数可以实现根据排序依据对数组进行排序。例如：

1. =SORTBY(D2:F2,{1,3,2})

复制代码

D2:F2单元格中存储着字母ABC，我们以{1,3,2}这个数组为依据对ABC进行排序，目前两个数组一一对应：A对应1，B对应3，C对应2。默认的排序会将{1,3,2}按升序排列变成{1,2,3}，因此ABC三个字母也会跟着一起调整顺序，由于2和3互换了位置，因此B和C也会互换位置，变成{"A","C","B"}。

再例如下面的公式将{"A","B","C"}数组中的第一个和第三个元素交换，结果数组是{"C","B","A"}：

1. =SORTBY(D2:F2,{3,2,1})

复制代码

shaowu459

准备工作3：定义一个【移动】的操作

在本帖讲解时，我们把一个圆盘从一个柱子挪动到另外一个柱子的操作定义为【移动】了一次。如下图，1号圆盘从A柱【移动】到了C柱，我们记作"A--->C"。


【移动】这个操作，可能发生在任意两个柱子之间，在每次移动圆盘时涉及两个柱子，一个是圆盘所在的初始柱，一个是圆盘要移动过去的目标柱。每次移动操作前，我们把初始柱放到最左面，把目标柱放在最右面。

例如：
1号圆盘从A柱移动到B柱时，A是初始柱，B是目标柱，记作"A--->B"，可以想象成先把B和C交换下位置，1号圆盘从最左侧的A柱移动到了最右侧的B柱上。
1号圆盘从B柱转移到C柱时，B是初始柱，C是目标柱，记作"B--->C"，可以想象成先把A和B交换下位置，1号圆盘从最左侧的B柱移动到了最右侧的C柱上。


也就是说：在每次移动操作时的初始柱和目标柱和上一次移动时的初始柱和目标柱可以不一样，ABC这3个柱子的角色可以互换。

shaowu459

准备工作做好之后，我们来开始研究如何用公式实现汉诺塔移动步骤。

为方便描述，用n来代表圆盘的总数量，用{"A","B","C"}来代表3个柱子和相对位置，默认所有的圆盘都在最左面的A柱上，要移动到最右侧的C柱上（其实B和C都是空柱子，完全是等价的）。

首先，来看最简单的1层汉诺塔，也就是n=1的情况。

这种情况下，只需要从A移动到C这一次操作即可，也就是从第1个柱子移动到底3个柱子。用公式来表示就是当n=1的时候，移动发生在第1个和第3个柱子之间，当n>1的时候需要执行其他操作：

1. IF(n=1,INDEX({"A","B","C"},1)&"-->"&INDEX({"A","B","C"},3),当n>1时执行的其他操作)

复制代码

shaowu459

2层汉诺塔一共需要移动3次：
第1次是将1号圆盘从A移动到B，由于【移动】是从最左面的柱子移动到最右面的柱子，可以理解成B和C先交换一下位置，然后执行1号圆盘的【移动】操作，操作完成后再把B和C交换回来。也就是将柱子位置数组{"A","B","C"}变成{"A","C","B"}后实现【移动】操作（从最左面移动到最右面），记做“A--->B”。
第2次是将2号圆盘从A移动到C，正好符合【移动】的定义，因此直接移动过去，记作“A--->C”
第3次是将1号圆盘从B移动到C，由于【移动】是从最左面的柱子移动到最右面的柱子，可以理解成A和B先交换一下位置，然后执行2号圆盘的【移动】操作，记作“B--->C”。

上面的3步操作都是执行的1层汉诺塔的移动操作。

假设是更多层的汉诺塔，我们可以把最底层之上的n-1个圆盘看成一个整体，这样就又成了一个2层的汉诺塔。把这n-1个圆盘移动到B柱后，将最底层的圆盘直接从A柱移动到C柱，这样B柱剩下n-1个圆盘，然后将A柱和B柱交换一下位置，就变成了n-1个圆盘的移动问题。在解决n-1个圆盘的移动问题时，可以把最底层圆盘以上的n-2个圆盘想成一个整体，把n-2个圆盘移动到B柱后，把A柱最下面的一个圆盘移动到C柱，而后B柱和A柱互换位置，再重复上面的移动步骤直到最左面的柱子只有1个的时候，执行最后一次从左面柱子移动到最右面柱子的移动操作。

可以看出，上面的移动过程和2层汉诺塔移动的模式是一样的，这也是递归每次循环的模式。


综上所述，我们可以把基础的【移动】操作定义为LAMBDA函数，圆盘数量在2层及以上时按重复执行2层汉诺塔的移动模式，也就是在5楼IF函数中提到的【当n>1时执行的其他操作】

shaowu459

在明确了递归的模式后，我们可以定义fx名称，公式如下：

1. =LAMBDA(n,y,IF(n=1,@y&"-->"&INDEX(y,3),VSTACK(fx(n-1,SORTBY(y,{1,3,2})),@y&"-->"&INDEX(y,3),fx(n-1,SORTBY(y,{2,1,3})))))

复制代码

上面的自定义函数fx有两个参数，分别为n和y。n代表要解决的汉诺塔层数，是正整数。y代表初始3个柱子的名字和位置，初始值为{"A","B","C"}，如下面的公式将返回3层汉诺塔的每步移动过程：

1. =fx(3,{"A","B","C"})

复制代码

shaowu459

最后，来说明一下公式每部分的意义：
=LAMBDA(n,y,
                    IF(n=1,                                                    判断圆盘数量
                       @y&"-->"&INDEX(y,3),                      如果圆盘数量为1，则将圆盘从第1个柱子移动到第3个柱子。@y获得数组第1个元素，INDEX(y,3)获得第3个元素
                       VSTACK(                                               当n>1时，VSTACK函数堆积下面3步的操作结果
                                    fx(n-1,SORTBY(y,{1,3,2})),  调用fx本身，这部分执行将n-1个圆盘从A柱移动到B柱的效果，因为移动是从最左移动到最右，
                                                                                     因此用SORTBY函数将2和3位置的柱子互换位置，相当于2层汉诺塔的第一步
                                    @y&"-->"&INDEX(y,3),         实现将A柱最下面一个编号为n的圆盘移动到最右侧柱子C的结果记录，相当于2层汉诺塔的第二步
                                    fx(n-1,SORTBY(y,{2,1,3}))   将B柱换到最左侧A柱位，再次循环，实现将中间B柱上的n-1个圆盘移动到最右侧C柱的效果。
                                    )
                      )
                )

shaowu459

下面是1-4层汉诺塔移动效果的展示：
1层汉诺塔：


2层汉诺塔：


3层汉诺塔：


4层汉诺塔：

alan57

这么好的帖子,必须要占个坑.