汉诺塔19世纪后期由法国数学家埃德沃德 · 卢卡斯发明的一个流行的游戏叫做汉诺塔，它由安装在一个板上的3根柱子和若千大小不同的盘子构成。开始时，这些盘子按照大小的次序放在第一根柱子上， 大盘子在底下(如图所示)。[img=709x335]17988e004cd33b3.png[/img]游戏的规则是:每一次把1个盘子从一根柱子移动到另-.根柱子，但是不允许这个盘子放在比它小的盘子上面。游戏的目标是把所有的盘子按照大小的次序都放到第二根柱子上，并且将最大的盘子放在底部。令[tex=1.286x1.214]IFb1VZrhzWFzgLztPGR0BA==[/tex]表示解[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个盘子的汉诺塔问题所需要的移动次数。建立一个关于序列[tex=2.286x1.357]MR0HEzSQTHn7ZK5WMW8S/PKyI26Y0n5gcYF9C9+Fh0s=[/tex]的递推关系。
举一反三
- 汉诺塔（Tower of Hanoi）是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。编写一个函数，用递归算法实现汉诺塔问题，输入A柱子上的盘子个数，打印输出搬动盘子顺序。
- 对于汉诺塔问题，假设盘子从上到下编号1，2，3，...，现在要把1号柱子上的n个盘子移到3号柱子，2号柱子为辅助。如果用(a,b,c)表示将编号a的盘子从b柱子移到c柱子，那么下面哪个列表表示两个盘子的解决方法？ A: [(1,2,2),(2,1,3),(1,2,3)] B: [(1,1,2),(2,1,3),(1,3,3)] C: [(1,1,2),(1,2,3),(1,2,3)] D: [(1,1,2),(2,1,3),(1,2,3)]
- 对于汉诺塔问题，假设盘子从上到下编号1，2，3，...，现在要把1号柱子上的n个盘子移到3号柱子，2号柱子为辅助。如果用(a,b,c)表示将编号a的盘子从b柱子移到c柱子，那么下面哪个列表表示两个盘子的解决方法？ A: [(1,2,2),(2,1,3),(1,2,3)] B: [(1,1,2),(2,1,3),(1,3,3)] C: [(1,1,2),(1,2,3),(1,2,3)] D: [(1,1,2),(2,1,3),(1,2,3)]
- 盘子数为4的汉诺塔问题需要移动盘子的次数为 （ ）? 16|15|7|8
- 盘子数为4的汉诺塔问题需要移动盘子的次数为 （