基本玩法只有两个动作P和Q，而且在状态000000000和000000001只能进行一个动作P，其他状态可以进行两个动作P,Q。打个比喻，就好像一个人沿着一条线走。在线的始点，他只能前进一步。在线的终点，他只能后退一步。在线的中间，他可以向前一步或后退一步。但在具体的一次行进中，为了由某一个位置到另外一个位置，他要么总是向前，要么总是向后，不可一会儿前进一会儿后退，因为那是走回头路，徒劳无益。如果记录他的各步，要么是连续的前进前进再前进，没有后退；要么是连续的后退后退再后退，没有前进。

    玩九连环当然也是这样，不过，动作P和Q，并不是简单的对应于前进和后退。根据规则4，连续的动作PP，或者QQ，必然是原地不动。所以，如果某个状态下，动作P是前进，那么接下来如果再做动作P就是后退，而动作Q才是前进；反之，如果动作Q是前进，那么接下来的动作中，再做动作Q就是后退而动作P才是前进。记录玩九连环的各步，只能是P和Q相间出现，而不能连续出现P或者连续出现Q。于是，同样是连续的前进前进再前进，没有后退；或者是连续的后退后退再后退，没有前进，但各个动作记录下来却是交错的序列：…PQPQP…。

    可以用图来表示如下，并称之为“状态图”。状态图是解决很多趣味数学问题的工具。图中小圆圈表示九连环的状态，称为点，两个小圆圈间的线段表示动作，称为边。下面不再区分九连环的状态和图中的点，也不区分九连环的动作和图中的边。点就是状态，边就是动作。两个点（小圆圈）间的边数（线段数）称为这两个点（即两个状态）间的距离。这也确实就是数学中图论的讨论对象，关于图论的进一步请参看迷宫部分。

图7

    状态000000000和终点000000001都只连接1条边，相当于路线的端点，也就是玩九连环的过程的两个端点，为了方便讨论，我们规定始点是000000000，终点000000001，其他状态称作中间状态。由于在状态000000000和000000001只能进行动作P，故不论从始点到终点，还是从终点到始点，这个动作序列总是由P开头也由P结束，即动作序列为PQPQPQ…PQPQP。

    这样，我们只对九连环做了点初步的分析，就已经初步知道玩九连环是怎么一回事了。比如从九个环都在下边，即从状态00000000开始，只要按照PQPQP…做下去，最终会成为000000001，且最后一步动作必是P。反之，如果一开始是终点000000001，仅9号环在上边，也只要按照PQPQP…做下去，最终也会把九个环都下下去成为始点00000000，且最后一步动作也必是P。

    说是“初步”的会玩，指的是我们还只会机械地连续操作，一旦中断一下，再开始时如果忘记了刚才最后做的是哪个动作，那就惨了，说不定就会会到初始状态去。这原因是我们仅知道了在始点和终点间变化，而从任意一个状态到另外任意一个状态应该怎样操作，还不知道。

    另外我们还有很多问题没有解决，例如，从始点，按照PQPQP…做下去，最终会成为终点000000001吗？还是永远也到达不了终点？如果能到，要多少步数？九连环有多少不同的状态，从始点，按照PQPQP…做下去，能出现所有的状态吗？解决了这些问题，我们才算是理解了基本玩法。

基本玩法的分析

    下面讨论几个问题。

1．九连环有多少状态？

    这就是从0，1中可重复的取九个元素做排列，其排列数为29=512，即有512个状态。表示为000000000，100000000，010000000，110000000，001000000，……。

2．九连环动作的图真的是这样一条路线吗？或者说，其中有没有分叉，或圈？

    问得好，提这个问题要有相当的思考习惯和能力。可以证明这个图确实就是一条路线。

（1）从状态000000000开始，连续进行动作PQPQPQ…，出现的九连环的状态不会重复。

    从状态000000000开始，只能进行动作P，下一步必然到达状态100000000。此时可以进行动作P，也可进行动作Q。但根据规则4，只能进行动作Q，得到再下一个状态。如此进行，得到九连环的许多状态。这些状态是不会重复出现的，下面用反证法证明。

    把出现的一系列状态记作A0, A1, A2, …,An, …，其中A0是始点000000000。我们依次检查每个新出现的状态，假设第一个出现与它前面的状态有重复的是状态An，而与它重复的状态是Ak(0≤k＜n)，如图。

word/media/image2.gif
图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），不可能出现无穷多多彼此不同的状态，所以必然到达某一个状态停止。

    进一步，到达哪个状态停止呢？我们是从状态000000000开始的，其他任何状态都联系于两个不同的动作P和Q，只有终点000000001例外。到了这个状态，只能进行动作P，而不能进行动作Q。由于刚刚是由动作P来的，一个动作不能连续进行，故到此不能再继续进行任何动作。因而操作停止于此。

   即，九连环由状态000000000开始，按照PQPQP…进行，经历各个不同的状态，必然到达状态000000001停止。
    证完。

    我们知道了，这个图确实如上面画的一样。于是，状态000000000和终点000000001相当于玩九连环的过程的两个端点，这也就是我们称000000000为始点，000000001为终点，其他状态称作中间状态的原因。我们的动作序列确实是PQPQP…PQPQP。

3．从始点到终点的过程是否穷尽了九连环的全部状态？或者说，是否有某个状态不能由这个过程实现？

    序列PQPQP…PQPQP中，首尾字母相同，一共有奇数个字母，相当于玩九连环的奇数个动作；而每个动作的前后都是九连环的状态，这些状态各不相同，当然九连环的全部状态是偶数个。这些状态是否就是前面得出的512个，还没有说明。这个问题并不是没有意义的，例如魔方的状态总数也是有限的，但从魔方的某一个状态开始，所能达到的状态数，并不等于魔方的全部状态数。请参见魔方部分。九连环的操作相对简单，因为按照规则1，2，4，任何状态都只能进行一个动作，我们依次写出这有限的动作，就得到有限个状态，只要数一数是否够512就行了。假定从始点000000000开始，试写如下

     
 初始       0       000000000
动作P       1       100000000
动作R       2       110000000
动作P       3       010000000
动作R       4       011000000
动作P       5       111000000
动作R       6       101000000
动作P       7       101100000
动作R       8       111100000
动作P       9       011100000
动作R      10       010100000
动作P      11       010110000
动作Q      12       110110000
……

    算了，这样的事情太枯燥无味了，还是交给电脑去做吧。编一个小程序，很容易得出所有的状态。程序的思路是这样的：定义一个数组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个状态:000000000                              
  动作P, 第   1个状态:100000000
  动作R, 第   2个状态:110000000
  动作P, 第   3个状态:010000000
  动作R, 第   4个状态:011000000
  动作P, 第   5个状态:111000000
  动作R, 第   6个状态:101000000
  动作P, 第   7个状态:001000000
  动作R, 第   8个状态:001100000
  动作P, 第   9个状态:101100000
  动作R, 第  10个状态:111100000
  动作P, 第  11个状态:011100000
  动作R, 第  12个状态:010100000
        ┆
        ┆
  动作P, 第 501个状态:111100001
  动作R, 第 502个状态:101100001
  动作P, 第 503个状态:001100001
  动作R, 第 504个状态:001000001
  动作P, 第 505个状态:101000001
  动作R, 第 506个状态:111000001
  动作P, 第 507个状态:011000001
  动作R, 第 508个状态:010000001
  动作P, 第 509个状态:110000001
  动作R, 第 510个状态:100000001
                                动作P, 第 511个状态:000000001                                  

    我们发现，从第0到第511，恰好是512个状态。前面已经证明了这些状态各不相同；而九连环的全部可能状态也恰是512个，于是我们的过程中出现的状态就是九连环的全部状态。这也说明，从始点000000000到终点000000001，共511步。

    由上表可以看出，从始点到仅第1个环在上状态100000000用1步，到仅第2个环在上状态010000000用3步，到仅第3个环在上状态001000000用7步，等等。如果对二进制数熟悉，立刻看出，步数写为二进制数依次是：1，11，111，等等。21-1=1，22-1=3，23-1=7,当然，一般，从始点000000000到仅有第k环在上的状态所需步数是2k-1。

