当前位置:首页 >> 学科竞赛 >>

河内塔问题


河内塔问题
最终的规律是,2 的N次方-1 次,其中N表示圆片的个数
在小学数学四年级上册(人教版)第 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 片金片,需要移动 18446744073709511615 次。然后,再向学 生提出一个新问题:假如僧侣们每秒钟移动一次金片,夜以继日废寝忘食地照这样干下去, 需要干多少年?可以要求学生只列出算式。因为一年有 60×60×24×365 秒,所以需要 18446744073709511615÷(60×60×24×365)年。最后,老师宣布答案:大约需要 5846 亿年!相 信学生一定会在一片惊呼中,极大地提高对数学的认识和兴趣。然后顺便指出:根据科学家 的研究,太阳的寿命最多还有 100~150 亿年,5846 亿年远远大于这个数,可见印度传说仅 仅是一个传说而已。 其实“河内”就是“汉诺”的另一种音译。“

最终的规律是,2 的N次方-1 次,其中N表示圆片的个数
解三:需要把 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 号杆。 随着珠子的数量增加,这个过程会变得比较复杂,但从原理上讲,都可以转化成两颗 珠子的情况。我们可以把最大那颗珠子以上的其他珠子看成“一颗”“连体小珠子”,这颗“连 体小珠子”又可以看成是由一个大珠子和新的“连体小珠子”组成的……这样一直下去,最后 就可以化归为两颗珠子的移动。 在这个过程中, 2、 号杆作为“起始站”“中间站”“目标站” 1、 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 的N次方-1 次,其中N表示圆片的个数 整理得 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 圈,或在太阳和地球之间打个来回。

王子一言既出就要信守承诺。 他苦苦想了好几天, 终于想出好办法来了。 他对数学家说: “好吧,就给你那些玉米。你把棋盘拿来,然后就按你所说在每个格子上面放那些玉米,然 后那走吧。” 当然,那么多玉米粒是无论如何也放不进小格子里的。最终王子和数学家打了个平手。


相关文章:
河内塔问题
河内塔问题 智力游戏 数学书上有一道河内塔的问题,这是一个流传很广的游戏: 1.有三根杆子 A、B、C。A 杆上有三个碟子。 2.每次移动一个碟子,大碟子不能...
河内塔问题_教案
河内塔问题_教案_数学_小学教育_教育专区。河内塔问题 尹庄小学 乔宝付 课题 章节 姓名 单元 乔宝付 序号 45 河内塔问题 学校 组内评价 尹庄 个人评 价 年...
河内塔问题
河内塔问题教学目的: (1)学生能够初步学会用递推方法解决实际问题; (2)进一步巩固求解递推数列的方法; (3)利用“特殊化与一般化”的数学思想解决问题。 教学...
汉诺塔问题的重点是分析移动的规则
汉诺塔问题的重点是分析移动的规则_计算机软件及应用_IT/计算机_专业资料。C语言经典递归调用 汉诺塔问题的重点是分析移动的规则,找到规律和边界条件。 若需要将 n ...
汉诺塔难题
汉诺塔难题_初一数学_数学_初中教育_教育专区。汉诺塔问题,存在相同大小圆盘,和不同大小圆盘的情况 汉诺塔难题蒲锐,计科一班,14081010603 汉诺塔问题的介绍及问题:...
汉诺塔问题的解决及游戏设计
汉诺塔问题研究,吉林,考试周刊,2010年28期; [4]郑莉,董渊,何江舟,C++程序语言设计[M](第4版),北京:清华大学出版 社,2010; [5]常跃,汉诺(Hanoi)塔递归...
汉诺塔问题
汉诺塔问题_IT/计算机_专业资料。Hanoi塔问题。(要求4个盘子移动,输出中间结果) (1)掌握栈的特点及其存储方法; (2)掌握栈的常见算法以及程序实现; (3)了解递归...
汉诺塔问题的程序实现
汉诺塔问题的程序实现_电脑基础知识_IT/计算机_专业资料。汉诺塔问题的程序实现实验目的:运用程序解决汉诺塔(hanoi)问题。 汉诺塔问题:假设有 3 个分别命名为 A,B,...
汉诺塔问题的非递归新解法
汉诺塔问题的非递归算法 计算机科学与技术学院 计 11-1 班 张春颖(组长) 37 号刘丹 (组员) 22 号 汉诺塔问题的非递归新解法计 11-1 张春颖 37 号刘丹 22 ...
汉诺塔问题
汉诺塔问题_IT/计算机_专业资料。ACM 算法 数据结构汉诺塔百科名片 汉诺塔 初始状态 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。上帝 创造世界...
更多相关标签:
河内塔 | 汉诺塔问题 | 新汉诺塔 | 杨幂的胸下垂 | 河内塔问题ppt | 恐怖谷理论 | 河内塔问题 java | 河内塔实验 |