admin 发表于 2019-2-7 12:39:32

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

  前面我们总结了汉诺塔游戏中的规律发现汉诺塔游戏中蕴藏着丰富的数学内容,因此,玩好汉诺塔游戏不仅可以从中获得游戏的快乐,而且还能够从中学到很多数学知识,体会很多数学思想与数学方法。返回搜狐,查看更多
  解决了第一步的问题后,我们就要研究所有汉诺塔问题的操作思路和方法了,我们发现:要移动4个构件,只需先将3个构件移到中间的柱子上,把第4个构件移到右边,接下来把剩下的3个构件移到右边去;要移动5个构件,只需先将4个构件移到中间的柱子上,把第5个构件移到右边,接下来将剩下的4个构件中的3个移到左边,第4个移到右边……,这样我们就可以总结出将所有的汉诺塔问题的总体操作思路总结为:先将n-1个构件移动中间的子,将第n个构件移动到右边的柱子上;再将中间的n-1个构件中n-2个构件先移到左边的柱子上,第n-1个构件移动到右边……。如有9个构件,首先需将8个构件移动到中间,将第9个构件移动到右边的柱子上;然后要将8个构件中的7个移动到左边,将第8个构件移动到右边的柱子上;接下来要将7个构件中的6个移动到左边,将第7个构件移动到右边的柱上……
  (1)当移动4个构件时:将三根柱子从左往右分别设为左、中、右,4个构件从小到大分别设为1、2、3、4,则移动步骤为:1中→2右→1右→3中→1左→2中→1中→4右→1右→2左→1左→3右→1中→2右→1右,最少需要移动15步。
  第一步移动的规律总结出来了,接下来我们就要用实际的操作来检验这个规律是否正确。实践证明,这个规律是正确的,然而在实践的过程中我们又碰到了另一个问题:当我们在移动4个构件的时候,我们还能比较顺利地完成;但是当我们在移动5个构件的时候,我们先用前面的规律将四个构件移动到中间,第5个构件移动到右边后,又会产生一次选择,要移动中间的4个构件,第一步又有或左或右两种选择,应该如何进行选择呢?有的同学在这里头脑又有点混乱了,后来经过实践,总结出每一阶段操作的第一步的规律:当要将奇数个构件从左边的柱子上全部移动到右边的柱子上时,第一步最好将第1个构件移到移动目标的柱子上;当要将偶数个构件从左边的柱子上全部移动到右边的柱子上时,第一步最好将第1个构件不要移到目标所在的柱子上。
  汉诺塔问题源于印度的一个古老的传说。传说开天辟地的神在一个庙里从左往右留下了三根金刚石的棒,在最左边的一根上从下往上、由大到小依次叠放着64个圆的金片,庙里的众僧遵照神的旨意,按照规定的方法,不知疲倦地把它们一个一个地从这根棒搬到最右边的那根棒上。有预言说,当这件事完成时宇宙会在一瞬间闪电式毁灭,按照这个传说,你
  分析:左边的柱子上只有三个构件,因此第一步只有两种选择,要么放在中间,要么放在右边,通过实际的操作,我们发现第一步如果放在中间,最少需要11步;第一步如果放右边,最少只需要7步;这样就会比选择中间时少掉4步!
http://img.mp.itc.cn/upload/20170320/d1303eccf9e24e74abcb8972f8f8a92f.png
http://img.mp.itc.cn/upload/20170320/e9247e305f884cefbccae7f9d85d991b.png
  因为移动3个构件时,第一步最好将第1个构件移动到右边的柱子上;移动4个构件时,第一步最好将第1个构件移动到中间的柱子上;移动5个构件时,第一步最好将第1个构件移动到右边的柱子上;因此有同学就用分类讨论和最优选择的方法总结为:当要将奇数个构件从左边的柱子上全部移动到右边的柱子上时,第一步最好将第1个构件移到右边的柱子上;当要将偶数个构件从左边的柱子上全部移动到右边的柱子上时,第一步最好将第1个构件移到中间的柱子上。
  有三根柱子,柱子上有若干构件,每次只能移动一块构件,在移动的过程中,大的构件不能压在小的构件上,将所有构件从最左边的柱子上移至最右边的柱子上即告胜利,规定可利用中间的一根柱子作为帮助。(如图)
  分析:当要移动4个构件时,第一步有两种选择,如果第一步移动到右边时,我们会发现,要将所有构件从最左边移动到最右边最少需要23步;如果第一步移动到中间时,我们会发现,要将所有构件从最左边移动到最右边最少只需要15步;这样就会比选择右边时少掉8步!并且在移动的过程中,你会明显感到将3个构件整体移动了两次,这是个多余的步骤。当要移动5个构件时,第一步选择中间的最少步骤就会比第一步选择右边的最少步骤多了16步!
  如果左边的柱子上只有三个构件,你能用最少的步骤将它们按照汉诺塔游戏的规则全部移动到右边的柱上吗?(如图)
http://img.mp.itc.cn/upload/20170320/58eaf0363ada470bb5c7d0bfefc0794c.png
  知道了操作的思路和方法以后,我们就要研究一下,将所有构件从最左边全部移动到最右边时,至少需要移动多少步。通过上面的研究我们发现,移动3个构件至少需要7步,移动4个构件至少需要15步,移动5个构件至少需要31步……,而移动2个构件至少需要3步,移动1个构件至少需要1步。归纳这些情况的规律,我们可以猜测:将构件从最左边的柱子移动到最右边的柱子上至少需要移动2n-1步,并且我们可以证明这个结论是正确的。利用这个规律,我们就可以知道,要将传说中的64块金片从最左边的柱子上移动到最右边的柱子上,庙里的和尚最少需要移动约1.84×1019步,这是一个天文数字,每一步就算只需要1分钟,和尚们不吃不喝也是不可能完成这个任务的。
  解答:将三根柱子从左往右分别设为左、中、右,3个构件从小到大分别设1、2、3,则移动步骤为:1右→2中→1中→3右→1左→2右→1右,最少需要移动7步。
  三个构件你已经学会了吧!那你知道四个构件又该如何移动吗?它们最少需要移动多少步?五个构件呢?赶快试试看吧!(如图)

zhenwelcome 发表于 2019-2-14 06:59:50

LZ{author}真是人才 逐句地看完这个帖子以后,我的心久久不能平静,震撼啊!为什么会有如此好的帖子!我纵横网络bbs多年,自以为再也不会有任何帖子能打动我,没想到今天看到了如此精妙绝伦的这样一篇帖子。

夏娃的诱惑 发表于 2019-3-16 13:36:57

我曾经忘情于汉廷的歌赋,我曾经惊讶于李杜的诗才,我曾经流连于宋元的词曲;但现在,我才知道我有多么浅薄 顶顶多好 楼主你的高尚情怀太让人感动了。
页: [1]
查看完整版本: 探索汉诺塔游戏中的数学奥秘