九连环的递归算法（C和C++）
九连环的递归算法
一、九连环简介
九连环游戏是中国人自己发明的，它的历史非常悠久，据说是起源于战国时期。九连环主要是由一个框架和九个圆环组成：每个圆环上连有一个直杆，而这个直杆则在后面一个圆环内穿过，九个直杆的另一端用一块木板或圆环相对固定。
二、九连环的规律
通过玩九连环你就会发现存在这样一个规律：
（1）第 1环可以自由上下
（2）而上/下第 n环时（n>1),则必须满足：
（a）第 n-1个环在架上
（b）前 n-2个环全部在架下
三、拆解/安装的过程
正确的拆解是先以第 9环为目标，先拆下它，简化为拆一个 8连环。接着再也第 8 环为目标，拆下它，简化为拆一个 7连环。以此类推，直至全部拆解。
其实安装和拆解是一个道理，因为他们均是使用上面说的规律来完成的。
正确是安装也是先以第 9环为目标，先装上它，简化为装一个 8连环。接着再也第 8 环为目标，装上它，简化为装一个 7连环。以此类推，直至全部安装。
当然，现在这么说是便于理解，当你深刻的理解了上面所说的规律后，就会发现，安装上第 9环后，问题可以被简化为装一个 7连环，而当装上第 7 环后，问题就被简化为装一个 5连环了，呵呵，就是这样的，不知道你现在是否明白我的意思……
四、一个猜想
仔细观察九连环的结构、思考九连环的规律及拆解/安装的过程，你是不是有一种感觉：九连环跟递归一定有联系。你看，递归的基本思想是把一个大的问题分解为一个规模较小的问题，从这些较小问题的解，构造出大问题的解，而这些规模较小的问题，用同样的方法分解成更小的问题，从更小问题的解，构造出较小的问题，一层层下去，一般最后总是可以分解到可以直接求解的小问题。嘿嘿，九连环的拆解/安装多么的符合这个规律啊……^_^
五、算法实现
以下是算法实现，程序写的很简洁，省略了很多功能的实现，比如计数等，如果你觉得有必要的话，可以自行添加上去，我相信很容易，并不要很多的改动。
The C Code Here:
/****************************/
任意 N连环均适用
日期：2002/11/6
程序设计：道可道
腾讯QQ：3908000
电邮：Havelife@mail.csdn.net
/****************************/
void UpRing(int n); /*函数声明*/
void DownRing(int n) /*下环逻辑*/
{
if(n>2) DownRing(n-2);
printf("下第%d环\n",n);
if(n>2) UpRing(n-2);
if(n>1) DownRing(n-1);
}
void UpRing(int n) /*上环逻辑*/
{
if(n>1) UpRing(n-1);
if(n>2) DownRing(n-2);
printf("上第%d环\n",n);
if(n>2) UpRing(n-2);
}
void main()
{
printf("拆解\n");
DownRing(9);
printf("安装\n");
UpRing(9);
printf("结束\n");
}
The C++ Code Here:
/****************************/
任意 N连环均适用
日期：2012/8/12
程序设计：YCY
电邮：ycy360@163.com
/****************************/
#include<iostream>
using namespace std;
class Ring
{
public:
Ring(int n):nRingNum(n){}
void UpRing(int n);
void DownRing(int n);
void startDownRing();
void startUpRing();
void totalCnt();
void setUpZero();
private:
int nRingNum;
static int s_nCnt;
};
int Ring::s_nCnt = 0; //计数
void Ring::UpRing(int n) //Upring是DownRing的逆过程.
{
++s_nCnt;
if(n>1) UpRing(n-1);
if(n>2) DownRing(n-2);
cout << "上第" << n << "环" << endl;
if(n>2) UpRing(n-2);
}
void Ring::DownRing(int n)
{
++s_nCnt;
if(n>2) DownRing(n-2);
cout <<"下第" << n << "环" << endl;
if(n>2) UpRing(n-2);
if(n>1) DownRing(n-1);
}
void Ring::startDownRing()
{
cout << "拆解" << nRingNum << "连环操作!" << endl;
DownRing(nRingNum);
cout << "拆解完毕" << endl;
}
void Ring::startUpRing()
{
cout << "安装" << nRingNum << "连环操作!" << endl;
UpRing(nRingNum);
cout << "安装完毕" << endl;
}
void Ring::totalCnt()
{
cout << "共累计上、下环" << s_nCnt << "次!" << endl << endl;
}
void Ring::setUpZero()
{
Ring::s_nCnt = 0;
}
int main()
{
Ring ring(3);
ring.startDownRing();
ring.totalCnt();
ring.setUpZero(); //置为0
ring.startUpRing();
ring.totalCnt();
ring.setUpZero();
return 0;
}
存在以下序列即：
N(numOfRing）
1
2
3
4
5
6
7
8
9
10
11
…
Cnts
1
2
5
10
21
42
85
170
341
682
1365
….
呈现阶层递增的趋势。
