九连环的递归算法（C和C++）

　　一、九连环简介

L|/K r]v?;w0　　九连环游戏是中国人自己发明的，它的历史非常悠久，据说是起源于战国时期。九连环主要是由一个框架和九个圆环组成：每个圆环上连有一个直杆，而这个直杆则在后面一个圆环内穿过，九个直杆的另一端用一块木板或圆环相对固定。

　　二、九连环的规律51Testing软件测试网vON*H(c#v

/Oc0L/R2Z~0　　通过玩九连环你就会发现存在这样一个规律：51Testing软件测试网Iv G(P3wxTM

　　（1）第 1环可以自由上下51Testing软件测试网,Aer]j

　　（2）而上/下第 n环时（n>1），则必须满足：51Testing软件测试网4ot|5z)?Er3f

　　　　（a）第 n-1个环在架上51Testing软件测试网/Cx1Hw;I:su!Bn@

g!A]^szt0　　　　（b）前 n-2个环全部在架下

　　三、拆解/安装的过程

　　正确的拆解是先以第 9环为目标，先拆下它，简化为拆一个 8连环。接着再也第 8 环为目标，拆下它，简化为拆一个 7连环。以此类推，直至全部拆解。

　　其实安装和拆解是一个道理，因为他们均是使用上面说的规律来完成的。51Testing软件测试网Th)cwem"y

　　正确是安装也是先以第 9环为目标，先装上它，简化为装一个 8连环。接着再也第 8 环为目标，装上它，简化为装一个 7连环。以此类推，直至全部安装。

　　当然，现在这么说是便于理解，当你深刻的理解了上面所说的规律后，就会发现，安装上第 9环后，问题可以被简化为装一个 7连环，而当装上第 7 环后，问题就被简化为装一个 5连环了，呵呵，就是这样的，不知道你现在是否明白我的意思……

　　四、一个猜想

*x A/C#g;~p!u0　 　仔细观察九连环的结构、思考九连环的规律及拆解/安装的过程，你是不是有一种感觉：九连环跟递归一定有联系。你看，递归的基本思想是把一个大的问题分解 为一个规模较小的问题，从这些较小问题的解，构造出大问题的解，而这些规模较小的问题，用同样的方法分解成更小的问题，从更小问题的解，构造出较小的问 题，一层层下去，一般最后总是可以分解到可以直接求解的小问题。嘿嘿，九连环的拆解/安装多么的符合这个规律啊……^_^

　　五、算法实现51Testing软件测试网]CI:}8p F

