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

N1{%[ g"pIV\&N0　　一、九连环简介51Testing软件测试网y-J-zs(M

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

　　二、九连环的规律51Testing软件测试网 M
q-KV?@"T

　　通过玩九连环你就会发现存在这样一个规律：51Testing软件测试网7A~7A7N@WC

　　（1）第 1环可以自由上下

{-}f&KAM_JI0　　（2）而上/下第 n环时（n>1），则必须满足：51Testing软件测试网}(G)O4k`7m(R\H

cN^.E:\bu0　　　　（a）第 n-1个环在架上

j\5^m:h"A5p0　　　　（b）前 n-2个环全部在架下

]7P#n-q[ ^u)r~0　　三、拆解/安装的过程51Testing软件测试网lM2?JWGK+s

\6a+ak3C0UAT0　　正确的拆解是先以第 9环为目标，先拆下它，简化为拆一个 8连环。接着再也第 8 环为目标，拆下它，简化为拆一个 7连环。以此类推，直至全部拆解。51Testing软件测试网P&M4J;A;N3a"}8JH

kex,M%F,?0　　其实安装和拆解是一个道理，因为他们均是使用上面说的规律来完成的。

@AN)N8s"Hi$YP8ws.K0　　正确是安装也是先以第 9环为目标，先装上它，简化为装一个 8连环。接着再也第 8 环为目标，装上它，简化为装一个 7连环。以此类推，直至全部安装。

/V8fnO:yo'}0　　当然，现在这么说是便于理解，当你深刻的理解了上面所说的规律后，就会发现，安装上第 9环后，问题可以被简化为装一个 7连环，而当装上第 7 环后，问题就被简化为装一个 5连环了，呵呵，就是这样的，不知道你现在是否明白我的意思……51Testing软件测试网sl%i!{M7u

　　四、一个猜想51Testing软件测试网S*G-R9D{)Py@

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

　　五、算法实现51Testing软件测试网a5g~0e+I4xh6y-l

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

　　The C Code Here：51Testing软件测试网KlVT9O)Cvm&n

M ax5Djbf'i0The C++ Code Here:51Testing软件测试网9pvi$cV"Dg

,lY9NIp#?d0/****************************/51Testing软件测试网1c2]ik H `&XO
           任意 N连环均适用

Td'{9E4CAp:H0           日期：2012/8/1251Testing软件测试网.@(?"M$Z*W6j:Gk

:OwQ.Ae&c0           程序设计：YCY
,QY VN5xzr@0           电邮：ycy360@163.com51Testing软件测试网i6R4u[)pG6f-L

@XOn,L$WW$L0/****************************/

*~"Q#?t(n_E0#include<iostream>

TdzkH"SK0using namespace std;

 51Testing软件测试网b)S f4hj(o8ws{

class Ring

x;V'K0M v7t7Ic0{51Testing软件测试网 e gXv*mWD"`ecF

public:

       Ring(int n):nRingNum(n){}

       void UpRing(int n);51Testing软件测试网J'_ vM m5Nz/O

g ~.R"i j*i ~@T0       void DownRing(int n);51Testing软件测试网L U!g/j$~ MA

R0VOf#?q/Z0       void startDownRing();51Testing软件测试网~oY*P|1X

       void startUpRing();

5`5Z\h,J0\ zz0       void totalCnt();51Testing软件测试网K
b s*x5ht

       void setUpZero();51Testing软件测试网*I
C Wk7{glhfT

private:

AD,z7M&v0       int nRingNum;

       static int s_nCnt;

jP-H4eSI:u0};

)@ [M(g?^ A4M.BBG |U0 51Testing软件测试网-rFU\y;Wr J

int Ring::s_nCnt = 0;    //计数51Testing软件测试网nn{bxC5J

void Ring::UpRing(int n)  //Upring是DownRing的逆过程.51Testing软件测试网H*iaH1o%}#b LkNXc

f4K(Db f0{

zyb#s"f y0       ++s_nCnt;51Testing软件测试网jkylJ

}sNVkO8],?0       if(n>1) UpRing(n-1);51Testing软件测试网4n u0G%Pc.p4G)Q

NnZuv$V$b0       if(n>2) DownRing(n-2);

       cout << "上第" << n << "环" << endl;51Testing软件测试网1x e(_uk0r,B
yh

       if(n>2) UpRing(n-2);51Testing软件测试网9J9h6mRl*OB:|)~

,la q @(b/|u~0}51Testing软件测试网MH1z.mr|Z:r

 51Testing软件测试网{D{z0dM7I

|a8e6yev^_&G)`0void Ring::DownRing(int n)51Testing软件测试网,F`sG2C/O#PU/x

Z*d$n8Y.?a:j6L0{51Testing软件测试网C,~rX~_

(UP\8p,I|X0       ++s_nCnt;51Testing软件测试网"g%i!B#nW's
Nk

       if(n>2) DownRing(n-2);51Testing软件测试网EZ#h:V7v

{4Ig8n6J[8Bo8r0       cout <<"下第" << n << "环" << endl;

6r|yO?#Q7sw0       if(n>2) UpRing(n-2);

       if(n>1) DownRing(n-1);51Testing软件测试网`!Y*ZFyn

}51Testing软件测试网"b!wB9|f }E

n3N*to"xl%{0 

void Ring::startDownRing()

{

       cout << "拆解" << nRingNum << "连环操作!" << endl;51Testing软件测试网1KCijj}Ic
d

       DownRing(nRingNum);

       cout << "拆解完毕" << endl;51Testing软件测试网h9d^;DZ:NN-~4W

}51Testing软件测试网"^z0_0\xx9R

