|
板凳
楼主 |
发表于 2013-7-1 01:37:03
|
只看该作者
2:汉诺塔移盘问题
有一种中国古老的智力游戏叫汉诺塔,有三个柱子,第一个柱子上有64个盘子,且大的在下,小的在上,大小都不等,要把这64个盘子移到另一个柱子上。问把整个64个盘子移到另一个柱子上需要多长时间?他的具体游戏规则如下:
1: 每次只能移动一个盘子。
2:无论在哪个柱子上,大盘不能放在小盘之上。
要算移动盘子的时间,先要算移动盘子的次数,为了弄清上边说的移动和推理过程,我们可以亲手玩一次这个游戏。我们可以把:“64”个盘子替换为“N”个盘子。先对较小的N(N=1,2,3,4)进行具体操作,通过游戏可以知道:当N=1时,移动盘子的次数M=1;当N=2时,M=3;当N=3时,M=7;当N=4时,M=15;……当N很大时,操作起来就很困难,我们用数学思想来考虑一下这个问题.
弄清N由 k变为k+1时发生的情况:对盘子从上到下依次编号,设为1~N号盘由A移到B(或C)上按移动次数最少的方法需要∪n次.因为要想把1~N号盘子由A移到B上,按规则(大盘不能在小盘之上),必须先把1~N-1号盘子由A移到C上(这是把B作为中转站),共用∪n-1次;再把N号盘移到B上,用一次;最后,再把C上的N-1个盘子(以A为中转站)移到B上,用∪n-1次.可见有如下的推理公式: ∪1﹦1,
∪n﹦2∪n-1+1(n≧2)
有了上述的递推公式,就可以逐渐地算出∪64了
方法一: ∪1=1,∪2=2∪1+1=3,∪3=∪2+1=,∪4=2∪3+1=15,∪5=2∪4+1=1,
∪6=2∪5+1=63,……可以看出这与2的幂有关,可以立刻得出∪1=21-1,∪2=22-1,∪3=23-1,∪4=24-1,∪5=25-1 ……可以立即猜想出∪64=264-1,或者可以猜想出这个式子的关系式 ∪n=2n -1 (n=1,2,3…)(用数学归纳法证明结论)
方法二:由于∪n = 2∪n-1+1, 所以∪n+1 = 2(∪n-1+1),得出数列{∪n+1}是首项为2,公比为2的等比数列.所以∪n+1=2×2n-1 =2n , ∪n=2n -1. 所以 ∪64=264 -1
最后得出结论移动完64个盘子需要58000亿年.在这里就运用到了数学中的等比数列的数学思想,才能使复杂的问题简单化.
数学思想是一个很广的问题,既有深度又有难度。这里只是简单的讨论一下,希望在我今后的数学探究路上及教学生崖中能够得出更有深度和广度的成果,与大家共勉。
参考文献:
(1〕 邵瑞珍 《教育心理学》 上海教育出版社 1985
(2〕 赵振威 《中学数学教材教法》 华东师范大学出版社 2000
(3〕 刘慧贤 《教育学》 内蒙古教育出版社 2003
(4〕 陈录生 马剑侠 《新编心理学》 北京师范大学出版社 2002
(5〕 张奠宇 过伯祥《数学方法初稿》 上海教育出版社 1996 |
|