4．大家都习惯从始点到状态111111111即九个环都在上的状态，查查附录，看到在512个状态里111111111编号为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)=1
f(2)=2
f(3)=2+2×2+1=5
f(4)=5+2×2+1=10
f(5)=10+2×5+1=21
f(6)=21+2×10+1=42
f(7)=42+2×21+1=85
f(8)=85+2×42+1=170
f(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按照奇偶数讨论，也可以写为：

word/media/image3.gif

    我们还可以看到，如果k为奇数，

word/media/image4.gif

，而如果k为偶数，

word/media/image5.gif

即

word/media/image6.gif

    这也是递推式。

    计算得出

f(1)= 1
f(2)= 2
f(3)= 5
f(4)= 10
f(5)= 21
f(6)= 42
f(7)= 85
f(8)= 170
f(9)= 341

    与前面一致。

    从始点000000000到前奇数个环在上的状态word/media/image7.gif需要用奇数步，因而最后一步是动作P；反之，从前奇数个环在上的状态到始点，第一步也是动作P。从始点000000000到前偶数个环在上的状态word/media/image8.gif，需用偶数步，因而最后一步是动作Q；反之，从前偶数个环在上的状态到始点，第一步也是动作Q。

5．还有一个问题，如果我们不是从始点000000000到终点000000001，而是从任意一个状态到另一个状态，应该如何进行九连环的操作，又需要多少步呢？解决这个问题，只要知道从始点到任意一个状态的步数就可以了。状态是用数字0，1的序列表示的，如001101001，这好像是二进制数。但仔细看一下附录，就知道其实不是那么回事。试看前20个状态：

第 0个状态:000000000 0的二进制数：000000000
第 1个状态:100000000 1的二进制数：000000001
第 2个状态:110000000 2的二进制数：000000010
第 3个状态:010000000 3的二进制数：000000011
第 4个状态:011000000 4的二进制数：000000100
第 5个状态:111000000 5的二进制数：000000101
第 6个状态:101000000 6的二进制数：000000110
第 7个状态:001000000 7的二进制数：000000111
第 8个状态:001100000 8的二进制数：000001000
第 9个状态:101100000 9的二进制数：000001001
第 10个状态:111100000 10的二进制数：000001010
第 11个状态:011100000 11的二进制数：000001011
第 12个状态:010100000 12的二进制数：000001100
第 13个状态:110100000 13的二进制数：000001101
第 14个状态:100100000 14的二进制数：000001110
第 15个状态:000100000 15的二进制数：000001111
第 16个状态:000110000 16的二进制数：000010000
第 17个状态:100110000 17的二进制数：000010001
第 18个状态:110110000 18的二进制数：000010010
第 19个状态:010110000 19的二进制数：000010011
第 20个状态:011110000 20的二进制数：000010100

    首先想到，二进制数的是个位置右边，从右向左位数逐渐增加，而九连环1号环状左边，从左向右环岛号数逐渐增加。因此我们把状态数字表示倒过来写以符合一般的习惯：

第 0个状态倒置:000000000 0的二进制数：000000000
第 1个状态倒置:000000001 1的二进制数：000000001
第 2个状态倒置:000000011 2的二进制数：000000010
第 3个状态倒置:000000010 3的二进制数：000000011
第 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，就成为000011010，恰好是状态倒置。在具体做时，可以从右向左进行。

    再看状态倒置，我们比较一下同一个数的二进制表示和状态倒置。数字0，1的二进制数和状态倒置是一样的，都是0，1。但数字2，3就不同了，分别是10，11和11，10。右数第二位都是1，但第一位的数字恰好相反。这其实很好理解，因为二进制数是“逢二进一”，而状态倒置由于规则4的限制，当出现如000100000这样的状态倒置时，要得到下一个状态倒置，不能改变个位，只能在更高位加一，成为001100000，然后再从右数第一位开始，同样由于规则4，只能按照上面的过程“倒过来”进行（说倒过来，其实不准确，因为高位不同），因此必然数字都相反，就是0011成了1100，等。

    这样给我们一个方法：在状态倒置里，凡是数字1，把它右边的所有数字都变化一下（0变为1，1变为0），就是相应的二进制数。

    例如，19的状态倒置是000011010，从右向左，第2位是1，把它右边的0改为1，成了000011011；第4位是1，把它右边的011改为100，成了000011100；第5位也是1，再把它右边的1100改为0011，成了000010011，恰好是19的二进制数。当然，0，1互换，换两次等于没换，故实际上是某一个数字的左边有奇数个1时，改变它；有偶数个1时，不动。具体做时，也应从右向左进行。

    这样我们就可以轻易地在状态倒置和二进制数间转换。

    实际上，我们的状态倒置，与编码理论中的 格雷码不谋而合，它的特点是相邻的数字的表示只有一个数字不同，这正好是九连环每次只改变一个环的状态一致。由于这个特点， 格雷码在计算机中有重要的理论与实际意义。关于 格雷码，可以参考有关书籍。 把前面的变换方法，写为口诀，

二G一改零不改，G二奇变偶不变

    就是由二进制数到 格雷码，某一数字的左边是1，它改；是0，不改。由 格雷码到二进制数，某一数字的左边数字和是奇数，变；是偶数，不变。

    例 状态011100101是第一个状态？从它向终点的方向进行5步操作得到什么状态？

    解 状态倒置为101001110，相应二进制数是110001011，十进制数是395，向初始点5步，为400，二进制数110010000，状态倒置是101011000，状态是000110101。

    例 九连环由状态011010010到状态011101010，要进行多少步操作？第一个动作是什么？

    解 初始状态011010010，倒置即 格雷码为010010110，二进制数011100100，十进制数228。终止状态011101010，倒置即 格雷码为010101110，二进制数011001011，十进制数203。因为228大于203，故应向始点进行（即反向进行），一共要进行228－203=25步。下一个状态应为第227个状态，227的二进制数是011100011， 格雷码即状态倒置是010010010， 状态为010010010，与初始状态011010010对比，应下3号环。

简单玩法就是除了使用动作 P,Q，还可以用动作R，因此它是基本玩法的一个简化。前面已经知道，动作R就是两个相继进行的动作上 1 号与 2 号环，记作 PQ，或者动作下 2 号与 1 号环，记作 QP。但先上 1 号再下 2 号，虽也记作PQ，但不能改为动作R；同样，先下 2 号再上 1 号，虽也记作QP，也不能改为动作 R。

简单玩法的前面几步出现的状态列举如下：

初始,  第 0个状态:000000000

动作R, 第 2个状态:110000000

动作P, 第 3个状态:010000000

动作Q, 第 4个状态:011000000

动作P, 第 5个状态:111000000

动作R, 第 7个状态:001000000

动作Q, 第 8个状态:001100000

动作R, 第 10个状态:111100000

动作P, 第 11个状态:011100000

动作Q, 第 12个状态:010100000

动作P, 第 13个状态:110100000

动作R,第 15个状态:000100000

动作Q, 第 16个状态:000110000

动作R,第 18个状态:110110000

动作P, 第 19个状态:010110000

动作Q, 第 20个状态:011110000

动作P, 第 21个状态:111110000

动作R,第 23个状态:001110000

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)=16

