玩玩汉诺塔
编程
jeff
2
汉诺塔
朋友家有个八层的小汉诺塔.好玩心起我忍不住玩了一下,不料却一玩停不了手.从一开始要花三十分钟把八块塔片移动另一条柱子上,四次之后变成五分钟内完成,最后演变成手指速度的考验.汉诺塔的移动规律已了然于心.最好成绩是3分钟左右,玩下来后,唯一感觉就是手累.
汉诺塔的玩法很简单,就是要玩家把串在某一条柱子上的所有塔片都移动到另一条柱了,要求在移动过程中:
1.不能用大片压在小片上面
2.一次只能移动一片
3.塔片只能够在三条柱子中间转移,不能离开三条柱子.
我发现了一些规律:
1.按源柱的塔片数目算,如果是奇数,第一步先移往目标柱,反之则移往附助柱.
2.重复动作一直在重复.如在两次连续移动当中肯定有一个移动是最小的塔片的移动.也就是说小塔片的移动占了所有移动的一半.
3.过程中不断地变化三个柱子的身份,源柱,输助柱与目标柱.
后来在网上找到更有概括性的文字:
1.如果只有一个金片，则把该金片从源移动到目标棒，结束。
2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒
这是很明显的递归算法..既然这样,何不写一段代码算算自己三分多钟里面称动了多少次塔片:
- def hano(count,source,target,help):
- if count == 1:
- print '%s -> %s'%(source,target)
- else:
- hano(count - 1,source,help,target)# 前N-1个移动附助
- print '%s -> %s'%(source,target)
- hano(count - 1,help,target,source)# 移动前N-1个到目标塔.
- hano(3,'B','A','C')
上面就是完整的汉诺塔的移动算法了.hano(3,'B','A','C')的意思是将三阶的汉诺塔从B柱移动到A柱.最后过程是这样的:
B -> A
B -> C
A -> C
B -> A
C -> B
C -> A
B -> A
三阶的汉诺塔移动的总次数为7次,换成8阶算了一下是255次.也就是说N阶的汉诺塔需要移动次数为2的N次方减1次.难怪说64阶的汉诺塔是一座庙里的和尚穷尽一生都不能移完的.我试一下把第一个参数换成了64,得到的结果是MemoryError.太牛了...计算机如此,何况人捏...要知道64阶的结果是18446744073709551615.
接下来再写程序分别计算一下每一个塔片的移动次数和行踪..
