探索汉诺塔游戏中的
数学
数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划
奥秘
数
采莫奉广一一j奂氢章镪..”,g.一嗨数噜教跨参荐i
一,一…一……
%|I6jS4《
2oO9嚣强阃曩
编者语编辑部每月收到数百份初中稿件,由于
版面所限,每期只能刊发二三十篇.为了扩大杂志的
信息量,同时也为了鼓励广大读者的创作热情,本栏
目对部分不便全文刊登的文章,筛选,摘录其中有新
意的观点和内容局部展示,希望对读者的教学教研有
所启迪,有所帮助.
熹薅谐帮游旗中敏
数警lJ必
江苏省常州市北环中学邹浩芳
1你知道吗
汉诺塔问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
源于印度.传说开天辟地的神在一个
庙里从左往右留下了三根金刚石做成的棒,在左边的
一
根棒上从下往上,由大到小依次叠放着64个圆的
金片,庙里的众僧遵照神的旨意,按照规定的
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
,不
知疲倦地把它们从这根棒一个一个地搬到右边的,
根棒上.有预言说,当这件事完成时宇宙会在一瞬间
闪电式毁灭.按照这个传说,你能知道宇宙将在何时
毁灭吗?
2游戏
规则
编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf
如图1,有三根柱子,左边的柱子上有若干构件,
规定每次只能移动一块构件,并且大的构件不能压在
小的构件上,将所有构件从左边
的柱子上移至右边的柱子上即
告胜利,在移动构件的过程中,
可利用中间一根柱子作为帮助.
活动1
图1
如果左边的柱子上只有三个构件(如图2),你能
用最少的步骤将它们按照汉诺
塔游戏的规则全部移动到右边
的柱子上吗?图2
分析:左边的柱子上只有三个构件,因此第一步
只有两种选择,要么放在中间,要么放在右边.通过实
际操作可以发现:第一步如果放在中间,最少需要移
动11步;第一步如果放在右边,最少需要移动7步.
所以第一步选择放在右边会比选择放在中间要少
4步!
解答:将三根柱子从左到右依次设为左,中,右,
三个构件从小到大分别设为1,2,3,则移动步骤为1
右一2中一1中一3右一1左一2右一1右,最少需要
移动7步.
活动2
研究了三个构件的移动规律,四个构件(如图3)
又该如何移动呢?最少需要移动多少步?五个构件
(如图4)呢?
L上上图3图4
分析:当要移动四个构件时,第一步有两种选择,
如果第一步移动到右边,通过实际操作发现,要将所
有构件从左边移动到右边最少需要23步;如果第一
步移动到中间,则将所有构件从左边移动到右边最少
需要15步;所以第一步选择放在中间会比选择放在
右边少8步!在移动过程中,你还会发现前者是将三
个构件整体移动了两次,这是一个多余的步骤.当要
移动五个构件时,第一步选择右边就会比选择中间少
16步!
解答:(1)当移动四个构件时,将三根柱子从左往
右分别设为左,中,右,四个构件从小到大分别设为
1,2,3,4,则移动步骤为1中一2右一1右一3中一1
左一2中一1中一4右一1右一2左一1左一3右一1
中一2右一1右,最少需要移动15步.
(2)同理,当移动五个构件时,最少需要移动
31步.
3规律探索
(1)移动三个构件时,第一步最好将第1个构件
移动到右边的柱子上;移动四个构件时,第一步最好
将第1个构件移动到中间的柱子上;移动五个构件
时,第一步最好将第1个构件移动到右边的柱子上.
因此,我们就可以用分类讨论和最优化选择的方法总
结:如果将奇数个构件从左边的柱子上全部移动到右
边的柱子上时,第一步最好将第1个构件移到右边的
柱子上;如果将偶数个构件从左边的柱子上全部移动
到右边的柱子上时,第一步最好将第1个构件移到中
诵F|培謦李;誊露2O09年第1O期I中旬)
间的柱子上.
(2)实践证明,移动第一步的规律是正确的.然
而我们又碰到了另一个问题:当我们在移动四个
构件时,还能顺利完成;但是在移动五个构件时,
先用前面的规律将四个构件移动到中间,第5个构
件移动到右边后,又会产生一次选择,要移动中间
的五个构件,第一步又有或左或右两种选择,有人
在这里就感觉头脑有点混乱了,后来经过实践总
结出每一阶段操作的第一步规律:如果将奇数个
构件从左边的柱子上全部移动到右边的柱子上
时,第一步最好将第1个构件移到目标所在的柱子
上;如果将偶数个构件从左边的柱子上全部移动
到右边的柱子上时,第一步最好不要将第1个构件
移到目标所在的柱子上.
(3)我们发现:要移动四个构件时,只需先将三个
构件移动到中间的柱子上,把第4个构件移动到右
边,接下来把剩下的三个构件移动到右边去;要移动
5个构件时,只需先将四个构件移动到中间的柱子
上,把第五个构件移动到右边,接下来将剩下的四个
构件中的三个移动到左边柱子上,第4个构件移动到
右边柱子上…,这样汉诺塔问题的总体操作思路可总
结为:当要移动n个构件时,先将(一1)个构件移动
到中间的柱子上,将第n个构件移动到右边的柱子
上;再将中间(一1)个构件中的(,2)个构件先移动
到左边的柱子上,第(,1)个构件移动到右边的柱子
上I..?.比如:有九个构件,首先需将8个构件移动到
中间柱子上,将第9个构件移动到右边的柱子上;然
后将八个构件中的七个移动到左边柱子上,将第8个
构件移动到右边的柱子上;接下来要将七个构件中的
六个移动到左边,将第7个构件移动到右边的柱子
上;….
(4)我们知道,移动三个构件至少需要7步,移动
四个构件至少需要15步,移动五个构件至少需要31
步,…,而移动两个构件至少需要3步,移动一个构件
至少需要1步,因此利用数学归纳法可以得出:将
个构件从左边的柱子移动到右边的柱子上至少需要
移动(2一1)步.利用这个规律,要将传说中64个圆
的金片从左边的柱子上移动到右边的柱子上,庙里的
和尚最少需要移动约1.84×10”步,这是一个天文数
字,每一步就算只需要1分钟,他们就算不吃不喝,也
采英撷萃
数
苑
广
角
是不可能完成这个任务的.
(
说明
关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书
:假如第一步选择不当,最少的移动步骤要
比选择恰当时最少的移动步骤多2一步,证明略).
4你学会了吗
现在你已经知道了汉诺塔游戏中的数学奥秘,那
你知道移动九个构件时,第一步应该移动到哪里?最
少需要移动多少步?第65步移动的是哪一个构件?
它将被移动到哪个位置上?
解答:按照上述规律,移动九个构件时第一步
应该将第1个构件移到右边的柱子上;因为将个
构件从左边柱子移动到右边柱子最少需要(2.
一
1)步,所以移动九个构件时最少需要移动511
步;因为将八个构件从左边柱子全部移动到右边
柱子时,需先将八个构件移动到中问柱子,将七个
构件移动到左边柱子,将六个构件移动到中间柱
子,将五个构件移动到左边柱子…,又因为第65
步最接近63—2一1,因此需从移动六个构件处人
手,6—9—3,所以需先将六个构件移动到中间柱
子,而移动六个构件至少需要63步,所以第64步
应该将第7个构件移动到右边柱子,接下来要将六
个构件移到右边柱子上去,需先将前五个构件移
到左边柱子上,因为5是个奇数,所以第65步应该
将第1个构件移动到左边柱子上.
5结束语
研究了汉诺塔游戏中的规律(包括游戏总体操
作思路的规律,每一次操作的第一步的规律和完
成任务所需的最少步骤等),我们已经知道,汉诺
塔游戏中蕴藏着丰富的数学思想方法(包括分类
讨论的思想与方法,最优化选择的方法,数学归纳
的方法,数学递归的思想等),因此,玩好汉诺塔游
戏不仅可以从中获得快乐,还能够学到许多数学
知识.
“l龋涟|
江苏省兴化市楚水实验学校邓昌滨
《中学数学教学参考》(中旬)2009年第3期刊登