怎样解九连环V5

九连环是我国古代民间的一种游戏，曾风靡明清二朝，也是世界公认的最奥妙的玩具之一，在国外被称为“ChineseRing”。它的历史已无从考证，但16世纪时，大数学家卡尔达诺曾提到九连环。数学家华利斯对它也作过精辟的分析。

九连环是这样的：有9个圆环，每一个环上都连着一根直杆，每一根直杆都从后一环内穿过，再穿过一块板的9个小孔。每根杆的下端都打上了结，因而只能在小孔中上下移动，而不能从板上拔出来。另外还有一个双股的钗。玩这个游戏的目的是要把9个环一个扣一个地都套到钗上，或者把套在钗上的9个环（如图）都脱下来。不论套上还是脱下，要经过几百道手续，还得遵循一定的规律，即要有一套算法。

先介绍一下基本动作。先把第一环自下而上穿过钗心（如图A）套在钗头上（如图B）。其他的环因为有别的环扣住，不能用这一方法。但如果前面有一个邻接的环已套在钗上，而所有其他前面的环都不在钗上，那么只要把这一个环暂时移到钗头前面，让出钗头（如图C），后一环就可以套上去，再把前一环复位（如图D）。至于脱环，只要把上面的动作颠倒过来就行了。

现在可以看出，如果只要套上第一环，只须1步。如果要套上第一、二两环，可先套第一环，再套第二环，需要2步。当要套三个环时，套好第一、二环后，必须先脱下第一环，再套第三环，最后再套第一环，一共是5步。当环数更多时，手续更加复杂。古代有这样一个口诀：“一二一三一二一，钗头双连下第二，独环在钗上后环。”这上环的最后5步是一二一三一，所以脱环最先5步是一三一二一。

换句话说，移动的手续是，每8步可作为一个单元，其中的前7步一定是“一二一三一二一”，至于到底应“上”还是应“下”，这可依自然趋势而定。即原来不在钗上的应“上”，原来在钗上的应“下”。至于第8步，则要看那时钗头的情况：在两环相连时，一定要脱下后一环；在钗头只有单独的一环时，一定要套上后一环。以上就是口诀的意思，“算法”的全部奥妙就都在这里了。根据这三句口诀，解开或套上9个环，虽然有341步之多，也不费吹灰之力了。

1975年，国外出版的一本专门讲数列的书，里面收罗了这样一个数列：

1，2，5，10，21，42，85，170，341，…

这个数列既非等差数列，又非等比数列，似乎也没有什么规律。它到底是什么数列呢？原来这是一个“九连环”数列，它的第n项就是解开n个环所需的步数。

那么数列里的各个数有没有规律呢？有。如果我们用u_n代表上述数列的第n项，那么，就可以得到以下的公式：

当n是偶数时，u_n=2u_n-1

当n是奇数时，u_n=2u_n-1+1。

通过上面的式子，我们可以由u₁求得u₂，再推出u₃……这种方法叫“递归”。

还有一个更直接的计算公式，即：

关键词：九连环 九连环数列 递归