经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。
汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往上按大小顺序摞着 64
片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一回只能移动一个圆盘。有预言说,这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩,当然这个传说并不可信,如今汉诺塔更多的是作为一个玩具存在。Odiosee就收到了一个汉诺塔玩具作为生日礼物。初始状态下,所有盘子都自底向上从大到小排列在第一根柱子A上,要求移动到第三根柱子C上。
下面的问题就是:当小A在一次游戏中使用了 N
个盘子时,他最少需要多少次移动才能把他们都移到第三个柱子上?输出操作步骤。