九连环的解法和代码

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

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

  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

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