九连环

递归算法

九连环是以金属丝制成的9个圆环

将圆环套装在横板或各式框架上，并贯以环柄

它的主体是九个环，一个套一个

并同时穿在剑形环柄上

环柄两端分别是柄把和柄钗

西汉时的卓文君就很喜欢拆解九连环

她写给夫君司马相如的信中如是说道：

“一别之后，二地相悬，

只说是三四月，又谁知五六年。

七弦琴无心弹，八行书无可传，

九连环从中折断，十里长亭望眼欲穿。

百思想，千系念，万般无奈把君怨。”

《红楼梦》中也有林黛玉拆解九连环的描写

周瑞家的把最后两支宫花送给黛玉时，原文有这样的文字：“谁知此时黛玉不在自己房中，却在宝玉房中大家解九连环顽呢。”

九连环的每个环是互相牵制的

拆解规则有两条：

第１环可以在任何时候放上或取下；拆解第Ｎ环(N1)，必须将第N-1环放在柄上，

而第1到N-2环全部取下；

实际这个过程就是数学上的递归算法

假设环的数量为n，解下每个环的步数为an

解开n连环所需总步数为Sn

根据拆解规则可以推出：

如若要卸下第n个环，就需要先卸下前n-2个环

其总步数就为Sn-2

这时再需要一步就可以把第n个环解下

而为了解下第n-1个环

还需把前面的n-2个环套上

装上前n-2个环需要Sn-2步

所以卸下第n个环需要an=2Sn-2+1步

1

2

3

4

5

6

7

8

9

an

1

1

3

5

11

21

43

85

sn

1

2

5

10

21

42

85

因此

解开九连环所需要的步数就是一道数列题：

已知S1=1，S2=2，an=2Sn-2+1,求Sn（n≥3）

当n=9时，S9=，即最终需要步