(BN4zW+i,Ze4VL0　　以下是算法实现，程序写的很简洁，省略了很多功能的实现，比如计数等，如果你觉得有必要的话，可以自行添加上去，我相信很容易，并不要很多的改动。

　　The C Code Here：51Testing软件测试网A u'f,c2CmM8Au#G

The C++ Code Here:

+qy!r.T4\v0/****************************/
SiC$f?w M0           任意 N连环均适用51Testing软件测试网+u7PTNE*{

!J[+byYN0           日期：2012/8/1251Testing软件测试网b(V0gL0g^

           程序设计：YCY
K!D |-p[;al`(r0           电邮：ycy360@163.com

h+qpp
DU8r%iT0/****************************/51Testing软件测试网0h x
R*A@ a$L

+@(_3y&Inl { Vf0#include<iostream>51Testing软件测试网7J%Q1c-H8z

Hf0RB/S4k0using namespace std;51Testing软件测试网t)M{+n+E.op J5{

 51Testing软件测试网 H3_2U {8D R[

class Ring

{

public:

E3e7AR|7m8u,|0       Ring(int n):nRingNum(n){}51Testing软件测试网+X x0} RNKW*P

       void UpRing(int n);51Testing软件测试网&a:e,z'Vk;D

\U4`a1V?0       void DownRing(int n);

Na6?Aq*z`[R0       void startDownRing();

(Q
G+^7E4F2]0~0       void startUpRing();51Testing软件测试网~/B:b,y{)LB$H6O3wK

+kI2DYi
VA0       void totalCnt();51Testing软件测试网G6\K:\+hwx

       void setUpZero();

zUjho8pTa P0private:51Testing软件测试网,b9Q s3{8g QH

       int nRingNum;51Testing软件测试网q+AQT;_1eF|)X

       static int s_nCnt;

};

#@nXSK"~a\ f0 

+i1KYBA@g(v0int Ring::s_nCnt = 0;    //计数51Testing软件测试网Z2p.u0b@ B$V

i-F!~%[n| k0void Ring::UpRing(int n)  //Upring是DownRing的逆过程.51Testing软件测试网]y5z.A;qX&L'}

{

,cxQ8L |1A8S)z*m0       ++s_nCnt;

       if(n>1) UpRing(n-1);

1Sl,[%yM^ ir,[8Z0       if(n>2) DownRing(n-2);51Testing软件测试网7qt|5`6K:N'FtW

       cout << "上第" << n << "环" << endl;51Testing软件测试网9D#s$X.MJ_;g i4Q.K

       if(n>2) UpRing(n-2);51Testing软件测试网wfZ7H$o@Jt3x

'|\X ^"I,@!e0}

;R:T(Y@5QC7?0 

void Ring::DownRing(int n)51Testing软件测试网]6]4RC*_k M&{

{51Testing软件测试网[iIm5V*WQ

{,td1} E0M0       ++s_nCnt;51Testing软件测试网Tc%X
KK&cHr(Vt:E

       if(n>2) DownRing(n-2);51Testing软件测试网_(KoI nI{0u

       cout <<"下第" << n << "环" << endl;51Testing软件测试网?G#EhG

       if(n>2) UpRing(n-2);

       if(n>1) DownRing(n-1);

F\2Z)NYgsv?:z0}

+Vk v(@W
X @0 

u[O ?J0void Ring::startDownRing()51Testing软件测试网N#z1SYaq

C{1gNrc(wCf0{51Testing软件测试网`UV J9a

       cout << "拆解" << nRingNum << "连环操作!" << endl;

       DownRing(nRingNum);

W9C,_{r{UM0       cout << "拆解完毕" << endl;

}

x2xHx4b'}w9[0 

void Ring::startUpRing()51Testing软件测试网'G.e6q^ZK.G"h#i

{

!A^vE;q,c*dj0       cout << "安装" << nRingNum << "连环操作!" << endl;51Testing软件测试网V ZgFB0sd

       UpRing(nRingNum);

"Q DQd$Yw0       cout << "安装完毕" << endl;

}

5up:Lq!i1Zt,U c/m0 

K/o@o3s*_0void Ring::totalCnt()

{51Testing软件测试网?8eE!T%cZZ

       cout << "共累计上、下环" << s_nCnt << "次!" << endl << endl;

H1Ix(L/Y0}

D)PR|!l&}0 51Testing软件测试网_#C&?Z'm&_6jBD8\

vR'b [(_*iY0void Ring::setUpZero()

#GLrb5_OD'F.N^!`0{51Testing软件测试网vy-G9_[4c

       Ring::s_nCnt = 0;51Testing软件测试网fQ I6h+Lcbl%na+j[

}51Testing软件测试网#d+i$YV+x\*I

 51Testing软件测试网8R'_$l%c4F.^^

int main()                 

{51Testing软件测试网BJ ?m'g#\y5U

       Ring ring(3);51Testing软件测试网 }7l I;m#BGo

_fU \+L#]aJ0       ring.startDownRing();51Testing软件测试网/z'r ` F` Ica
^

       ring.totalCnt();51Testing软件测试网 ^W/\*VQ%e5P

YFAd*Ceo0       ring.setUpZero();      //置为0

 51Testing软件测试网~(t#J-U+h]

       ring.startUpRing();

T2E:z"wf4s0       ring.totalCnt();

*g5}5d GevU DW?0       ring.setUpZero();

      51Testing软件测试网;zi3eE2g:K[X

c8Ag-R7fW0       return 0;51Testing软件测试网7C']X"U$N |*mc

y2@ k
_mxh4}6r2QT0}51Testing软件测试网*hrB;H%z%}3DR]

　　存在以下序列即：51Testing软件测试网!W'o!hYsL r

　　呈现阶层递增的趋势。