怎样玩九连环……世界三大智力玩具的秘密之九连环！！
我的图书馆
怎样玩九连环……世界三大智力玩具的秘密之九连环！！
一、九连环的历史九连环是中国人的发明，这是没有疑问的。宋代（公元960－1279）已经流行，至少已有800年历史。但究竟何时发明，还有不同的说法。　　1，《战国策·齐策六》：“秦昭王尝遣使者遗君王后玉连环，曰：”齐多智，而解此环否？‘君王后以示群臣，群臣不知解，君王后引锥椎破之，谢秦使曰：“谨以解矣！’”　　2，西汉说。西汉司马相如与妻子通信，妻子回信中有：一别之后，二地相思。都说是三四月，谁又知五六年。七弦琴无心弹，八行书不可传。九连环从中折断，十里长亭望眼欲穿！百思想，千系念。万般无奈，把郎怨。　　3，三国说。认为是诸葛亮发明，这许是由孔明锁推论而来。　　4，红楼梦中有大观园中小姐们玩九连环的描写：在红楼梦第七回，周瑞家的奉薛姨妈之命，送一些宫制的堆纱假花给园子里的姑娘们，每人两朵。找黛玉时，“谁知此时黛玉不在自己房中，却在宝玉房中大家解九连环玩呢”。原书仅此一句。至于哪些人在玩，至少有宝玉黛玉二人，要么还有一些丫环也在凑热闹。但我们后面会看到，九连环的玩法是“只此一手”，会就是会，不会就是不会，也说不上巧解不巧解。二、九连环的发展九连环产生在古代中国，它结构精巧，玩法复杂，更有丰富的数学内涵，是一种优秀的智力玩具。九连环的产生反映了我们中国人的智慧。九连环早已流传到世界各国，西方称之为“中国环” ( The Chinese Rings ,The Chinese Rings Puzzle) 。 2002 年北京世界数学家大会期间，北京科教馆展出一些数学玩具，其中就有九连环。2002年北京世界数学家大会期间举办的展览中展示的数学游戏之一九连环九连环一般由金属丝和板条制成，下面是示意图和实物图：三、九连环的解法玩九连环的基本动作和几个规则& & 九连环由两部分组成，一部分称作“钗”，这是沿用数学教育家许莼舫先生使用的名称，如图。&图 1 钗& & 另一部分主要是由九个环构成的，如下图。这九个环，按照从左到右依次称为第一个到第九个环，或 1 号环到 9 号环。&图 2 九个环部分& & 按照和钗的关系，每个环都有两个状态：在钗上或在钗下，简称在上和在下。图 3 中的九个环都在钗上，而图 4 中的九个环都在钗下。我们用九个数字表示九个环的状态， 0 表示在钗下， 1 表示在钗上。如
表示从左到右第 3 ， 4 ， 8 三个环状钗上，其余的环在钗下。&图3 九个环都在钗上，表示为图4 九个环都在钗下，表示为& & 所谓玩九连环，或者说解九连环，就是把原来不在钗上的环套在钗上，我们称为某环“上去”或者“上”某环；或者相反，使原来在钗上的环不再在钗上，我们称为某环“下来”，或者“下”某环。一般玩九连环，就是当九个环都不在钗上时，把九个环都上上去；或者当九个环都在钗上时，把它们都下下来，也就是从在状态
，或者相反。当然，也可以有其他过程，即从某一个状态到另一个状态。& & 玩九连环，习惯左手拿环的部分，右手拿钗，如图。&玩九连环，右手在反复往返动作，而左手手指在不停的做着把环套上或卸下的动作，正是活动左手的运动。大家都知道，活动左手可以开发右脑，这也是的九连环的一个作用。& & 试着玩几下，就可以发现九连环有三个基本动作，其中只改变一个环的状态的（每次只能把一个环上或者下）有以下两个动作：1. 基本动作1 ．任何时候可以改变 1 号环的状态，即：当 1 号环在上的时候，可以下 1 号环；当 1 号环在下的时候，可以上 1 号环。注意这两个动作只能进行其一。&& & 下面几图表示了这个动作。&图5-1 开始状况 图5－2& &&&1 号环上升图5－3& & 把 1 号环从钗中间向上穿过图5－4 钗稍后移， 1 号环向下倾斜图 5－5 使钗从 1 号环中穿过& & 至此， 1 号环上去了，状态变为
。如果是反过来进行，就是下 1 号环。我们把上或下 1 号环都称作动作P 。&& & 用动画演示如下。2. 基本动作2 ．可以改变第一个在上的环的下一个环（指右边的一个环，如果右边没有环，当然不能做此动作）的状态。注意这里“第一个在上的环”并不是“ 1 号环”。例如，当仅有 1 号环在上时即状态
，这 1 号环就是第一个在上的环，可以改变它右面即 2 号环的状态：原来在上可以下，原来在下可以上。又如当仅有 5 号环和 8 号环在上时即状态
，第一个在上的环是 5 号环，可以改变 6 号环的状态：原来在上可以下，原来在下可以上。操作方法如下图。&图 6-1 状态
，即仅有 5 号和 8 号环在上图 6-2& &&&6号环升高，从拆中穿过图6－3&&钗后退& &图 6 － 4& &6号环降低,钗前移穿过 5 ，6 号环& & 至此， 6 号环上去了，状态变为
。当然，如果是反过来进行，就是下这第二个在上的环。我们把上或下第二个在上的环都称作动作Q 。&& & 用动画演示如下。& & 注意，所有环都在下的状态
，或者仅有最后一个环（第九个环）在上的状态
，是不能做动作 Q的，因为前者没有第一个在上的环，后者第一个在上的环右面没有环了。其他状态都可以做这个动作。&& & 同时改变两个环的状态，仅有一个动作：&3. 简化动作& &1 号 2 号环状态相同时可以同时改变状态，即当 1 号 2 号环都在上时可以一次操作同时下来；当 1 号 2 号环都在下时可以一次操作同时上去。操作与仅 1 号环上或下相似，见下面图示。&图 7－1 状态 图 7－2 第1 ，2 号环上升由钗中穿过图 7-3 钗后移图 5 － 4 第 1,2 号环向下倾斜，钗从中穿过，成为状态 & & 同时上或下 1 号 2 号环称作动作 R。当然，如果 1 ， 2 号环有一个在上而另一个在下，不能进行动作 R。&& & 这样，任何状态都可以进行动作P；除了状态
外，都可进行动作 Q；状态 00******* 或 11******* 可以进行动作 R。九连环只有这三个基本动作可以一次进行，其他动作都是相继进行这三个动作。&& & 有一个重要的限制。每种动作如果连续进行两次，例如 PP，那就是刚上了 1 号环，又下 1 号环；或者刚下了 1 号环，又上 1 号环。又如 QQ，那就是刚上了第二个在上的环，紧跟着又下这个环；或者是刚下了第二个在上的环，紧跟着又上这个环。再如 RR，是刚下了第 1 ， 2 号环，又上这两个环；或者刚上了第 1 ， 2 号环，又下这两个环。这都是刚刚向目标前进了一步，又原路后退一步，白费了功夫，而九连环的状态没有改变。反之，只要不连续做同一个动作，就不会原路退回。因此，在实际玩九连环时，应该规定：&4. 不重复规则&&动作 P、 Q、 R都不可连续重复做两次。&& &&& & 以上四点，就是九连环的玩法的全部依据，可以称为四个规则。&& && & 动作 R是连续进行的 1 号环上、 2 号环上，可以表示为动作 PQ；或者是连续进行的 2 号环下、 1 号环下，可以表示为动作 QP。因此动作 R实际是一种简化。如果限定只用动作 P和动作 Q，不允许使用动作 R，这样玩九连环称作基本玩法。如果除了动作 P， Q，还必须使用动作 R（凡是能用动作 R的场合都必须使用动作 R），称作简化玩法。我们先讨论基本玩法，然后讨论简化玩法。四、基本玩法&九连环与格雷码基本玩法只有两个动作P和Q，而且在状态和只能进行一个动作P，其他状态可以进行两个动作P,Q。打个比喻，就好像一个人沿着一条线走。在线的始点，他只能前进一步。在线的终点，他只能后退一步。在线的中间，他可以向前一步或后退一步。但在具体的一次行进中，为了由某一个位置到另外一个位置，他要么总是向前，要么总是向后，不可一会儿前进一会儿后退，因为那是走回头路，徒劳无益。如果记录他的各步，要么是连续的前进前进再前进，没有后退；要么是连续的后退后退再后退，没有前进。& & 玩九连环当然也是这样，不过，动作P和Q，并不是简单的对应于前进和后退。根据规则4，连续的动作PP，或者QQ，必然是原地不动。所以，如果某个状态下，动作P是前进，那么接下来如果再做动作P就是后退，而动作Q才是前进；反之，如果动作Q是前进，那么接下来的动作中，再做动作Q就是后退而动作P才是前进。记录玩九连环的各步，只能是P和Q相间出现，而不能连续出现P或者连续出现Q。于是，同样是连续的前进前进再前进，没有后退；或者是连续的后退后退再后退，没有前进，但各个动作记录下来却是交错的序列：…PQPQP…。&& & 可以用图来表示如下，并称之为“状态图”。状态图是解决很多趣味数学问题的工具。图中小圆圈表示九连环的状态，称为点，两个小圆圈间的线段表示动作，称为边。下面不再区分九连环的状态和图中的点，也不区分九连环的动作和图中的边。点就是状态，边就是动作。两个点（小圆圈）间的边数（线段数）称为这两个点（即两个状态）间的距离。这也确实就是数学中图论的讨论对象，关于图论的进一步请参看迷宫部分。&图7& & 状态和终点都只连接1条边，相当于路线的端点，也就是玩九连环的过程的两个端点，为了方便讨论，我们规定始点是，终点，其他状态称作中间状态。由于在状态和只能进行动作P，故不论从始点到终点，还是从终点到始点，这个动作序列总是由P开头也由P结束，即动作序列为PQPQPQ…PQPQP。& & 这样，我们只对九连环做了点初步的分析，就已经初步知道玩九连环是怎么一回事了。比如从九个环都在下边，即从状态开始，只要按照PQPQP…做下去，最终会成为，且最后一步动作必是P。反之，如果一开始是终点，仅9号环在上边，也只要按照PQPQP…做下去，最终也会把九个环都下下去成为始点，且最后一步动作也必是P。& & 说是“初步”的会玩，指的是我们还只会机械地连续操作，一旦中断一下，再开始时如果忘记了刚才最后做的是哪个动作，那就惨了，说不定就会会到初始状态去。这原因是我们仅知道了在始点和终点间变化，而从任意一个状态到另外任意一个状态应该怎样操作，还不知道。& & 另外我们还有很多问题没有解决，例如，从始点，按照PQPQP…做下去，最终会成为终点吗？还是永远也到达不了终点？如果能到，要多少步数？九连环有多少不同的状态，从始点，按照PQPQP…做下去，能出现所有的状态吗？解决了这些问题，我们才算是理解了基本玩法。&基本玩法的分析& & 下面讨论几个问题。1．九连环有多少状态？& & 这就是从0，1中可重复的取九个元素做排列，其排列数为29=512，即有512个状态。表示为，，，，，……。2．九连环动作的图真的是这样一条路线吗？或者说，其中有没有分叉，或圈？& & 问得好，提这个问题要有相当的思考习惯和能力。可以证明这个图确实就是一条路线。（1）从状态开始，连续进行动作PQPQPQ…，出现的九连环的状态不会重复。& & 从状态开始，只能进行动作P，下一步必然到达状态。此时可以进行动作P，也可进行动作Q。但根据规则4，只能进行动作Q，得到再下一个状态。如此进行，得到九连环的许多状态。这些状态是不会重复出现的，下面用反证法证明。& & 把出现的一系列状态记作A0, A1, A2, …,An, …，其中A0是始点。我们依次检查每个新出现的状态，假设第一个出现与它前面的状态有重复的是状态An，而与它重复的状态是Ak(0≤k＜n)，如图。图8& & 也就是说，在A0, A1, A2, …,An中，只有Ak=An，其他再无相同的点。考虑Ak与几个不同的点相连。首先，Ak与An－1相连，又与Ak+1相连。如果k＞0（即Ak不是始点），Ak还与Ak－1相连。因此如果Ak是中间状态，它与三个点Ak－1,Ak,An-1相连，但我们知道，任何一个中间点顶多与两个点相连，矛盾,故不会有k＞0。如果k=0（即Ak是始点），Ak也与两个状态Ak+1,An－1相连，但始点只与一个点相连，也是矛盾。因此，不可能有Ak=An。& & 这就证明了在状态系列A0, A1, A2, …,An…中，不会出现重复的状态。（2）动作序列是有限的，不能无限进行。& & 如果这个动作序列可以无限进行，而得到无限多的彼此不同的状态。但九连环的状态总数是有限的（不会超过512），不可能出现无穷多多彼此不同的状态，所以必然到达某一个状态停止。& & 进一步，到达哪个状态停止呢？我们是从状态开始的，其他任何状态都联系于两个不同的动作P和Q，只有终点例外。到了这个状态，只能进行动作P，而不能进行动作Q。由于刚刚是由动作P来的，一个动作不能连续进行，故到此不能再继续进行任何动作。因而操作停止于此。& &即，九连环由状态开始，按照PQPQP…进行，经历各个不同的状态，必然到达状态停止。& & 证完。& & 我们知道了，这个图确实如上面画的一样。于是，状态和终点相当于玩九连环的过程的两个端点，这也就是我们称为始点，为终点，其他状态称作中间状态的原因。我们的动作序列确实是PQPQP…PQPQP。3．从始点到终点的过程是否穷尽了九连环的全部状态？或者说，是否有某个状态不能由这个过程实现？& & 序列PQPQP…PQPQP中，首尾字母相同，一共有奇数个字母，相当于玩九连环的奇数个动作；而每个动作的前后都是九连环的状态，这些状态各不相同，当然九连环的全部状态是偶数个。这些状态是否就是前面得出的512个，还没有说明。这个问题并不是没有意义的，例如魔方的状态总数也是有限的，但从魔方的某一个状态开始，所能达到的状态数，并不等于魔方的全部状态数。请参见魔方部分。九连环的操作相对简单，因为按照规则1，2，4，任何状态都只能进行一个动作，我们依次写出这有限的动作，就得到有限个状态，只要数一数是否够512就行了。假定从始点开始，试写如下& &&&初始& && & 0& && & 动作P& && & 1& && & 动作R& && & 2& && & 动作P& && & 3& && & 动作R& && & 4& && & 动作P& && & 5& && & 动作R& && & 6& && & 动作P& && & 7& && & 动作R& && & 8& && & 动作P& && & 9& && & 动作R& && &10& && & 动作P& && &11& && & 动作Q& && &12& && & ……& & 算了，这样的事情太枯燥无味了，还是交给电脑去做吧。编一个小程序，很容易得出所有的状态。程序的思路是这样的：定义一个数组a(0－9)， a(0)表示当前是第几个状态，a(1)到a(9)表示此时各环的状态。初始时，数组的各值都为0，a(0) =a(1)= …=a(0)=0 ，表示在第0个状态时，所有的环都在钗下。到了第k个状态所进行的操作是：如果k是偶数，进行操作P，改变a(1)=1－a(1)；如果a(0)是奇数，进行操作Q：在a(1) 到a(8)中找第一个1，如a(i)=1，改变a(i+1)=1－a(i+1)。如果某时刻该进行动作Q，而a(1) 到a(8)中没有1时，就停止。每进行一步，a(0)即步数增加1。这个程序就是再现了前面的规则1，2，4。运行程序，可以得出九连环的所有状态。这里只写出一些，全部状态见附录。& && && && && && && && && && &&&初始,&&第& &0个状态:& && && && && && && && && && &&&&动作P, 第& &1个状态:&&动作R, 第& &2个状态:&&&动作P, 第& &3个状态:&&&动作R, 第& &4个状态:&&&动作P, 第& &5个状态:&&&动作R, 第& &6个状态:&&&动作P, 第& &7个状态:&&&动作R, 第& &8个状态:&&&动作P, 第& &9个状态:&&&动作R, 第&&10个状态:&&&动作P, 第&&11个状态:&&&动作R, 第&&12个状态:&& && &&&┆& && &&&┆&&动作P, 第 501个状态:&&&动作R, 第 502个状态:&&&动作P, 第 503个状态:&&&动作R, 第 504个状态:&&&动作P, 第 505个状态:&&&动作R, 第 506个状态:&&&动作P, 第 507个状态:&&&动作R, 第 508个状态:&&&动作P, 第 509个状态:&&&动作R, 第 510个状态:&& && && && && && && && && && &&&动作P, 第 511个状态:& && && && && && && && && && && &&&& & 我们发现，从第0到第511，恰好是512个状态。前面已经证明了这些状态各不相同；而九连环的全部可能状态也恰是512个，于是我们的过程中出现的状态就是九连环的全部状态。这也说明，从始点到终点，共511步。& & 由上表可以看出，从始点到仅第1个环在上状态用1步，到仅第2个环在上状态用3步，到仅第3个环在上状态用7步，等等。如果对二进制数熟悉，立刻看出，步数写为二进制数依次是：1，11，111，等等。21-1=1，22-1=3，23-1=7,当然，一般，从始点到仅有第k环在上的状态所需步数是2k-1。4．大家都习惯从始点到状态即九个环都在上的状态，查查附录，看到在512个状态里编号为341，即用341步。那么到前个k环在上需要多少步？& & 我们来解决这个问题。& & 记从始点到前k个环在上用f(k)步，考虑怎么上这前k个环呢？可以先上前k－1个环，用f(k－1)步，再下前k－2个环，用f(k－2)步。此时仅有第k－1个环在上，可以进行动作Q上k号环，用1步，然后再上前k－2个环，用f(k－2)步。f(k)就是以上各个动作所需步数的和，& & f(k)=f(k－1)+f(k－2)+1+f(k－2) =f(k－1)+2f(k－2)+1& & 即& &f(k) =f(k－1)+2f(k－2)+1& && && && && && && && && && && && &&&& & 这是确定函数关系的一种方法，叫做递归方法，与大家熟知的数学归纳法的原理有相似之处。如果知道了f(1),f(2)的值，由此可以计算出f(3)，有了f(3)，与f(2)一起又可以计算f(4)，等等，直到f(9)，或者更一般的f(k)。当然，这必须先知道f(1),f(2)的值，这犹如数学归纳法里的归纳假设。容易知道，f(1)=1,f(2)=2。所以由& & f(k) =f(k－1)+2f(k－2)+1,f(1)=1,f(2)=2& && && && && && && && && & 可以确定f(k)的各个取值，依次得出f(1)=1f(2)=2f(3)=2+2×2+1=5f(4)=5+2×2+1=10f(5)=10+2×5+1=21f(6)=21+2×10+1=42f(7)=42+2×21+1=85f(8)=85+2×42+1=170f(9)=170+2×85+1=341& & 既然对任何正整数k，都可以得f(k)的值，这实际上已经确定了函数关系f(k)。但我们还是希望得出这个函数关系的解析表达式。& & 递推式（2）也叫做递归方程，由（2）寻找函数关系f(k)的解析表达式，称作解递归方程。& & 要确定一个未知函数f(k)的函数关系的方程是函数方程。函数方程的内容很丰富，一般的函数方程也不容易解，不过很幸运，我们见到的递归方程是最简单的一种，还是容易解的。在别的章节里还会遇到递归方程，下面我们来讨论一般解法。& & 先看一个简单的例子f(k)=a*f(k－1)，这里f(k)的函数关系是什么呢？我们递推几次看看。& & f(k)=a*f(k－1) =a2*f(k－2) =a3*f(k－3) =a4*f(k－4)= …& & 如此递推，总会到达ak-1*f(1)，而f(1)是一个常数，实际上它是可以任意取值的。这样，我们自然会想起学过的指数函数Aan应该是个解，它恰好满足Aak=aAak-1，其中方程中的a就是指数函数的底数，A是待定系数。& & 稍微复杂一点，方程中有个常数项：f(k)=a*f(k－1)+b ,有& & f(k)=af(k－1)+b=a（af(k－1)+b=）+b=a2*f(k－2)+ab+b，记作a2*f(k－2)+ b1，即& & f(k)=a2*f(k－2)+ b1& && &&&=a3*f(k－3)+ b2& && &&&=a4*f(k－4)+ b3& && &&&…& && &&&=ak-1*f(1)+ b(k－1)& & 总之，解的形式是f(k)=Aak+B，A,B是待定系数。例 解方程f(k)=3f(k－1)+2,f(1)=5& & 解 设a=3,可设f(k)=A3k+B，带入方程，得A3k+B=3(A3k-1+B)+2，即A3k+B=A3k+3B+2，故B=－1。再以f(1)=5代入,5=A*3－1,得A=2，于是方程的解是f(k)=2*3k-1较复杂一些，考虑f(k)=af(k－1)+bf(k－2)。受上面的启发，我们尝试寻找指数函数的解，先设底数为x，设f(k)=Axk，代入方程得Axk=aAxk-1+bA=Axk-2& && & 约去公因式得x2=ax+b& & 此式给我们非常重要的启示，它说明指数函数f(k)=Axk如果是解，其底数必为上面的一元二次方程的根。反之，也容易验证当x满足x2=ax+b时，f(k)=Axk确实是解。但二次方程有两个根x1，x2，两根不等时，f(k)=Ax1k与f(k)=Ax2k都是解，实际上一般解是二者之和f(k)=Ax1k+Bx2k&&& & 进一步讨论可以知道，如果方程中有个常数项，解为f(k)=Ax1k+Bx2k +C 。现在来解上面讨论九连环的方程& && && &&&f(k)=f(k－1)+2f(k－2)+1,f(1)=1,f(2)=2& && && && && && && && && && &（3）& & 这里a=1,b=2,二次方程x2=x+2有两个根－1，2，故可设f(k)=A2k+B(－1)k+C，代入方程(2)得& && && && && && &A2k+B(－1)k+C=A2k-1+B(－1)k-1+C+2(A2k-2+B(－1)k-2+C)+1& & 类似前例解法，首先得出C=3C+1,故C=－1/2，因而f(k)=A2k+B(－1)k-1/2。再以f(1)=1,f(2)=2代入，得2A－B－1/2=1,4A+B－1/2=2,解出A=2/3,B=－1/6，我们得到了f(k)=2k+1/3-(－1)k/6-1/2=(2k+2-(－1)k-3)/6& & 这个表达式中含有分数，但对正整数k，f(k)都是正整数。如果对k按照奇偶数讨论，也可以写为：& & 我们还可以看到，如果k为奇数，，而如果k为偶数，即& & 这也是递推式。& & 计算得出f(1)= 1f(2)= 2f(3)= 5f(4)= 10f(5)= 21f(6)= 42f(7)= 85f(8)= 170f(9)= 341& & 与前面一致。& & 从始点到前奇数个环在上的状态需要用奇数步，因而最后一步是动作P；反之，从前奇数个环在上的状态到始点，第一步也是动作P。从始点到前偶数个环在上的状态，需用偶数步，因而最后一步是动作Q；反之，从前偶数个环在上的状态到始点，第一步也是动作Q。5．还有一个问题，如果我们不是从始点到终点，而是从任意一个状态到另一个状态，应该如何进行九连环的操作，又需要多少步呢？解决这个问题，只要知道从始点到任意一个状态的步数就可以了。状态是用数字0，1的序列表示的，如，这好像是二进制数。但仔细看一下附录，就知道其实不是那么回事。试看前20个状态：第 0个状态:的二进制数：第 1个状态:的二进制数：第 2个状态:的二进制数：第 3个状态:的二进制数：第 4个状态:的二进制数：第 5个状态:的二进制数：第 6个状态:的二进制数：第 7个状态:的二进制数：第 8个状态:的二进制数：第 9个状态:的二进制数：第 10个状态:的二进制数：第 11个状态:的二进制数：第 12个状态:的二进制数：第 13个状态:的二进制数：第 14个状态:的二进制数：第 15个状态:的二进制数：第 16个状态:的二进制数：第 17个状态:的二进制数：第 18个状态:的二进制数：第 19个状态:的二进制数：第 20个状态:的二进制数：& & 首先想到，二进制数的是个位置右边，从右向左位数逐渐增加，而九连环1号环状左边，从左向右环岛号数逐渐增加。因此我们把状态数字表示倒过来写以符合一般的习惯：&第 0个状态倒置:的二进制数：第 1个状态倒置:的二进制数：第 2个状态倒置:1&2的二进制数：0第 3个状态倒置:0&3的二进制数：1第 4个状态倒置:000000110 4的二进制数：000000100第 5个状态倒置:000000111 5的二进制数：000000101第 6个状态倒置:000000101 6的二进制数：000000110第 7个状态倒置:000000100 7的二进制数：000000111第 8个状态倒置:000001100 8的二进制数：000001000第 9个状态倒置:000001101 9的二进制数：000001001第 10个状态倒置:000001111&10的二进制数：000001010第 11个状态倒置:000001110&11的二进制数：000001011第 12个状态倒置:000001010 12的二进制数：000001100第 13个状态倒置:000001011 13的二进制数：000001101第 14个状态倒置:000001001 14的二进制数：000001110第 15个状态倒置:000001000&15的二进制数：000001111第 16个状态倒置:000011000 16的二进制数：000010000第 17个状态倒置:000011001 17的二进制数：000010001第 18个状态倒置:000011011&18的二进制数：000010010第 19个状态倒置:000011010&19的二进制数：000010011第 20个状态倒置:000011110 20的二进制数：000010100& & 状态倒置的表示各不相同，当然也可以表示一定的次序，例如我们规定就用000表示0，001表示1，011表示2，010表示3，又有何不可呢？但如果我们不能比较方便的使这种表述与通常的十进制数或二进制数换算，那还是无法应用。我们来看看它与二进制数的关系。&& & 上面列举了20步以内的状态倒置与二进制数，并用粗体标出了二者不同的数字。先看二进制数，考察其中粗体字的位置，可以发现，如果某一数字的左边是1，改变它（1变为0，0变为1），而而如果某一数字左边是0，它保持不变（1仍是1，0仍是0），就成了状态倒置。例如19的二进制数是000010011，其中第1位数1和第4位数0的左边都是1，把这两个数字改变，即第1位数的1变为0，第4位数的0变为1，就成为，恰好是状态倒置。在具体做时，可以从右向左进行。&& & 再看状态倒置，我们比较一下同一个数的二进制表示和状态倒置。数字0，1的二进制数和状态倒置是一样的，都是0，1。但数字2，3就不同了，分别是10，11和11，10。右数第二位都是1，但第一位的数字恰好相反。这其实很好理解，因为二进制数是“逢二进一”，而状态倒置由于规则4的限制，当出现如这样的状态倒置时，要得到下一个状态倒置，不能改变个位，只能在更高位加一，成为，然后再从右数第一位开始，同样由于规则4，只能按照上面的过程“倒过来”进行（说倒过来，其实不准确，因为高位不同），因此必然数字都相反，就是0011成了1100，等。& & 这样给我们一个方法：在状态倒置里，凡是数字1，把它右边的所有数字都变化一下（0变为1，1变为0），就是相应的二进制数。&& & 例如，19的状态倒置是，从右向左，第2位是1，把它右边的0改为1，成了；第4位是1，把它右边的011改为100，成了；第5位也是1，再把它右边的1100改为0011，成了，恰好是19的二进制数。当然，0，1互换，换两次等于没换，故实际上是某一个数字的左边有奇数个1时，改变它；有偶数个1时，不动。具体做时，也应从右向左进行。& & 这样我们就可以轻易地在状态倒置和二进制数间转换。& & 实际上，我们的状态倒置，与编码理论中的 格雷码不谋而合，它的特点是相邻的数字的表示只有一个数字不同，这正好是九连环每次只改变一个环的状态一致。由于这个特点， 格雷码在计算机中有重要的理论与实际意义。关于 格雷码，可以参考有关书籍。 把前面的变换方法，写为口诀，二G一改零不改，G二奇变偶不变& & 就是由二进制数到 格雷码，某一数字的左边是1，它改；是0，不改。由 格雷码到二进制数，某一数字的左边数字和是奇数，变；是偶数，不变。&& & 例 状态是第一个状态？从它向终点的方向进行5步操作得到什么状态？&& & 解 状态倒置为，相应二进制数是，十进制数是395，向初始点5步，为400，二进制数，状态倒置是，状态是。&& & 例 九连环由状态到状态，要进行多少步操作？第一个动作是什么？& & 解 初始状态，倒置即 格雷码为，二进制数，十进制数228。终止状态，倒置即 格雷码为，二进制数，十进制数203。因为228大于203，故应向始点进行（即反向进行），一共要进行228－203=25步。下一个状态应为第227个状态，227的二进制数是， 格雷码即状态倒置是， 状态为，与初始状态对比，应下3号环。五、九连环的简单解法 换算简单玩法简单玩法就是除了使用动作 P,Q，还可以用动作R，因此它是基本玩法的一个简化。前面已经知道，动作R就是两个相继进行的动作上 1 号与 2 号环，记作 PQ，或者动作下 2 号与 1 号环，记作 QP。但先上 1 号再下 2 号，虽也记作PQ，但不能改为动作R；同样，先下 2 号再上 1 号，虽也记作QP，也不能改为动作 R。&简单玩法的前面几步出现的状态列举如下：&初始,&&第 0个状态:动作R, 第 2个状态:动作P, 第 3个状态:动作Q, 第 4个状态:动作P, 第 5个状态:动作R, 第 7个状态:动作Q, 第 8个状态:动作R, 第 10个状态:动作P, 第 11个状态:动作Q, 第 12个状态:动作P, 第 13个状态:动作R,第 15个状态:动作Q, 第 16个状态:动作R,第 18个状态:动作P, 第 19个状态:动作Q, 第 20个状态:动作P, 第 21个状态:动作R,第 23个状态:1 ．从始点到仅有k号环在上的状态要多少步呢？可以看出，省去的动作是第 1 ， 6 ， 9 ， 14 ， 17 ， 22 个等，是第8k+1,8k－2 个动作。简单说来就是每 4 步省去 1 步，而从始点到仅有 k号环在上的状态的基本玩法的步数是2k-1，故当k&1时简单玩法的步数为3*2k-2-1，k=1 时当然是 1 步。这个序列是： 1 ， 2 ， 5 ， 11 ， 23 ， 47 ， 95 ， 197 ， 383 。&2 ．从始点到前k个环在上的状态要多少步？&递归方程与基本玩法一样，但初始值不同。&& && && & g(k)=g(k－1)+2g(k－2)+1,g(1)=1,g(2)=1& && && && && && && && && &&&（4）&还是设g(k)=A2k+B(－1)k+C，代入方程得&& && && && && & A2k+B(－1)k+C=A2k-1+B(－1)k-1+C+2(A2k-2+B(－1)k-2+C)+1依然C=－1/2。 再由g(1)=1,g(2)=1 ，得出A=1/2，B=-1/2。于是&& && && && && && && && && &g(k)=2k/2-(－1)k/2-1/2=(2k-(－1)k-1)/2或者，当k为奇数时，g(k)=2k-1 ; 当k为偶数时，g(k)=2k-1-1。这样可以计算出&g(1)=1,g(2)=1,g(3)=4,g(4)=7,g(5)=16g(6)=31,g(7)=64,g(8)=127,g(9)=256故 9 环全部上去，所需步数按照基本玩法是 341 步，按照简单玩法是 256 步。&基本解法步数与简单解法步数的换算进一步考虑，到某一个状态（不一定是前面若干个环全部上去），如果完整步数是N，简单步数N0，二者如何换算呢？实际上，可以看出，由初始开始，每经过完整步数8步，简单步数可省略2步成为6步。余数达到2时再省略1步；达到7时再省略1步。因此简单步数N0是其中运算 [x]表示实数x的整数部分,r是N除以8的余数。这样，我们不但可以知道从任何一个状态到另一个状态用完整解法需要多少步，用简单解法又需要多少步，而且可以知道下一步的动作是什么。（除去两个状态和，任何状态下都可以转变为两个状态，即有两个动作。）再举一个例子。例 设九连环的初始状态是
，要求终止状态是
，简单解法与完整解法各需要多少步？第一步是什么动作？解 （1）初始状态
， 格雷码是，转换为二进制数是，相应十进制数是141。终止状态是， 格雷码是，转换为二进制数是，相应十进制数是327。二者差326－141＝186，完整解法需要186步。（2）由于初始状况141小于终止状况327，第一步应成为142，相应二进制是，转换为 格雷码是，状态是，与原状态比较，第一步应上第2环。（3）简单解法步数,我们由141，327分别求相应的简单步数，对于N=141,得到N0=106；对于 N=327,N0=245。二者差139，故简单步数139。这些结果很容易在下一页九连环电脑游戏上验证。
TA的推荐TA的最新馆藏[转]&
喜欢该文的人也喜欢}