河内塔问题

河内塔问题

最终的规律是，2的Ｎ次方－1次，其中Ｎ表示圆片的个数 在小学数学四年级上册（人教版）第120页有一道思考题“河内塔问题

解一：http://www.rajflxx.cn/Article/ShowArticle.asp?ArticleID=76 具体教材分析

解二：教参对这道题的解法做了一些简要的说明。网上也能查到一些相关的文章，不过大都

比较专业不大好懂。其实，这道题源于印度的一个古老传说。我最早是从美国著名科普作家乔治·盖莫夫的名著《从一到无穷大——科学中的事实和臆测》中读到的，不仅内容引人入胜，文笔也清新流畅。在此，推荐给有兴趣的网友。

“在世界中心贝拿勒斯的圣庙里，安放着一个黄铜板，板上插着三根宝石针。每根针像韭菜叶那样粗细。梵天（印度教的主神勃拉玛）在创造世界的时候，在其中一根针上从下到上放下了由大到小64个金片。这就是所谓梵塔。不论白天黑夜，都有一个值班的僧侣按照梵天不渝的法则，把这些金片在三根针上移来移去：一次只能移一片，并且要求不管在哪根针上，小片永远在大片的上面。当所有的64片都从梵天创造世界时所放的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。”

课本安排了经过简化的这样一道题目，是想让学有余力的学生，初步感知一下化归这种数学思想方法，用意很好。不过我觉得，倒不如先以阅读的形式或者听老师讲故事的形式，让学生对问题的全貌有所了解，借以引起学生的兴趣，再让学生从移动1个金片开始，去探究其中的规律。

(1)如果①号针上只有1个金片。把金片移到③号针上只需要移1次；

(2)如果①号针上有2个金片。先把小金片移到②号针上，再把大金片移到③号针上，再把小金片移到③号针上，总共需要移3次；

(3)如果①号针上有3个金片。像(2)那样(针号稍有改变)，先把上面的2个金片移到②号针上，需要移3次。再把最后1个大金片移到③号针上需要移1次。再把②号针上的2个金片移到③号针上又需要移3次。总共需要移3＋1＋3＝7次；

(4)如果①号针上有4个金片。先把上面的3个金片移到②号针上，需要移7次。再把最后1个大金片移到③号针上需要移1次。再把②号针上的3个金片移到③号针上又需要移7次，总共需要移7＋1＋7＝15次。

这时，可以引导学生观察由移动次数组成的数列：1，3，7，15，结合上面的实践，猜想和

探究其中隐藏的规律。因为学生在三年级下期课本第18页的思考题中，已经对数列：4，8，16，32，( )和2，5，11，23，47，( )有过先找规律后填数的经验。相信经过老师的启发和引导，学生能够发现数列1，3，7，15的规律是：后一项总是比前一项的2倍多1。这时，老师要不失时机地鼓励学生按照自己发现的规律，接着把金片的数目增加下去。随着金片移动次数的急剧增大，学生的情绪一定会越来越高涨。到了适当时机，老师可以告诉学生：按照梵天的法则移动64片金片，需要移动 [***********]15次。然后，再向学生提出一个新问题：假如僧侣们每秒钟移动一次金片，夜以继日废寝忘食地照这样干下去，需要干多少年？可以要求学生只列出算式。因为一年有60×60×24×365秒，所以需要[***********]15÷(60×60×24×365)年。最后，老师宣布答案：大约需要5846亿年！相信学生一定会在一片惊呼中，极大地提高对数学的认识和兴趣。然后顺便指出：根据科学家的研究，太阳的寿命最多还有100～150亿年，5846亿年远远大于这个数，可见印度传说仅仅是一个传说而已。

其实“河内”就是“汉诺”的另一种音译。“

最终的规律是，2的Ｎ次方－1次，其中Ｎ表示圆片的个数 解三：需要把A、B、C（从上到下）三颗珠子从1号杆移到3号杆

首先让学生明白：需要先把珠子C（最大的）移到3号杆（因为大珠不能放小珠上） 为了把珠子C移到3号杆，必须把A、B两珠都移到2号杆，这一步骤需要移3次 这样，第4次时才能把珠子C移到3号杆

然后又需要3次，把A、B两珠都移到3号杆，所以是7次

解四：河内塔问题渗透的是一种化归的思想。最简单的河内塔问题是把两颗珠子按照教材上的规则进行转移，方法如下：

第一步：把1号杆上的小珠子移到2号杆。

第二步：把1号杆上的大珠子移到3号杆。

第三步：把2号杆上的小珠子移到3号杆。

