九連環的遞歸算法
一、九連環簡介
九連環游戲是中國人自己發明的，它的歷史非常悠久，據說是起源於戰國時期。九連環主要是由一個框架和九個圓環組成：每個圓環上連有一個直桿，而這個直桿則在後面一個圓環內穿過，九個直桿的另一端用一塊木板或圓環相對固定。
二、九連環的規律
通過玩九連環你就會發現存在這樣一個規律：
（1）第 1環可以自由上下
（2）而上/下第 n環時（n>1),則必須滿足：
（a）第 n-1個環在架上
（b）前 n-2個環全部在架下
三、拆解/安裝的過程
正確的拆解是先以第 9環為目標，先拆下它，簡化為拆一個 8連環。接著再也第 8 環為目標，拆下它，簡化為拆一個 7連環。以此類推，直至全部拆解。
其實安裝和拆解是一個道理，因為他們均是使用上面說的規律來完成的。
正確是安裝也是先以第 9環為目標，先裝上它，簡化為裝一個 8連環。接著再也第 8 環為目標，裝上它，簡化為裝一個 7連環。以此類推，直至全部安裝。
當然，現在這麼說是便於理解，當你深刻的理解了上面所說的規律後，就會發現，安裝上第 9環後，問題可以被簡化為裝一個 7連環，而當裝上第 7 環後，問題就被簡化為裝一個 5連環了，呵呵，就是這樣的，不知道你現在是否明白我的意思……
四、一個猜想
仔細觀察九連環的結構、思考九連環的規律及拆解/安裝的過程，你是不是有一種感覺：九連環跟遞歸一定有聯系。你看，遞歸的基本思想是把一個大的問題分解為一個規模較小的問題，從這些較小問題的解，構造出大問題的解，而這些規模較小的問題，用同樣的方法分解成更小的問題，從更小問題的解，構造出較小的問題，一層層下去，一般最後總是可以分解到可以直接求解的小問題。嘿嘿，九連環的拆解/安裝多麼的符合這個規律啊……^_^
五、算法實現
以下是算法實現，程序寫的很簡潔，省略了很多功能的實現，比如計數等，如果你覺得有必要的話，可以自行添加上去，我相信很容易，並不要很多的改動。
e C Code Here: /****************************/ 任意 N連環均適用 程序設計：道可道 個人網站：www.shengshiyouxi.com 電郵：[email protected] /****************************/ 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 電郵：[email protected] /****************************/ #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
….