g(6)=31,g(7)=64,g(8)=127,g(9)=256

故 9 环全部上去，所需步数按照基本玩法是 341 步，按照简单玩法是 256 步。

基本解法步数与简单解法步数的换算

进一步考虑，到某一个状态（不一定是前面若干个环全部上去），如果完整步数是N，简单步数N0，二者如何换算呢？

实际上，可以看出，由初始开始，每经过完整步数8步，简单步数可省略2步成为6步。余数达到2时再省略1步；达到7时再省略1步。因此简单步数N0是

word/media/image9.gif

其中运算 [x]表示实数x的整数部分,r是N除以8的余数。

这样，我们不但可以知道从任何一个状态到另一个状态用完整解法需要多少步，用简单解法又需要多少步，而且可以知道下一步的动作是什么。（除去两个状态000000000和111111111，任何状态下都可以转变为两个状态，即有两个动作。）再举一个例子。

例 设九连环的初始状态是 110100110 ，要求终止状态是 001001111 ，简单解法与完整解法各需要多少步？第一步是什么动作？

解 （1）初始状态 110100110 ， 格雷码是011001011，转换为二进制数是010001101，相应十进制数是141。终止状态是001001111， 格雷码是111100100，转换为二进制数是101000111，相应十进制数是327。二者差326－141＝186，完整解法需要186步。

（2）由于初始状况141小于终止状况327，第一步应成为142，相应二进制是010001110，转换为 格雷码是011001001，状态是100100110，与原状态比较，第一步应上第2环。

（3）简单解法步数,我们由141，327分别求相应的简单步数，

对于N=141,得到N0=106；对于 N=327,N0=245。二者差139，故简单步数139。

九连环的全部状态

     第 0个状态:000000000 格雷码：000000000 二进制数：000000000