在上面的过程中，如果我们把1号杆当作“起始站“，把2号杆当作“中间站”，把3 号杆当作“目标站”的话，就是先把小珠子从“起始站”移到“中间站”，把大珠子从“起始站” 移到“目标站”，再把小珠子从“中间站”移到“目标站”。

当珠子的数量变成3个时，可以把上面的2颗珠子看成“连体珠”，所以第一个目标就是要把它“整体”移到2号杆上，但因为每次只能移一个珠子，所以要先把3号杆作为“中间站”…… 整个步骤如下：

第一步：把最上面的珠子移到3号杆。

第二步：把中间的珠子移到2号杆。

第三步：把最上面的珠子从3号杆移到2号杆（此时上面两颗珠子相当于“整体”移到2号杆。） 第四步：把最下面的珠子移到3号杆。

第五步：把最上面的珠子从2号杆移到1号杆。

第六步：把中间的珠子从2号杆移到3号杆。

第七步：把最上面的珠子从1号杆移到3号杆。

随着珠子的数量增加，这个过程会变得比较复杂，但从原理上讲，都可以转化成两颗珠子的情况。我们可以把最大那颗珠子以上的其他珠子看成“一颗”“连体小珠子”，这颗“连体小珠子”又可以看成是由一个大珠子和新的“连体小珠子”组成的……这样一直下去，最后就可以化归为两颗珠子的移动。在这个过程中，1、2、3号杆作为“起始站”“中间站”“目标站”的状态是动态变化的。

解五：学点递推的方法

有老师问我一个问题：从1,2,3三个数字中可重复的选择一些数字排成一个10位数，不允许这个10位数中有连续的两个1，比如2113331111是不允许的，而1213333333是允许的，因为前者有两个连续的1（事实上还超过了连续两个）问这样的10位数一共有多少个。

用递推的方法能很好的解决这个问题：

我们先来把这个问题一般化，即解决按题目中的要求排出的n位数有多少个的问题。事实上，n位数与n-1位数关系密切，我们可以认为每一个n位数都是在一个n-1位数的末尾添上一个数字构成的。找出这种关系对递推来说是关键的。我们来考虑所有的n位符合要求的数，为了讨论方便，把这样的数分为两类，一类是末位是1的，另一类是末位不是1（即是2或3）的。前者的个数记作An,后者记作Bn，所有的n位符合要求的数记作Cn，显然Cn=An+Bn。通过列举，不难得到C1=3,C2=8,而末位是1的n位数就是在末位不是1的n-1位数的末尾添一个1得到的（因为不能有两个连续的1，因结，对末位是1的n-1位数，不能在其末尾添1），所以，末位是1的n位数个数就和末尾不是1的n-1位数的个数相等，即An=B(n-1)，而末尾不是1的n位数就是在任何一个n-1位数的末尾添加一个2或一个3而得到的。因此，Bn=2*C(n-1),于是，

Cn=An+Bn=B(n-1)+2*C(n-1)=2*C(n-2)+2*C(n-1)

于是C3=2*C1+2*C2=2*3+2*8=21

C4=2*C2+2*C3=2*8+2*21=58,依此类推，C10不难求得。

一个更简单的练习：有10级台阶，小明可以每次跨一级，也可以每次跨两级，小明上到第10级台阶共有多少种不同的上法？

解六：数学书上120页有个河内塔的问题，按照老师布置的作业要求，我进行了一点研究和

试验。通过研究，我发现了一点规律：如果粒数是单数，首先要把1号珠移到C杆上，2号珠移到B杆上；如果粒数是双数，前二步必须把1号珠移到B杆上，2号珠移到C杆上。而且，算出3个珠子需要移动了多少下，再用其乘以2加1就等于4个珠子移动的次数；以此类推，如果知道N个珠子移动的次数为T，那么珠子数目为N+1个时，移动的次数就是2T+1；珠子数目为N+2个时，移动的次数就是2X（2T+1）+1…… 我的试验内容如下(说明：“1C”表示把1号珠子移动到C杆上)：

珠子数 移动次数 步骤

1个 1 1C

2个 3 1B→2C→1C

3个 7 1C→2B→1B→3C→1A→2C→1C

4个 15 1B→2C→1C→3B→1A→2B→1B→4C→1C→2A→1A→3C→1B

→2C→1C

5个 31 1C→2B→1B→3C→1A→2C→1C→4B→1B→2A→1A→3B→1C→

2B

→1B→5C→1A→2C→1C→3A→1B→2A→1A→4C→1C→2B→

1B→3C→1A→2C→1C