{tk8Po }:I0 51Testing软件测试网]1Q[jVIg,G

void Ring::startUpRing()51Testing软件测试网{E.Z!Q*`5c@.d

{

       cout << "安装" << nRingNum << "连环操作!" << endl;51Testing软件测试网
Yu#s/x }&VL"y&jg

/JG+Z#\A/TC&of0       UpRing(nRingNum);51Testing软件测试网7y#T,@L {:]5J4a3d

       cout << "安装完毕" << endl;

}

Y'm'h-yPC$S0 

[8k jcW2jd0void Ring::totalCnt()51Testing软件测试网]$}DrSe)_u;Kiq

J Qc3~B*p0{

8rc _?Z&HW%p0       cout << "共累计上、下环" << s_nCnt << "次!" << endl << endl;

}51Testing软件测试网 mz3s?7y g

void Ring::setUpZero()51Testing软件测试网 lN1d&~8z

{51Testing软件测试网 T1y+PF+M'B

       Ring::s_nCnt = 0;51Testing软件测试网-P)X:g!xbtl

}51Testing软件测试网6WI'j LS7Y w4{

^c/ME7B8_ wG]*mU0 51Testing软件测试网6W_%y1^pF'{#h0ZB

?e*g*T
k,F2vY0int main()                 

{51Testing软件测试网7E4{2hS4p%F0`a_`,_

       Ring ring(3);

2DZ q*|Ev0       ring.startDownRing();

.[5}
?){UX
{JLE0       ring.totalCnt();

&G0ZG-m/F[0       ring.setUpZero();      //置为0

 51Testing软件测试网3s4JXm C.j }

0d"v8U?\r(p0       ring.startUpRing();

       ring.totalCnt();51Testing软件测试网\'g9IH&OQOE

+YE{o.JsB QY+M0       ring.setUpZero();

I z5Nd(R'kD(^ {6M0       return 0;51Testing软件测试网W-kMH1?"pK6C ]

}51Testing软件测试网wp@5z#fV'h fl

　　存在以下序列即：51Testing软件测试网I2^sn&Ug

51Testing软件测试网a0Z"nbRk[#u

　　呈现阶层递增的趋势。51Testing软件测试网jx#h W6\I`
u'y1Z