动作P,第 1个状态:100000000 格雷码：000000001 二进制数：000000001
动作Q,第 2个状态:110000000 格雷码：000000011 二进制数：000000010
动作P,第 3个状态:010000000 格雷码：000000010 二进制数：000000011
动作Q,第 4个状态:011000000 格雷码：000000110 二进制数：000000100
动作P,第 5个状态:111000000 格雷码：000000111 二进制数：000000101
动作Q,第 6个状态:101000000 格雷码：000000101 二进制数：000000110
动作P,第 7个状态:001000000 格雷码：000000100 二进制数：000000111
动作Q,第 8个状态:001100000 格雷码：000001100 二进制数：000001000
动作P,第 9个状态:101100000 格雷码：000001101 二进制数：000001001
动作Q,第 10个状态:111100000 格雷码：000001111 二进制数：000001010
动作P,第 11个状态:011100000 格雷码：000001110 二进制数：000001011
动作Q,第 12个状态:010100000 格雷码：000001010 二进制数：000001100
动作P,第 13个状态:110100000 格雷码：000001011 二进制数：000001101
动作Q,第 14个状态:100100000 格雷码：000001001 二进制数：000001110
动作P,第 15个状态:000100000 格雷码：000001000 二进制数：000001111
动作Q,第 16个状态:000110000 格雷码：000011000 二进制数：000010000
动作P,第 17个状态:100110000 格雷码：000011001 二进制数：000010001
动作Q,第 18个状态:110110000 格雷码：000011011 二进制数：000010010
动作P,第 19个状态:010110000 格雷码：000011010 二进制数：000010011
动作Q,第 20个状态:011110000 格雷码：000011110 二进制数：000010100
动作P,第 21个状态:111110000 格雷码：000011111 二进制数：000010101
动作Q,第 22个状态:101110000 格雷码：000011101 二进制数：000010110
动作P,第 23个状态:001110000 格雷码：000011100 二进制数：000010111
动作Q,第 24个状态:001010000 格雷码：000010100 二进制数：000011000
动作P,第 25个状态:101010000 格雷码：000010101 二进制数：000011001
动作Q,第 26个状态:111010000 格雷码：000010111 二进制数：000011010
动作P,第 27个状态:011010000 格雷码：000010110 二进制数：000011011
动作Q,第 28个状态:010010000 格雷码：000010010 二进制数：000011100
动作P,第 29个状态:110010000 格雷码：000010011 二进制数：000011101
动作Q,第 30个状态:100010000 格雷码：000010001 二进制数：000011110
动作P,第 31个状态:000010000 格雷码：000010000 二进制数：000011111
动作Q,第 32个状态:000011000 格雷码：000110000 二进制数：000100000
动作P,第 33个状态:100011000 格雷码：000110001 二进制数：000100001
动作Q,第 34个状态:110011000 格雷码：000110011 二进制数：000100010
动作P,第 35个状态:010011000 格雷码：000110010 二进制数：000100011
动作Q,第 36个状态:011011000 格雷码：000110110 二进制数：000100100
动作P,第 37个状态:111011000 格雷码：000110111 二进制数：000100101
动作Q,第 38个状态:101011000 格雷码：000110101 二进制数：000100110
动作P,第 39个状态:001011000 格雷码：000110100 二进制数：000100111
动作Q,第 40个状态:001111000 格雷码：000111100 二进制数：000101000
动作P,第 41个状态:101111000 格雷码：000111101 二进制数：000101001
动作Q,第 42个状态:111111000 格雷码：000111111 二进制数：000101010
动作P,第 43个状态:011111000 格雷码：000111110 二进制数：000101011
动作Q,第 44个状态:010111000 格雷码：000111010 二进制数：000101100
动作P,第 45个状态:110111000 格雷码：000111011 二进制数：000101101
动作Q,第 46个状态:100111000 格雷码：000111001 二进制数：000101110
动作P,第 47个状态:000111000 格雷码：000111000 二进制数：000101111
动作Q,第 48个状态:000101000 格雷码：000101000 二进制数：000110000
动作P,第 49个状态:100101000 格雷码：000101001 二进制数：000110001
动作Q,第 50个状态:110101000 格雷码：000101011 二进制数：000110010
动作P,第 51个状态:010101000 格雷码：000101010 二进制数：000110011
动作Q,第 52个状态:011101000 格雷码：000101110 二进制数：000110100
动作P,第 53个状态:111101000 格雷码：000101111 二进制数：000110101
动作Q,第 54个状态:101101000 格雷码：000101101 二进制数：000110110
动作P,第 55个状态:001101000 格雷码：000101100 二进制数：000110111
动作Q,第 56个状态:001001000 格雷码：000100100 二进制数：000111000
动作P,第 57个状态:101001000 格雷码：000100101 二进制数：000111001
动作Q,第 58个状态:111001000 格雷码：000100111 二进制数：000111010
动作P,第 59个状态:011001000 格雷码：000100110 二进制数：000111011
动作Q,第 60个状态:010001000 格雷码：000100010 二进制数：000111100
动作P,第 61个状态:110001000 格雷码：000100011 二进制数：000111101
动作Q,第 62个状态:100001000 格雷码：000100001 二进制数：000111110
动作P,第 63个状态:000001000 格雷码：000100000 二进制数：000111111
动作Q,第 64个状态:000001100 格雷码：001100000 二进制数：001000000
动作P,第 65个状态:100001100 格雷码：001100001 二进制数：001000001
动作Q,第 66个状态:110001100 格雷码：001100011 二进制数：001000010
动作P,第 67个状态:010001100 格雷码：001100010 二进制数：001000011
动作Q,第 68个状态:011001100 格雷码：001100110 二进制数：001000100
动作P,第 69个状态:111001100 格雷码：001100111 二进制数：001000101
动作Q,第 70个状态:101001100 格雷码：001100101 二进制数：001000110
动作P,第 71个状态:001001100 格雷码：001100100 二进制数：001000111
动作Q,第 72个状态:001101100 格雷码：001101100 二进制数：001001000
动作P,第 73个状态:101101100 格雷码：001101101 二进制数：001001001
动作Q,第 74个状态:111101100 格雷码：001101111 二进制数：001001010
动作P,第 75个状态:011101100 格雷码：001101110 二进制数：001001011
动作Q,第 76个状态:010101100 格雷码：001101010 二进制数：001001100
动作P,第 77个状态:110101100 格雷码：001101011 二进制数：001001101
动作Q,第 78个状态:100101100 格雷码：001101001 二进制数：001001110
动作P,第 79个状态:000101100 格雷码：001101000 二进制数：001001111
动作Q,第 80个状态:000111100 格雷码：001111000 二进制数：001010000
动作P,第 81个状态:100111100 格雷码：001111001 二进制数：001010001
动作Q,第 82个状态:110111100 格雷码：001111011 二进制数：001010010
动作P,第 83个状态:010111100 格雷码：001111010 二进制数：001010011
动作Q,第 84个状态:011111100 格雷码：001111110 二进制数：001010100
动作P,第 85个状态:111111100 格雷码：001111111 二进制数：001010101
动作Q,第 86个状态:101111100 格雷码：001111101 二进制数：001010110
动作P,第 87个状态:001111100 格雷码：001111100 二进制数：001010111
动作Q,第 88个状态:001011100 格雷码：001110100 二进制数：001011000
动作P,第 89个状态:101011100 格雷码：001110101 二进制数：001011001
动作Q,第 90个状态:111011100 格雷码：001110111 二进制数：001011010
动作P,第 91个状态:011011100 格雷码：001110110 二进制数：001011011
动作Q,第 92个状态:010011100 格雷码：001110010 二进制数：001011100
动作P,第 93个状态:110011100 格雷码：001110011 二进制数：001011101
动作Q,第 94个状态:100011100 格雷码：001110001 二进制数：001011110
动作P,第 95个状态:000011100 格雷码：001110000 二进制数：001011111
动作Q,第 96个状态:000010100 格雷码：001010000 二进制数：001100000
动作P,第 97个状态:100010100 格雷码：001010001 二进制数：001100001
动作Q,第 98个状态:110010100 格雷码：001010011 二进制数：001100010
动作P,第 99个状态:010010100 格雷码：001010010 二进制数：001100011
动作Q,第100个状态:011010100 格雷码：001010110 二进制数：001100100
动作P,第101个状态:111010100 格雷码：001010111 二进制数：001100101
动作Q,第102个状态:101010100 格雷码：001010101 二进制数：001100110
动作P,第103个状态:001010100 格雷码：001010100 二进制数：001100111
动作Q,第104个状态:001110100 格雷码：001011100 二进制数：001101000
动作P,第105个状态:101110100 格雷码：001011101 二进制数：001101001
动作Q,第106个状态:111110100 格雷码：001011111 二进制数：001101010
动作P,第107个状态:011110100 格雷码：001011110 二进制数：001101011
动作Q,第108个状态:010110100 格雷码：001011010 二进制数：001101100
动作P,第109个状态:110110100 格雷码：001011011 二进制数：001101101
动作Q,第110个状态:100110100 格雷码：001011001 二进制数：001101110
动作P,第111个状态:000110100 格雷码：001011000 二进制数：001101111
动作Q,第112个状态:000100100 格雷码：001001000 二进制数：001110000
动作P,第113个状态:100100100 格雷码：001001001 二进制数：001110001
动作Q,第114个状态:110100100 格雷码：001001011 二进制数：001110010
动作P,第115个状态:010100100 格雷码：001001010 二进制数：001110011
动作Q,第116个状态:011100100 格雷码：001001110 二进制数：001110100
动作P,第117个状态:111100100 格雷码：001001111 二进制数：001110101
动作Q,第118个状态:101100100 格雷码：001001101 二进制数：001110110
动作P,第119个状态:001100100 格雷码：001001100 二进制数：001110111
动作Q,第120个状态:001000100 格雷码：001000100 二进制数：001111000
动作P,第121个状态:101000100 格雷码：001000101 二进制数：001111001
动作Q,第122个状态:111000100 格雷码：001000111 二进制数：001111010
动作P,第123个状态:011000100 格雷码：001000110 二进制数：001111011
动作Q,第124个状态:010000100 格雷码：001000010 二进制数：001111100
动作P,第125个状态:110000100 格雷码：001000011 二进制数：001111101
动作Q,第126个状态:100000100 格雷码：001000001 二进制数：001111110
动作P,第127个状态:000000100 格雷码：001000000 二进制数：001111111
动作Q,第128个状态:000000110 格雷码：011000000 二进制数：010000000
动作P,第129个状态:100000110 格雷码：011000001 二进制数：010000001
动作Q,第130个状态:110000110 格雷码：011000011 二进制数：010000010
动作P,第131个状态:010000110 格雷码：011000010 二进制数：010000011
动作Q,第132个状态:011000110 格雷码：011000110 二进制数：010000100
动作P,第133个状态:111000110 格雷码：011000111 二进制数：010000101
动作Q,第134个状态:101000110 格雷码：011000101 二进制数：010000110
动作P,第135个状态:001000110 格雷码：011000100 二进制数：010000111
动作Q,第136个状态:001100110 格雷码：011001100 二进制数：010001000
动作P,第137个状态:101100110 格雷码：011001101 二进制数：010001001
动作Q,第138个状态:111100110 格雷码：011001111 二进制数：010001010
动作P,第139个状态:011100110 格雷码：011001110 二进制数：010001011
动作Q,第140个状态:010100110 格雷码：011001010 二进制数：010001100
动作P,第141个状态:110100110 格雷码：011001011 二进制数：010001101
动作Q,第142个状态:100100110 格雷码：011001001 二进制数：010001110
动作P,第143个状态:000100110 格雷码：011001000 二进制数：010001111
动作Q,第144个状态:000110110 格雷码：011011000 二进制数：010010000
动作P,第145个状态:100110110 格雷码：011011001 二进制数：010010001
动作Q,第146个状态:110110110 格雷码：011011011 二进制数：010010010
动作P,第147个状态:010110110 格雷码：011011010 二进制数：010010011
动作Q,第148个状态:011110110 格雷码：011011110 二进制数：010010100
动作P,第149个状态:111110110 格雷码：011011111 二进制数：010010101
动作Q,第150个状态:101110110 格雷码：011011101 二进制数：010010110
动作P,第151个状态:001110110 格雷码：011011100 二进制数：010010111
动作Q,第152个状态:001010110 格雷码：011010100 二进制数：010011000
动作P,第153个状态:101010110 格雷码：011010101 二进制数：010011001
动作Q,第154个状态:111010110 格雷码：011010111 二进制数：010011010
动作P,第155个状态:011010110 格雷码：011010110 二进制数：010011011
动作Q,第156个状态:010010110 格雷码：011010010 二进制数：010011100
动作P,第157个状态:110010110 格雷码：011010011 二进制数：010011101
动作Q,第158个状态:100010110 格雷码：011010001 二进制数：010011110
动作P,第159个状态:000010110 格雷码：011010000 二进制数：010011111
动作Q,第160个状态:000011110 格雷码：011110000 二进制数：010100000
动作P,第161个状态:100011110 格雷码：011110001 二进制数：010100001
动作Q,第162个状态:110011110 格雷码：011110011 二进制数：010100010
动作P,第163个状态:010011110 格雷码：011110010 二进制数：010100011
动作Q,第164个状态:011011110 格雷码：011110110 二进制数：010100100
动作P,第165个状态:111011110 格雷码：011110111 二进制数：010100101
动作Q,第166个状态:101011110 格雷码：011110101 二进制数：010100110
动作P,第167个状态:001011110 格雷码：011110100 二进制数：010100111
动作Q,第168个状态:001111110 格雷码：011111100 二进制数：010101000
动作P,第169个状态:101111110 格雷码：011111101 二进制数：010101001
动作Q,第170个状态:111111110 格雷码：011111111 二进制数：010101010
动作P,第171个状态:011111110 格雷码：011111110 二进制数：010101011
动作Q,第172个状态:010111110 格雷码：011111010 二进制数：010101100
动作P,第173个状态:110111110 格雷码：011111011 二进制数：010101101
动作Q,第174个状态:100111110 格雷码：011111001 二进制数：010101110
动作P,第175个状态:000111110 格雷码：011111000 二进制数：010101111
动作Q,第176个状态:000101110 格雷码：011101000 二进制数：010110000
动作P,第177个状态:100101110 格雷码：011101001 二进制数：010110001
动作Q,第178个状态:110101110 格雷码：011101011 二进制数：010110010
动作P,第179个状态:010101110 格雷码：011101010 二进制数：010110011
动作Q,第180个状态:011101110 格雷码：011101110 二进制数：010110100
动作P,第181个状态:111101110 格雷码：011101111 二进制数：010110101
动作Q,第182个状态:101101110 格雷码：011101101 二进制数：010110110
动作P,第183个状态:001101110 格雷码：011101100 二进制数：010110111
动作Q,第184个状态:001001110 格雷码：011100100 二进制数：010111000
动作P,第185个状态:101001110 格雷码：011100101 二进制数：010111001
动作Q,第186个状态:111001110 格雷码：011100111 二进制数：010111010
动作P,第187个状态:011001110 格雷码：011100110 二进制数：010111011
动作Q,第188个状态:010001110 格雷码：011100010 二进制数：010111100
动作P,第189个状态:110001110 格雷码：011100011 二进制数：010111101
动作Q,第190个状态:100001110 格雷码：011100001 二进制数：010111110
动作P,第191个状态:000001110 格雷码：011100000 二进制数：010111111
动作Q,第192个状态:000001010 格雷码：010100000 二进制数：011000000
动作P,第193个状态:100001010 格雷码：010100001 二进制数：011000001
动作Q,第194个状态:110001010 格雷码：010100011 二进制数：011000010
动作P,第195个状态:010001010 格雷码：010100010 二进制数：011000011
动作Q,第196个状态:011001010 格雷码：010100110 二进制数：011000100
动作P,第197个状态:111001010 格雷码：010100111 二进制数：011000101
动作Q,第198个状态:101001010 格雷码：010100101 二进制数：011000110
动作P,第199个状态:001001010 格雷码：010100100 二进制数：011000111
动作Q,第200个状态:001101010 格雷码：010101100 二进制数：011001000
动作P,第201个状态:101101010 格雷码：010101101 二进制数：011001001
动作Q,第202个状态:111101010 格雷码：010101111 二进制数：011001010
动作P,第203个状态:011101010 格雷码：010101110 二进制数：011001011
动作Q,第204个状态:010101010 格雷码：010101010 二进制数：011001100
动作P,第205个状态:110101010 格雷码：010101011 二进制数：011001101
动作Q,第206个状态:100101010 格雷码：010101001 二进制数：011001110
动作P,第207个状态:000101010 格雷码：010101000 二进制数：011001111
动作Q,第208个状态:000111010 格雷码：010111000 二进制数：011010000
动作P,第209个状态:100111010 格雷码：010111001 二进制数：011010001
动作Q,第210个状态:110111010 格雷码：010111011 二进制数：011010010
动作P,第211个状态:010111010 格雷码：010111010 二进制数：011010011
动作Q,第212个状态:011111010 格雷码：010111110 二进制数：011010100
动作P,第213个状态:111111010 格雷码：010111111 二进制数：011010101
动作Q,第214个状态:101111010 格雷码：010111101 二进制数：011010110
动作P,第215个状态:001111010 格雷码：010111100 二进制数：011010111
动作Q,第216个状态:001011010 格雷码：010110100 二进制数：011011000
动作P,第217个状态:101011010 格雷码：010110101 二进制数：011011001
动作Q,第218个状态:111011010 格雷码：010110111 二进制数：011011010
动作P,第219个状态:011011010 格雷码：010110110 二进制数：011011011
动作Q,第220个状态:010011010 格雷码：010110010 二进制数：011011100
动作P,第221个状态:110011010 格雷码：010110011 二进制数：011011101
动作Q,第222个状态:100011010 格雷码：010110001 二进制数：011011110
动作P,第223个状态:000011010 格雷码：010110000 二进制数：011011111
动作Q,第224个状态:000010010 格雷码：010010000 二进制数：011100000
动作P,第225个状态:100010010 格雷码：010010001 二进制数：011100001
动作Q,第226个状态:110010010 格雷码：010010011 二进制数：011100010
动作P,第227个状态:010010010 格雷码：010010010 二进制数：011100011
动作Q,第228个状态:011010010 格雷码：010010110 二进制数：011100100
动作P,第229个状态:111010010 格雷码：010010111 二进制数：011100101
动作Q,第230个状态:101010010 格雷码：010010101 二进制数：011100110
动作P,第231个状态:001010010 格雷码：010010100 二进制数：011100111
动作Q,第232个状态:001110010 格雷码：010011100 二进制数：011101000
动作P,第233个状态:101110010 格雷码：010011101 二进制数：011101001
动作Q,第234个状态:111110010 格雷码：010011111 二进制数：011101010
动作P,第235个状态:011110010 格雷码：010011110 二进制数：011101011
动作Q,第236个状态:010110010 格雷码：010011010 二进制数：011101100
动作P,第237个状态:110110010 格雷码：010011011 二进制数：011101101
动作Q,第238个状态:100110010 格雷码：010011001 二进制数：011101110
动作P,第239个状态:000110010 格雷码：010011000 二进制数：011101111
动作Q,第240个状态:000100010 格雷码：010001000 二进制数：011110000
动作P,第241个状态:100100010 格雷码：010001001 二进制数：011110001
动作Q,第242个状态:110100010 格雷码：010001011 二进制数：011110010
动作P,第243个状态:010100010 格雷码：010001010 二进制数：011110011
动作Q,第244个状态:011100010 格雷码：010001110 二进制数：011110100
动作P,第245个状态:111100010 格雷码：010001111 二进制数：011110101
动作Q,第246个状态:101100010 格雷码：010001101 二进制数：011110110
动作P,第247个状态:001100010 格雷码：010001100 二进制数：011110111
动作Q,第248个状态:001000010 格雷码：010000100 二进制数：011111000
动作P,第249个状态:101000010 格雷码：010000101 二进制数：011111001
动作Q,第250个状态:111000010 格雷码：010000111 二进制数：011111010
动作P,第251个状态:011000010 格雷码：010000110 二进制数：011111011
动作Q,第252个状态:010000010 格雷码：010000010 二进制数：011111100
动作P,第253个状态:110000010 格雷码：010000011 二进制数：011111101
动作Q,第254个状态:100000010 格雷码：010000001 二进制数：011111110
动作P,第255个状态:000000010 格雷码：010000000 二进制数：011111111
动作Q,第256个状态:000000011 格雷码：110000000 二进制数：100000000
动作P,第257个状态:100000011 格雷码：110000001 二进制数：100000001
动作Q,第258个状态:110000011 格雷码：110000011 二进制数：100000010
动作P,第259个状态:010000011 格雷码：110000010 二进制数：100000011
动作Q,第260个状态:011000011 格雷码：110000110 二进制数：100000100
动作P,第261个状态:111000011 格雷码：110000111 二进制数：100000101
动作Q,第262个状态:101000011 格雷码：110000101 二进制数：100000110
动作P,第263个状态:001000011 格雷码：110000100 二进制数：100000111
动作Q,第264个状态:001100011 格雷码：110001100 二进制数：100001000
动作P,第265个状态:101100011 格雷码：110001101 二进制数：100001001
动作Q,第266个状态:111100011 格雷码：110001111 二进制数：100001010
动作P,第267个状态:011100011 格雷码：110001110 二进制数：100001011
动作Q,第268个状态:010100011 格雷码：110001010 二进制数：100001100
动作P,第269个状态:110100011 格雷码：110001011 二进制数：100001101
动作Q,第270个状态:100100011 格雷码：110001001 二进制数：100001110
动作P,第271个状态:000100011 格雷码：110001000 二进制数：100001111
动作Q,第272个状态:000110011 格雷码：110011000 二进制数：100010000
动作P,第273个状态:100110011 格雷码：110011001 二进制数：100010001
动作Q,第274个状态:110110011 格雷码：110011011 二进制数：100010010
动作P,第275个状态:010110011 格雷码：110011010 二进制数：100010011
动作Q,第276个状态:011110011 格雷码：110011110 二进制数：100010100
动作P,第277个状态:111110011 格雷码：110011111 二进制数：100010101
动作Q,第278个状态:101110011 格雷码：110011101 二进制数：100010110
动作P,第279个状态:001110011 格雷码：110011100 二进制数：100010111
动作Q,第280个状态:001010011 格雷码：110010100 二进制数：100011000
动作P,第281个状态:101010011 格雷码：110010101 二进制数：100011001
动作Q,第282个状态:111010011 格雷码：110010111 二进制数：100011010
动作P,第283个状态:011010011 格雷码：110010110 二进制数：100011011
动作Q,第284个状态:010010011 格雷码：110010010 二进制数：100011100
动作P,第285个状态:110010011 格雷码：110010011 二进制数：100011101
动作Q,第286个状态:100010011 格雷码：110010001 二进制数：100011110
动作P,第287个状态:000010011 格雷码：110010000 二进制数：100011111
动作Q,第288个状态:000011011 格雷码：110110000 二进制数：100100000
动作P,第289个状态:100011011 格雷码：110110001 二进制数：100100001
动作Q,第290个状态:110011011 格雷码：110110011 二进制数：100100010
动作P,第291个状态:010011011 格雷码：110110010 二进制数：100100011
动作Q,第292个状态:011011011 格雷码：110110110 二进制数：100100100
动作P,第293个状态:111011011 格雷码：110110111 二进制数：100100101
动作Q,第294个状态:101011011 格雷码：110110101 二进制数：100100110
动作P,第295个状态:001011011 格雷码：110110100 二进制数：100100111
动作Q,第296个状态:001111011 格雷码：110111100 二进制数：100101000
动作P,第297个状态:101111011 格雷码：110111101 二进制数：100101001
动作Q,第298个状态:111111011 格雷码：110111111 二进制数：100101010
动作P,第299个状态:011111011 格雷码：110111110 二进制数：100101011
动作Q,第300个状态:010111011 格雷码：110111010 二进制数：100101100
动作P,第301个状态:110111011 格雷码：110111011 二进制数：100101101
动作Q,第302个状态:100111011 格雷码：110111001 二进制数：100101110
动作P,第303个状态:000111011 格雷码：110111000 二进制数：100101111
动作Q,第304个状态:000101011 格雷码：110101000 二进制数：100110000
动作P,第305个状态:100101011 格雷码：110101001 二进制数：100110001
动作Q,第306个状态:110101011 格雷码：110101011 二进制数：100110010
动作P,第307个状态:010101011 格雷码：110101010 二进制数：100110011
动作Q,第308个状态:011101011 格雷码：110101110 二进制数：100110100
动作P,第309个状态:111101011 格雷码：110101111 二进制数：100110101
动作Q,第310个状态:101101011 格雷码：110101101 二进制数：100110110
动作P,第311个状态:001101011 格雷码：110101100 二进制数：100110111
动作Q,第312个状态:001001011 格雷码：110100100 二进制数：100111000
动作P,第313个状态:101001011 格雷码：110100101 二进制数：100111001
动作Q,第314个状态:111001011 格雷码：110100111 二进制数：100111010
动作P,第315个状态:011001011 格雷码：110100110 二进制数：100111011
动作Q,第316个状态:010001011 格雷码：110100010 二进制数：100111100
动作P,第317个状态:110001011 格雷码：110100011 二进制数：100111101
动作Q,第318个状态:100001011 格雷码：110100001 二进制数：100111110
动作P,第319个状态:000001011 格雷码：110100000 二进制数：100111111
动作Q,第320个状态:000001111 格雷码：111100000 二进制数：101000000
动作P,第321个状态:100001111 格雷码：111100001 二进制数：101000001
动作Q,第322个状态:110001111 格雷码：111100011 二进制数：101000010
动作P,第323个状态:010001111 格雷码：111100010 二进制数：101000011
动作Q,第324个状态:011001111 格雷码：111100110 二进制数：101000100
动作P,第325个状态:111001111 格雷码：111100111 二进制数：101000101
动作Q,第326个状态:101001111 格雷码：111100101 二进制数：101000110
动作P,第327个状态:001001111 格雷码：111100100 二进制数：101000111
动作Q,第328个状态:001101111 格雷码：111101100 二进制数：101001000
动作P,第329个状态:101101111 格雷码：111101101 二进制数：101001001
动作Q,第330个状态:111101111 格雷码：111101111 二进制数：101001010
动作P,第331个状态:011101111 格雷码：111101110 二进制数：101001011
动作Q,第332个状态:010101111 格雷码：111101010 二进制数：101001100
动作P,第333个状态:110101111 格雷码：111101011 二进制数：101001101
动作Q,第334个状态:100101111 格雷码：111101001 二进制数：101001110
动作P,第335个状态:000101111 格雷码：111101000 二进制数：101001111
动作Q,第336个状态:000111111 格雷码：111111000 二进制数：101010000
动作P,第337个状态:100111111 格雷码：111111001 二进制数：101010001
动作Q,第338个状态:110111111 格雷码：111111011 二进制数：101010010
动作P,第339个状态:010111111 格雷码：111111010 二进制数：101010011
动作Q,第340个状态:011111111 格雷码：111111110 二进制数：101010100
动作P,第341个状态:111111111 格雷码：111111111 二进制数：101010101
动作Q,第342个状态:101111111 格雷码：111111101 二进制数：101010110
动作P,第343个状态:001111111 格雷码：111111100 二进制数：101010111
动作Q,第344个状态:001011111 格雷码：111110100 二进制数：101011000
动作P,第345个状态:101011111 格雷码：111110101 二进制数：101011001
动作Q,第346个状态:111011111 格雷码：111110111 二进制数：101011010
动作P,第347个状态:011011111 格雷码：111110110 二进制数：101011011
动作Q,第348个状态:010011111 格雷码：111110010 二进制数：101011100
动作P,第349个状态:110011111 格雷码：111110011 二进制数：101011101
动作Q,第350个状态:100011111 格雷码：111110001 二进制数：101011110
动作P,第351个状态:000011111 格雷码：111110000 二进制数：101011111
动作Q,第352个状态:000010111 格雷码：111010000 二进制数：101100000
动作P,第353个状态:100010111 格雷码：111010001 二进制数：101100001
动作Q,第354个状态:110010111 格雷码：111010011 二进制数：101100010
动作P,第355个状态:010010111 格雷码：111010010 二进制数：101100011
动作Q,第356个状态:011010111 格雷码：111010110 二进制数：101100100
动作P,第357个状态:111010111 格雷码：111010111 二进制数：101100101
动作Q,第358个状态:101010111 格雷码：111010101 二进制数：101100110
动作P,第359个状态:001010111 格雷码：111010100 二进制数：101100111
动作Q,第360个状态:001110111 格雷码：111011100 二进制数：101101000
动作P,第361个状态:101110111 格雷码：111011101 二进制数：101101001
动作Q,第362个状态:111110111 格雷码：111011111 二进制数：101101010
动作P,第363个状态:011110111 格雷码：111011110 二进制数：101101011
动作Q,第364个状态:010110111 格雷码：111011010 二进制数：101101100
动作P,第365个状态:110110111 格雷码：111011011 二进制数：101101101
动作Q,第366个状态:100110111 格雷码：111011001 二进制数：101101110
动作P,第367个状态:000110111 格雷码：111011000 二进制数：101101111
动作Q,第368个状态:000100111 格雷码：111001000 二进制数：101110000
动作P,第369个状态:100100111 格雷码：111001001 二进制数：101110001
动作Q,第370个状态:110100111 格雷码：111001011 二进制数：101110010
动作P,第371个状态:010100111 格雷码：111001010 二进制数：101110011
动作Q,第372个状态:011100111 格雷码：111001110 二进制数：101110100
动作P,第373个状态:111100111 格雷码：111001111 二进制数：101110101
动作Q,第374个状态:101100111 格雷码：111001101 二进制数：101110110
动作P,第375个状态:001100111 格雷码：111001100 二进制数：101110111
动作Q,第376个状态:001000111 格雷码：111000100 二进制数：101111000
动作P,第377个状态:101000111 格雷码：111000101 二进制数：101111001
动作Q,第378个状态:111000111 格雷码：111000111 二进制数：101111010
动作P,第379个状态:011000111 格雷码：111000110 二进制数：101111011
动作Q,第380个状态:010000111 格雷码：111000010 二进制数：101111100
动作P,第381个状态:110000111 格雷码：111000011 二进制数：101111101
动作Q,第382个状态:100000111 格雷码：111000001 二进制数：101111110
动作P,第383个状态:000000111 格雷码：111000000 二进制数：101111111
动作Q,第384个状态:000000101 格雷码：101000000 二进制数：110000000
动作P,第385个状态:100000101 格雷码：101000001 二进制数：110000001
动作Q,第386个状态:110000101 格雷码：101000011 二进制数：110000010
动作P,第387个状态:010000101 格雷码：101000010 二进制数：110000011
动作Q,第388个状态:011000101 格雷码：101000110 二进制数：110000100
动作P,第389个状态:111000101 格雷码：101000111 二进制数：110000101
动作Q,第390个状态:101000101 格雷码：101000101 二进制数：110000110
动作P,第391个状态:001000101 格雷码：101000100 二进制数：110000111
动作Q,第392个状态:001100101 格雷码：101001100 二进制数：110001000
动作P,第393个状态:101100101 格雷码：101001101 二进制数：110001001
动作Q,第394个状态:111100101 格雷码：101001111 二进制数：110001010
动作P,第395个状态:011100101 格雷码：101001110 二进制数：110001011
动作Q,第396个状态:010100101 格雷码：101001010 二进制数：110001100
动作P,第397个状态:110100101 格雷码：101001011 二进制数：110001101
动作Q,第398个状态:100100101 格雷码：101001001 二进制数：110001110
动作P,第399个状态:000100101 格雷码：101001000 二进制数：110001111
动作Q,第400个状态:000110101 格雷码：101011000 二进制数：110010000
动作P,第401个状态:100110101 格雷码：101011001 二进制数：110010001
动作Q,第402个状态:110110101 格雷码：101011011 二进制数：110010010
动作P,第403个状态:010110101 格雷码：101011010 二进制数：110010011
动作Q,第404个状态:011110101 格雷码：101011110 二进制数：110010100
动作P,第405个状态:111110101 格雷码：101011111 二进制数：110010101
动作Q,第406个状态:101110101 格雷码：101011101 二进制数：110010110
动作P,第407个状态:001110101 格雷码：101011100 二进制数：110010111
动作Q,第408个状态:001010101 格雷码：101010100 二进制数：110011000
动作P,第409个状态:101010101 格雷码：101010101 二进制数：110011001
动作Q,第410个状态:111010101 格雷码：101010111 二进制数：110011010
动作P,第411个状态:011010101 格雷码：101010110 二进制数：110011011
动作Q,第412个状态:010010101 格雷码：101010010 二进制数：110011100
动作P,第413个状态:110010101 格雷码：101010011 二进制数：110011101
动作Q,第414个状态:100010101 格雷码：101010001 二进制数：110011110
动作P,第415个状态:000010101 格雷码：101010000 二进制数：110011111
动作Q,第416个状态:000011101 格雷码：101110000 二进制数：110100000
动作P,第417个状态:100011101 格雷码：101110001 二进制数：110100001
动作Q,第418个状态:110011101 格雷码：101110011 二进制数：110100010
动作P,第419个状态:010011101 格雷码：101110010 二进制数：110100011
动作Q,第420个状态:011011101 格雷码：101110110 二进制数：110100100
动作P,第421个状态:111011101 格雷码：101110111 二进制数：110100101
动作Q,第422个状态:101011101 格雷码：101110101 二进制数：110100110
动作P,第423个状态:001011101 格雷码：101110100 二进制数：110100111
动作Q,第424个状态:001111101 格雷码：101111100 二进制数：110101000
动作P,第425个状态:101111101 格雷码：101111101 二进制数：110101001
动作Q,第426个状态:111111101 格雷码：101111111 二进制数：110101010
动作P,第427个状态:011111101 格雷码：101111110 二进制数：110101011
动作Q,第428个状态:010111101 格雷码：101111010 二进制数：110101100
动作P,第429个状态:110111101 格雷码：101111011 二进制数：110101101
动作Q,第430个状态:100111101 格雷码：101111001 二进制数：110101110
动作P,第431个状态:000111101 格雷码：101111000 二进制数：110101111
动作Q,第432个状态:000101101 格雷码：101101000 二进制数：110110000
动作P,第433个状态:100101101 格雷码：101101001 二进制数：110110001
动作Q,第434个状态:110101101 格雷码：101101011 二进制数：110110010
动作P,第435个状态:010101101 格雷码：101101010 二进制数：110110011
动作Q,第436个状态:011101101 格雷码：101101110 二进制数：110110100
动作P,第437个状态:111101101 格雷码：101101111 二进制数：110110101
动作Q,第438个状态:101101101 格雷码：101101101 二进制数：110110110
动作P,第439个状态:001101101 格雷码：101101100 二进制数：110110111
动作Q,第440个状态:001001101 格雷码：101100100 二进制数：110111000
动作P,第441个状态:101001101 格雷码：101100101 二进制数：110111001
动作Q,第442个状态:111001101 格雷码：101100111 二进制数：110111010
动作P,第443个状态:011001101 格雷码：101100110 二进制数：110111011
动作Q,第444个状态:010001101 格雷码：101100010 二进制数：110111100
动作P,第445个状态:110001101 格雷码：101100011 二进制数：110111101
动作Q,第446个状态:100001101 格雷码：101100001 二进制数：110111110
动作P,第447个状态:000001101 格雷码：101100000 二进制数：110111111
动作Q,第448个状态:000001001 格雷码：100100000 二进制数：111000000
动作P,第449个状态:100001001 格雷码：100100001 二进制数：111000001
动作Q,第450个状态:110001001 格雷码：100100011 二进制数：111000010
动作P,第451个状态:010001001 格雷码：100100010 二进制数：111000011
动作Q,第452个状态:011001001 格雷码：100100110 二进制数：111000100
动作P,第453个状态:111001001 格雷码：100100111 二进制数：111000101
动作Q,第454个状态:101001001 格雷码：100100101 二进制数：111000110
动作P,第455个状态:001001001 格雷码：100100100 二进制数：111000111
动作Q,第456个状态:001101001 格雷码：100101100 二进制数：111001000
动作P,第457个状态:101101001 格雷码：100101101 二进制数：111001001
动作Q,第458个状态:111101001 格雷码：100101111 二进制数：111001010
动作P,第459个状态:011101001 格雷码：100101110 二进制数：111001011
动作Q,第460个状态:010101001 格雷码：100101010 二进制数：111001100
动作P,第461个状态:110101001 格雷码：100101011 二进制数：111001101
动作Q,第462个状态:100101001 格雷码：100101001 二进制数：111001110
动作P,第463个状态:000101001 格雷码：100101000 二进制数：111001111
动作Q,第464个状态:000111001 格雷码：100111000 二进制数：111010000
动作P,第465个状态:100111001 格雷码：100111001 二进制数：111010001
动作Q,第466个状态:110111001 格雷码：100111011 二进制数：111010010
动作P,第467个状态:010111001 格雷码：100111010 二进制数：111010011
动作Q,第468个状态:011111001 格雷码：100111110 二进制数：111010100
动作P,第469个状态:111111001 格雷码：100111111 二进制数：111010101
动作Q,第470个状态:101111001 格雷码：100111101 二进制数：111010110
动作P,第471个状态:001111001 格雷码：100111100 二进制数：111010111
动作Q,第472个状态:001011001 格雷码：100110100 二进制数：111011000
动作P,第473个状态:101011001 格雷码：100110101 二进制数：111011001
动作Q,第474个状态:111011001 格雷码：100110111 二进制数：111011010
动作P,第475个状态:011011001 格雷码：100110110 二进制数：111011011
动作Q,第476个状态:010011001 格雷码：100110010 二进制数：111011100
动作P,第477个状态:110011001 格雷码：100110011 二进制数：111011101
动作Q,第478个状态:100011001 格雷码：100110001 二进制数：111011110
动作P,第479个状态:000011001 格雷码：100110000 二进制数：111011111
动作Q,第480个状态:000010001 格雷码：100010000 二进制数：111100000
动作P,第481个状态:100010001 格雷码：100010001 二进制数：111100001
动作Q,第482个状态:110010001 格雷码：100010011 二进制数：111100010
动作P,第483个状态:010010001 格雷码：100010010 二进制数：111100011
动作Q,第484个状态:011010001 格雷码：100010110 二进制数：111100100
动作P,第485个状态:111010001 格雷码：100010111 二进制数：111100101
动作Q,第486个状态:101010001 格雷码：100010101 二进制数：111100110
动作P,第487个状态:001010001 格雷码：100010100 二进制数：111100111
动作Q,第488个状态:001110001 格雷码：100011100 二进制数：111101000
动作P,第489个状态:101110001 格雷码：100011101 二进制数：111101001
动作Q,第490个状态:111110001 格雷码：100011111 二进制数：111101010
动作P,第491个状态:011110001 格雷码：100011110 二进制数：111101011
动作Q,第492个状态:010110001 格雷码：100011010 二进制数：111101100
动作P,第493个状态:110110001 格雷码：100011011 二进制数：111101101
动作Q,第494个状态:100110001 格雷码：100011001 二进制数：111101110
动作P,第495个状态:000110001 格雷码：100011000 二进制数：111101111
动作Q,第496个状态:000100001 格雷码：100001000 二进制数：111110000
动作P,第497个状态:100100001 格雷码：100001001 二进制数：111110001
动作Q,第498个状态:110100001 格雷码：100001011 二进制数：111110010
动作P,第499个状态:010100001 格雷码：100001010 二进制数：111110011
动作Q,第500个状态:011100001 格雷码：100001110 二进制数：111110100
动作P,第501个状态:111100001 格雷码：100001111 二进制数：111110101
动作Q,第502个状态:101100001 格雷码：100001101 二进制数：111110110
动作P,第503个状态:001100001 格雷码：100001100 二进制数：111110111
动作Q,第504个状态:001000001 格雷码：100000100 二进制数：111111000
动作P,第505个状态:101000001 格雷码：100000101 二进制数：111111001
动作Q,第506个状态:111000001 格雷码：100000111 二进制数：111111010
动作P,第507个状态:011000001 格雷码：100000110 二进制数：111111011
动作Q,第508个状态:010000001 格雷码：100000010 二进制数：111111100
动作P,第509个状态:110000001 格雷码：100000011 二进制数：111111101
动作Q,第510个状态:100000001 格雷码：100000001 二进制数：111111110
动作P,第511个状态:000000001 格雷码：100000000 二进制数：111111111