汉诺塔问题的两种解法(1)
汉诺塔是一种益智玩具，源自古老的印度。如图1、图2及图3所示，有三根柱子，若干个大小不等的圆盘按顺序依次叠落在起点（左侧）的柱子上，通过多次移动后，全部圆盘要叠落在终点（右侧）的柱子上。移动必需遵守两个原则：
每次只能移动一个圆盘；
移动过程中，大圆盘不允许覆盖在小圆盘上。
图1 游戏的初始状态
图2 游戏的中间状态
图3 游戏的结束状态
第一次接触这个游戏，是在一本叫做《具体数学》的书里（图4），第一章讨论的就是这个问题。不得不说《具体数学》是一本非常有趣的书，教你如何将物理世界的问题转化为数学问题（进而才有可能转化为计算机可解的问题），不过阅读它需要一颗闲适的心，以及非常专注的状态。上次读这本书大约是在一年前。
图4 一本与算法有关的数学书
Roadlabs给陶陶同学出了一些练习算法的题，茶余饭后提起了汉诺塔，我想起了这本书，但关于书中陈述的内容已经淡忘了。经不起诱惑的我，放下手头的翻译工作，参与到他们的练习中。为了葆有求解过程中探索与思考的快乐，我们约定好，每个人独立思考，不查资料寻求思路，必要时可以在一起讨论。我们的项目正式开始了。
第一节 解决物理世界中的问题
面对这样一个物理世界中的问题，首先必须在物理世界中找出问题的解，才有可能在这个解的基础上，寻求数学乃至程序的解法。
先从简单的3个圆盘开始，如图5所示，完成任务共需要7个步骤。
图5 三个圆盘的移动方法
此时，建议读者自己在纸上画一画，试试看4个、5个圆盘如何移动，需要多少步骤，是否可以从中发现一些规律。经过反复实践，你会发现如下规律：
移动4个圆盘需要15步，移动5个圆盘需要31步；
移动3个、5个圆盘时，第一步为S→T（从起点移动到终点），移动4个圆盘时，第一步为S→B（从起点移动到缓冲区）；
移动3个、5个圆盘时，最后一步为S→T（从起点移动到终点），移动4个圆盘时，最后一步为B→T（从缓冲区移动到终点）。
关于移动步数，3个盘子7步，4个盘子15步，5个盘子31步，有兴趣的读者通过观察思考，或许会发现其中的规律，如果再结合1个、2个盘子的移动步数，相信你会有所发现。
关于不同数量盘子移动时的第一步与最后一步，不难猜想，它们与盘子数量的奇偶有关，当盘子数为奇数时，第一步要移动到终点，而当盘子数为偶数时，第一步要移动到缓冲区，最后一步也有类似的规律。
经过反复移动不同数量的盘子，你也许会发现更多的规律，并找到在物理世界里解决这一问题的通用办法。这里暂时不揭晓答案，留一些时间让读者思考，切记，不要到网上搜索答案，否则，失去的将是探索与发现的快乐！
==未完待续==