只能在同一根桩柱上,否则若分散在两根或三根桩柱上,是无法移动那两个尺寸相同的最大的圆盘的。因此,移动2n-2个圆盘的最少次数为。●然后移动两个最大圆盘,需要2次。●最后仍需要将2n-2个圆盘移动到两个最大圆盘的上面,还需要次移动。综上并考虑到,可得递归式:,进而可求得:有一点需要说明的是,当移动两个尺寸相同的最大圆盘到其它桩柱后,它们两个互相交换了上下位置。请思考:为什么前2n-2个圆盘中的每两个尺寸相同的圆盘在移动完成后,仍能够保持原来的上下位置关系?解题思路2:在移动这些圆盘时,对每两个尺寸相同的圆盘的移动过程都是先后紧邻次序的进行移动的,因此若将每两个尺寸相同的圆盘看做一个圆盘的话,那么该问题等价于对n个不同尺寸的圆盘进行移动的原始汉诺塔问题。因此,与存在如下关系:(b)设为符合要求的移动2n个圆盘的解。该问题的最终移动结果如下图所示。-9-移动过程分以下几个步骤,其中步骤1、3、5、7均等价于问题(a)的移动规则:Step1:将前2n-2个圆盘从A→C,需移动次,每对同尺寸圆盘将颠倒叠放次序;Step2:将第2n-1号圆盘从A→B,需移动1次;Step3:将前2n-2个圆盘从C→B,需移动次,每对同尺寸圆盘又恢复叠放次序;Step4:将第2n号圆盘从A→C,需移动1次;Step5:将前2n-2个圆盘从B→A,需移动次,每对同尺寸圆盘将颠倒叠放次序;Step6:将第2n-1号圆盘从B→C,需移动1次;Step7:将前2n-2个圆盘从A→C,需移动次,每对同尺寸圆盘又恢复叠放次序。综上,可得:,经计算可得:扩展思考1:双色河内塔包含3个桩柱和2n个圆盘,这些圆盘有n种不同的尺寸,每种尺寸的圆盘有2个且颜色不同。每次只移动一个圆盘,且不能把较大的圆盘放在较小的圆盘上面。如下图所示,若将不同颜色的圆盘移动到不同的桩柱上,那么足够且最少(充分且必要)的移动次数是多少?-10-
全文预览
