GESP 四级的新汉诺塔纳入教案,看完你也能教孩子

GESP 9 月四级这道新汉诺塔，题目质量很高 —— 它和经典汉诺塔一起，会成为我教案里最重要的一个板块。

我们给孩子学编程，图的是“会编程”。那怎么才算会呢？会编程，是对现实世界问题的一种解题游戏，也是一种思维升级。我们从小做的数学题，是一步一步走完手头这一步再走下一步；编程有更好的套路 —— 先把问题折小一号，再折小一号，一路折到他会做的那一步。经典汉诺塔和这道新汉诺塔，就是一个完整的会编程思维。

一、经典汉诺塔：线性思维到递推思维的转变

汉诺塔是个老玩法。三根柱子摆成一排，从左往右叫 A、B、C。A 上套着一摞盘子，越往下越大，像一叠碗摞在一起。目标是把这整摞盘子挪到 C 上，中间的 B 拿来做周转。能动的只有每根柱子最上面那一个盘子，大盘子不许压在小盘子上面。

孩子第一次做这类题，做法都很像：搬一个，看一眼，再搬一个。三个盘子他七步就能搬完，还挺得意。我教到这里一般不讲方法，先让他们自己搬下去。

三个盘子还数得过来。盘子加到五个六个，纸面上就开始乱：搬到一半忘了刚才为什么那么搬，只能退回去重来。

然后我给他们的提示是把这一摞分成两拨看：最底下那个大盘子算一拨，压在它上面的所有盘子算另一拨。

分开看以后，问题小了一大半。最大的盘子这辈子只动一次 —— 它要动，先得让头顶空出来；可头顶那摞盘子也不会凭空挪走，只能先整体搬到中间柱子上把位置腾开（我们称这一步为让路）。等大盘子落到终点，那摞盘子再整体搬过去，重新盖在它上面。

醒目的孩子一下子就会发现两个规律：1、小盘子们 A→B 和 B→C 的步数是一样的；2、下一个 6 个盘子的步数 = 5 个盘子的步数 × 2 + 1。

既然小盘子们 A→B 和 B→C 的步数是一样的，我们是不是可以合理的推断：小盘子们从任意柱子挪到另一个柱子的步数是一样的。

自然而然，我们脑海里就有了个式子： N 个盘移动的步数 = N−1 个小盘子们让路的步数 + 大盘子移动 1 步 + N−1 个小盘子们移动到大盘上的步数

但是这摞小盘子们在让路和挪到大盘子上的时候你还要再搬一次数步数吗？不用数了，你其实忘记了你已经数过一次了。

我们用 数学符号f 表示盘子们从一个柱子挪到另一个柱子的步数看看：

看到这里，孩子们和家长们都学会了怎么解汉诺塔难题。编程的解法就是这么朴实无华而无趣，但是你的思维已经从线性思维转成了递推思维。从此你看汉诺塔就会自动把这些盘子分成了两堆，最大盘和小盘子们，而且你也记起了小盘子们你已经搬过了。

二、新汉诺塔：状态描述最好的变式教材

经典版说完了，9 月四级这道新题，规则只挪了一条。

在纸上把三根柱子按 A→B→C→A 首尾接成一个圈，盘子只能顺着圈走：A 上的盘子只能去 B，B 上的只能去 C，C 上的只能回 A。反方向走不了。

经典版本里面，大盘子要挪到目标柱子，小盘子们只需要让路一次即可。新规则下由于只能一步一步挪，所以要先把小盘子们从 A 挪到 C，大盘子从 A 挪到 B，小盘子们再从 C 挪到 A，大盘子就可以到 C 了，这里小盘子们就要让路两次。

我们按照学过经典汉诺塔的大盘和小盘们分离的习惯总结出：N 个盘移动的步数 = N−1 个小盘子们第一次让路的步数 + 大盘子移动 1 步 + N−1 个小盘子们第二次让路的步数 + 大盘子移动 1 步 + N−1 个小盘子们搬到大盘子上的步数。

这就是我们的状态描述，没什么高大上的东西，就是把我们的脑子里已经存在的话用数学公式表达出来了。

三、双式递推：递推思维大集结

我们在前一节推出的新汉诺塔状态公式，有 3 个未解决的问题：小盘子们第一次让路的步数、小盘子们第二次让路的步数、小盘子们搬到大盘子上的步数，这三个数怎么计算呢。

很难是不是。这一点也是比较多同学卡住的地方，我们把状态公式拉出来对比下就很简单了：

有没有发现新大陆：N 个盘移动的步数、N−1 个小盘子们第一次让路的步数、N−1 个小盘子们搬到大盘子上的步数，都是从 A→C，那他们是不是都同一个计算方式？而且 A→C 的步数就是我们最终要的答案，可以先放着。

那么只剩下一个问题：N−1 个小盘子们第二次让路的步数，C→A。

小盘子们从 C→A 的步数单独拎出来看很明显也是个递推问题。我们把 N−2 个小盘子看成更小一号盘子们，N−1 看成小大盘子，那么这些小盘子们从 C→A 的步数 = N−2 个小盘子们从 C→B 的让路步数 + N−1 号大盘子从 C→A 的 1 步 + N−2 个小盘子们从 B→A 的步数。

我们再把这个小号递推公式拉出来对比下：

同学们能推到这里其实对递推已经有了很深的掌握了。但是还差一口气，我们发现问题又来了，C→B、B→A 的步数是没有推过的，是不是还要往下推？并不需要继续往下推了，由于新汉诺塔是一个单向环形 A→B→C→A，所以 C→B、B→A 的步数是等价于 A→C 的。

我们用数学符号 f 表示 A→C、g 表示 C→A 看看：

CCF 还是大能之人，这道新汉诺塔加上经典汉诺塔，建立了从状态描述的变化到多式递推的思维链，这样的思维深度恰恰是我们进行高阶递推训练需要的最完好的范本，也会成为许许多多孩子递推训练的绝佳案例。