九连环的解法和代码

发表于 更新于 Disqus：

今天第一次解九连环，觉得这个小玩具还是很有思想的，特把解法整理如下。

首先要明确以下两个事实：

  1. 每个环只有两种状态：套在柄上（记作1），取下来（记作0）。很容易联想到二进制，为了表示的方便，我们把一个九连环的状态记作一串9位的二进制数，最低位对应最外侧的环。

  2. 当且仅当某环是最低位的环，或，它的右一位是1而右边其余位都是0，这两种情况下，该环的状态可以切换（取下或套上）。

（至于怎么操作……那是你的事情了）

解法是递归过程。定义解开\(n\)连环的操作为\(solve(n)\)，它的逆过程为\(rsovle(n)\)，即把\(n\)连环套上去的过程。因为后者只是前者的逆过程，以下只讨论\(solve(n)\)。

\(n=1\)和\(n=2\)的情形都是trivial的，很容易看出： 

1
2
0 -> 1
00 -> 01 -> 11

\(n>2\)的过程如下： 

1
2
3
4
solve(n - 2);
flip(n - 1); // 翻转最高位
rsolve(n - 2);
solve(n - 1);

举个例子更好懂些： 

1
11111 ---> 11000 -> 01000 ---> 01111 ---> 00000

代码在这里，可以输出解法和步骤。