汉诺塔游戏 328. 探索汉诺塔游戏中的数学奥秘

提交电子邮件:shuxuetg@163.com

邮政编码:4-312

○订阅2016年杂志，请点击文末“阅读原文”，进入海月新轩图书网站订阅

你知道吗

汉诺塔问题源于一个古老的印度传说。传说创造世界的神从左到右在一座庙里留下了三根钻石棒，最左边的那根从下到上，从大到小依次叠放着64个圆形金块。庙里的和尚按照上帝的旨意和规定的方法，不知疲倦地把他们从这个酒吧移到最右边的那个。预计这一事件完成后，宇宙将在一瞬间毁灭。根据这个传说，你能知道宇宙何时会毁灭吗？

游戏规则

有三根柱子，上面有几个组件，一次只能移动一个组件。在移动过程中，大部件不能压在小部件上。把所有组件从最左边的柱子移到最右边的柱子是胜利。规定中间支柱可以作为帮助。(如图)

分析:左栏只有三个组件，所以第一步只有两个选择，要么在中间，要么在右边。通过实际操作，我们发现如果把第一步放在中间，至少需要11步；如果第一步放在右边，至少只需要7步；这将比选择中间时少4步！

答:如果从左到右分别设置三列为左、中、右，从小到大分别设置三个成员为1、2、3，移动步骤如下:1右→2中→1中→3右→1左→2右→1右，至少需要7步。

活动2

你已经学会了三个组成部分。你知道怎么移动四个部件吗？他们至少需要移动多少步？那五个成分呢？试试吧！(如图)

分析:移动四个组件时，第一步有两个选择。如果将第一步向右移动，我们会发现将所有组件从最左边移动到最右边至少需要23步；如果第一步移动到中间，我们会发现将所有组件从最左边移动到最右边至少需要15步。这将比选择正确的一边少8步！而且在移动的过程中，你会明显感觉到整个三个组件都被移动了两次，这是多余的一步。当移动五个组件时，选择中间最少一步的第一步将比选择右边最少一步的第一步多16步！

回答:

(1)移动四个构件时:三列从左到右分别设为左、中、右，四个构件从小到大分别设为1、2、3、4，移动步骤为:1中→2右→1右→3中→1左→2中→1中→4右→1右→2左→3右

(2)移动5个成员时，第一步应该是向右移动1…，至少要走31步。

简易法

因为移动三个构件时，第一步是将第一个构件移动到右立柱；移动四个构件时，第一步是将第一个构件移动到中间立柱；移动五个构件时，第一步是将第一个构件移动到右立柱；所以有同学用分类讨论和最优选择的方法总结:当所有奇数分量都要从左列移到右列时，第一步是把第一个分量移到右列；当偶数个构件从左立柱移动到右立柱时，第一步是将第一个构件移动到中间立柱。

第一步，总结运动规律，然后我们通过实际操作来检验这个规律是否正确。实践证明，这个规律是正确的，但在实践过程中，我们遇到了另一个问题:当我们移动四个部件时，可以顺利完成；但是我们移动五个分量的时候，先用之前的规则把四个分量移动到中间，第五个分量移动到右边之后，会有另外的选择。要在中间移动四个组件，第一步有两个选择:左或右。应该如何选择？这里有些同学有点迷茫。后来经过实践，他们总结出每一个操作阶段第一步的规律:当所有奇数个部件都要从左立柱移动到右立柱时，第一步是将第一个部件移动到移动目标的立柱上；当您想要将所有偶数个成员从左列移动到右列时，最好不要在第一步中将第一个成员移动到目标列。

在解决了第一步的问题之后，我们将研究所有汉诺塔问题的操作思路和方法。我们发现要移动四个分量，只需要把三个分量移到中间的柱子，第四个分量移到右边，然后剩下的三个分量移到右边；要移动五个组件，我们只需要将四个组件移动到中间的柱子，将第五个组件移动到右边，然后将剩余的四个组件中的三个移动到左边，将第四个移动到右边...，这样我们就可以总结出所有汉诺塔问题的整体操作思路:先把n-1分量移到中间子，再把第n分量移到右边的柱子；然后，在中间的n-1个成员中，n-2个成员首先移动到左边的柱子，n-1个成员移动到右边。如果有九个成员，首先将八个成员移到中间，将第九个成员移到右列；然后8个成员中的7个会移到左边，第8个会移到右边的柱子。接下来，我们将七个组件中的六个移到左边，第七个组件移到右边的列...

在了解了操作的思路和方法之后，我们需要研究将所有组件从最左边移动到最右边需要多少个步骤。通过以上研究，我们发现移动3个组件至少需要7个步骤，移动4个组件需要15个步骤，移动5个组件需要31个步骤，移动2个组件需要3个步骤，移动1个组件需要1个步骤。总结这些情况的规律，我们可以猜测，将组件从最左边一列移动到最右边一列至少需要2n-1步，我们可以证明这个结论是正确的。利用这个规律，我们可以知道，要把传说中的64枚金块从最左边的柱子移到最右边的柱子上，寺庙里的僧人至少需要移动1.84×1019步左右，这是一个天文数字。就算每一步只要一分钟，和尚不吃不喝也不可能完成这个任务。

在我们面前，我们总结了汉诺塔游戏的规则，发现汉诺塔游戏中有丰富的数学内容。所以，玩好汉诺塔游戏，不仅能获得游戏的快乐，还能学到很多数学知识，体验很多数学思想和方法。

(内容和标题图均来自网络)

ID:xxsxjszz

长按二维码识别注意力