一些关于河内塔问题的小故事：

古印度恒河附近的贝那勒斯城(瓦腊纳西)里有一个印度教大寺庙。庙里有一座由三根高约50厘米的钻石针支撑着的大圆塔。其中的一根钻石针上放蛰64个从上到下、从小到大的黄金圆盘。有一天神召集所有的僧侣说道：“现在你们将所有的黄金圆盘从第一根钻石针移至其他钻石针上去，每次只能搬动一个，而且必须把小黄金圆盘放在大的上面。但你们如果偷懒，

这座塔就会倒塌，世界的末日也将来临。”

其实这个故事不仅是来自于印度的传说，也是1883年由法国数学家鲁卡斯提出的问题。除了这个问题以外，他还提出了不少与斐波纳契数列有关的问题。现在甚至有个数列叫“鲁卡斯数列”。

首先，假设黄金圆盘共有n个，需要搬运这些黄金圆盘的最少次数为xn.

如果黄金圆盘的个数n=1，那么x1=1;

如果n=2，那么x2=3;

n=3，那么x3=7.

这还不难理解。

x3的计算方法是这样的。

第一，要想把最小的黄金圆盘和中间的黄金圆盘移到钻石针c上，需要搬运3次。 第二，要想把最大的黄金圆盘移到钻石针b上，只需搬运1次

第三，要想把钻石针c上的两个黄金圆盘移到b上的大黄金圆盘上面，需要搬运3次。所以，

x3=3+1+3=7

同样道理，如果有4个黄金圆盘时的搬运方法如下。

第一，要想把最小的黄金圆盘和比它大一号的黄金圆盘，还有比最大的黄金圆盘小一号的圆

盘移到c上，需要搬运7次

第二，要想把最大的黄金圆盘移到b上只需搬运1次。

第三，要想把c上的3个圆盘放在b上的最大的圆盘上面，需要再搬运7次。

所以，x4=7+1+7=15

综上所述搬运n个圆盘的次数为：2的Ｎ次方－1次，其中Ｎ表示圆片的个数 整理得 xn=2n-1x64=18 446 744 073 709 551 615

如果每搬动一次圆盘需1秒钟，就需要5849亿4241万7355年。地球的年龄也只不过才45亿年左右。所以，即使僧侣们从地球诞生之日起开始不间断地搬运，想搬完还得花上5800亿年的时间。所以离世界末日还早着呢！ 摘自《神话中的数学》 还有一个与此类似的关于“国际象棋”的故事：

国际象棋是由距今约四千年前的一个名叫chartranga的印度游戏开始发展起来的。chartranga是以木偶形状作成的骑着大象的士兵、坐在战车上的士兵、步兵等兵种组成，按照一定规则移动的战争游戏。随着佛教的传播，这个游戏也随之传到了东亚，发展成为今天的中国象棋等。波斯帝国时代，chartranga游戏还传到了欧洲，成为11世纪欧洲最流行的一种游戏。直到1470年chartranga才慢慢发展成为现在的国际象棋。

国际象棋是在64个黑白小方格相间排列而成的棋盘上玩的游戏。古印度有个数学家叫西萨 班 达依尔，有一天印度的王子命他想出一个好玩的游戏，于是chartranga游戏诞生了。因为游戏太好玩，所以王子决定赏赐数学家。王子问他想要什么。数学家说：“王子殿下，请您在这张棋盘的第一个小格内，赏给我一粒玉米，在第二个小格内给我两粒，第三格内给四粒，照这样下去，每个小格都比前一个小格加一倍。陛下，把这样摆满棋盘上所有64格的玉米粒都赏给您的仆人吧！”

王子慷慨地答应了数学家的要求。但是没过多久，王宫里的其他数学家急急忙忙跑来向王子报告了一个惊人的数字。

1+2+22+23+24+……+263=264 -1=18 446 744 073 709 551 615

这个惊人的数字，把全印度的玉米，不，即使是把亚洲甚至是全世界所有仓库里的玉米都加起来也远远不够。要想凑够这个数，还得全世界的人种好几百年玉米才行。如果造一个宽四米，高四米的粮仓来储存这些粮食，那么这个粮仓就要长三亿千米，可以绕地球赤道7500圈，或在太阳和地球之间打个来回。

王子一言既出就要信守承诺。他苦苦想了好几天，终于想出好办法来了。他对数学家说：“好吧，就给你那些玉米。你把棋盘拿来，然后就按你所说在每个格子上面放那些玉米，然后那走吧。”

当然，那么多玉米粒是无论如何也放不进小格子里的。最终王子和数学家打了个平手。