4.2. 九连环的秘密

九连环是起源于中国宋代的一种民间智力玩具。它主要由九个硬环组成，每个环上铰接一个柄，后一个环套在前一个环的柄上，柄的末端全部插在一块带孔的板里，可以上下活动，但不能拿出来。所有的环套在一个剑形的框架上。玩法是把环从框架上取下来。

仔细观察可以发现，九连环的结构使它具有以下的特点：

第一环可以随时取下来或者装上去
要想取下或装上某个环，它前面的一环必须在框架上，且前面一环的前面不能有环在框架上

至此，解决问题的方法也就清楚了。用递归的思想，把 n 个环全部解下来就可以分解为以下几个动作：

把前 n-2 个环解下来
把第 n 个环解下来
把前 n-2 个环装上去
把 n-1 个环解下来

事实上不需要考虑得这么复杂。显然，在任何时候只有两个环可以操作，一个是第一环，一个是第一个在框上的环后面那环。对其中的一个进行操作正是你刚刚操作完的那一步的后退。比如刚刚把第一环解下来，那么把它再装回去是没有进展的，你只能去操作另外一个环。因此整个过程就成了对第一环和第一个在框上的环后面那环的交替操作，关键是开始时对哪一个环操作。不难推算，解奇数个环应先对第一环操作，解偶数个环先对第二环操作。

用 1 表示在框上的环，用 0 表示不在框上的环。马上就可以发现，解九连环的过程就是一个用格雷码 (Gray Code) 进行记数的过程。格雷码的特点是相邻两个数字之间只有一个二进制位是不同的。