九連環(huán)遞歸算法及其拓展

1 九連環(huán)簡(jiǎn)介

九連環(huán)是中國(guó)最杰出的益智游戲。長(zhǎng)期以來(lái)，這個(gè)益智游戲是數(shù)學(xué)家及現(xiàn)代的電子計(jì)算機(jī)專家們用于教學(xué)研究的課題和例子。

九連環(huán)以金屬絲制成9個(gè)圓環(huán)，將圓環(huán)套裝在橫板或各式框架上，并貫以環(huán)柄。把玩時(shí)，按照一定的程序反復(fù)操作，可使9個(gè)圓環(huán)分別解開，或合二為一。從完整狀態(tài)解下所有九個(gè)環(huán)一般需要解341步。

2 九連環(huán)規(guī)則

在解九連環(huán)的過(guò)程中間，只有兩個(gè)規(guī)則可循。并且這兩個(gè)規(guī)則在游戲中交替使用：

規(guī)則一：第一環(huán)可以在任何時(shí)候放上或取下環(huán)柄。

規(guī)則二：只有緊跟在領(lǐng)頭環(huán)后的環(huán)可以放上或取下環(huán)柄。（領(lǐng)頭環(huán)是套在柄上的最前面的環(huán)）

如果所有的環(huán)都在柄上，那么第一步可以有兩個(gè)選擇。（根據(jù)規(guī)則一，取下第一環(huán)；或者根據(jù)規(guī)則二，取下第二環(huán)。）但是，走完第一步以后，我們只需要交替使用這兩個(gè)規(guī)則，就不會(huì)走回頭路。

當(dāng)環(huán)數(shù)是奇數(shù)時(shí)，第一步必須是要將第一環(huán)取下（規(guī)則一）。要解是偶數(shù)的連環(huán)時(shí)，第一步則是要將第二環(huán)取下（規(guī)則二）。取下一個(gè)環(huán)就是要將這個(gè)環(huán)滑過(guò)柄尖并從柄中由上而下滑下。放上一個(gè)環(huán)就是要將這個(gè)環(huán)由下而上穿過(guò)柄中，再滑過(guò)柄尖放入柄上。

3 九連環(huán)遞歸描述

（1）第 1 環(huán)可以自由上下 （2）而上/下第 n(n>1) 環(huán)時(shí)，則必須滿足：（a）第 n-1 個(gè)環(huán)在架上（b）前 n-2 個(gè)環(huán)全部在架下

4 九連環(huán)拆解安裝過(guò)程

正確的拆解是先以第 9 環(huán)為目標(biāo)，先拆下它，簡(jiǎn)化為拆一個(gè) 8 連環(huán)。接著再也第 8 環(huán)為目標(biāo)，拆下它，簡(jiǎn)化為拆一個(gè) 7 連環(huán)。以此類推，直至全部拆解。

其實(shí)安裝和拆解是一個(gè)道理，因?yàn)樗麄兙鞘褂蒙厦嬲f(shuō)的規(guī)律來(lái)完成的。

正確是安裝也是先以第 9 環(huán)為目標(biāo)，先裝上它，簡(jiǎn)化為裝一個(gè) 8 連環(huán)。接著再也第 8 環(huán)為目標(biāo)，裝上它，簡(jiǎn)化為裝一個(gè) 7 連環(huán)。以此類推，直至全部安裝。

實(shí)踐中，我們會(huì)進(jìn)一步發(fā)現(xiàn)一個(gè)簡(jiǎn)單規(guī)律，當(dāng)安裝上第 9 環(huán)后，問(wèn)題可以被簡(jiǎn)化為裝一個(gè) 7 連環(huán)，而當(dāng)裝上第 7 環(huán)后，問(wèn)題就被簡(jiǎn)化為裝一個(gè) 5 連環(huán)了。

5 求解九連環(huán)及相關(guān)問(wèn)題

5.1 拆解/安裝 n 連環(huán)

5.1.1 問(wèn)題描述

輸入一個(gè)正整數(shù) n ，輸出 n 連環(huán)的拆解和安裝步驟，以及相應(yīng)步驟數(shù)。

5.1.2 編程思路

遞歸實(shí)現(xiàn)問(wèn)題求解。

拆解 n 連環(huán)，首先在第 n-1 在軸上的前提下卸下第 n 環(huán)前需要將前 n-2 環(huán)全部卸下，然后才能卸下第 n 環(huán)，之后裝上前 n-2 環(huán)，此時(shí)已經(jīng)簡(jiǎn)化為拆解 n-1 連環(huán)問(wèn)題，開始拆解 n-1 連環(huán)，步驟同 n 連環(huán)。

安裝 n 連環(huán)，首先在安裝第 n 環(huán)前需要先將第 n-1 環(huán)裝上以及卸下前 n-2 環(huán)，之后才能裝上第 n 環(huán)，此時(shí)可以直接簡(jiǎn)化為安裝 n-2 連環(huán)問(wèn)題，開始安裝 n-2 連環(huán)，步驟同 n 連環(huán)。

以此類推，實(shí)現(xiàn)遞歸。

5.1.3 編程實(shí)現(xiàn)

源碼位于ChineseRings.cpp文件

/***************************************** * 功能：拆解&安裝n連環(huán) * 介紹：輸入數(shù)字n * 輸出n連環(huán)的解法和裝法以及相應(yīng)步數(shù) * * 僅支持環(huán)全部在軸上時(shí)解下和環(huán)全部在軸下時(shí)裝上 ******************************************/# 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; };//記錄拆裝步驟數(shù) int Ring::s_nCnt = 0; void Ring::UpRing(int n) {//Upring是DownRing的逆過(guò)程 if (n != 0){++s_nCnt;if (n > 1) UpRing(n - 1);if (n > 2) DownRing(n - 2);cout << "上第" << n << "環(huán)" << endl;if (n > 2) UpRing(n - 2);} }void Ring::DownRing(int n) {if (n != 0){++s_nCnt;if (n > 2) DownRing(n - 2);cout << "下第" << n << "環(huán)" << endl;if (n > 2) UpRing(n - 2);if (n > 1) DownRing(n - 1);} }void Ring::startDownRing() {// 拆解九連環(huán)cout << "拆解" << nRingNum << "連環(huán)操作!" << endl;DownRing(nRingNum);cout << "拆解完畢" << endl; }void Ring::startUpRing() {// 安裝九連環(huán)cout << "安裝" << nRingNum << "連環(huán)操作!" << endl;UpRing(nRingNum);cout << "安裝完畢" << endl; }void Ring::totalCnt() {cout << "共累計(jì)上、下環(huán)" << s_nCnt << "次!" << endl << endl; }void Ring::setUpZero() {Ring::s_nCnt = 0; }int main() {int n;cin >> n;Ring ring(n);// 拆解過(guò)程ring.startDownRing();ring.totalCnt();ring.setUpZero();//將步驟數(shù)清零，以便記錄安裝步驟// 安裝過(guò)程ring.startUpRing();ring.totalCnt();ring.setUpZero();return 0; }

5.1.4 程序演示

5.2 拆解/安裝任意狀態(tài)九連環(huán)

5.2.1 問(wèn)題描述

九連環(huán)共有 9 位在軸上和在軸下可以分別用 1 和 0 表示，那么九連環(huán)可能的狀態(tài)共有 2^9=512 種。

輸入一個(gè)九連環(huán)的當(dāng)前狀態(tài)（ 9 位 01 串表示），輸出此狀態(tài)下的九連環(huán)的最快解法和最快裝法，以及相應(yīng)步數(shù)。

5.2.2 編程思路

編程思路與前面 5.1 類似，但并不完全相同。也是遞歸實(shí)現(xiàn)，但是要考慮其中狀態(tài)的問(wèn)題，并不是像 5.1 中完整的 n 連環(huán)那樣容易。

首先簡(jiǎn)化問(wèn)題難度，如果是拆解九連環(huán)則從最后一個(gè)在軸上的環(huán)開始向前解，同理，安裝九連環(huán)從最后一個(gè)不在軸上的環(huán)開始向前裝，這樣會(huì)省去一些遞歸。

拆解第 n 環(huán)，首先檢查，如果當(dāng)前環(huán)在軸上，則跳過(guò)，開始拆解前一個(gè)環(huán)，重復(fù)此步驟；接著如果第 n-1 環(huán)在下，需要上第 n-1 環(huán)，然后下 第 n-2 環(huán)，之后下第 n 環(huán)；第 n 環(huán)拆下后，需要將之前卸下的第 n-2 環(huán)裝上，再下第 n-1 環(huán)，重復(fù)回第一步；

安裝第 n 環(huán)，首先如果第 n-1 環(huán)在下，需要上第 n-1 環(huán)，然后下 第 n-2 環(huán)，之后上第 n 環(huán)； 第 n 環(huán)安裝后，需要將之前卸下的第 n-2 環(huán)裝上（如果在上則不需，因?yàn)榭赡艿?n 環(huán)也在上跳過(guò)之前一步），再上第 n-2 環(huán)，重復(fù)回第一步；

重復(fù)遞歸實(shí)現(xiàn)。

5.2.3 編程實(shí)現(xiàn)

源碼位于allChineseRings.cpp文件

/***************************************** * 功能：拆解&安裝九連環(huán) * 介紹：輸入九連環(huán)當(dāng)前狀態(tài)（9位01串表示） * 輸出此時(shí)九連環(huán)的解法和裝法以及相應(yīng)步數(shù) * 0表示環(huán)在軸下 * 1表示環(huán)在軸上 * * 支持九連環(huán)全部狀態(tài)的解法和裝法 ******************************************/# include <iostream> # include <string>using namespace std;class Ring { public:Ring(string s);void UpRing(int n);void DownRing(int n);void startDownRing();void startUpRing();void totalCnt();void setUpZero(); private:int nDownRingNum;int nUpRingNum;static int s_nCnt;string stRing; };// 記錄拆裝步驟數(shù) int Ring::s_nCnt = 0; Ring::Ring(string s) {// 用于簡(jiǎn)化問(wèn)題，拆解過(guò)程中后面的 0 可忽略不計(jì)；安裝過(guò)程中后面的 1 可忽略不計(jì)stRing = s;for (int i = 0;i < 9;i++){if (s[i] == '1')nDownRingNum = i + 1;if (s[i] == '0')nUpRingNum = i + 1;} }void Ring::UpRing(int n) {// 上環(huán)if (n > 0){if (n > 1 && stRing[n - 2] == '0') UpRing(n - 1);if (n > 2) DownRing(n - 2);if (stRing[n - 1] == '0'){stRing[n - 1] = '1';++s_nCnt;cout << "上第" << n << "環(huán)" << endl;}if (n > 1 && stRing[n - 2] == '0') UpRing(n - 1);if (n > 2) UpRing(n - 2);} }void Ring::DownRing(int n) {// 下環(huán)while (n >= 1 && stRing[n - 1] == '0')n--;if (n > 0){if (n > 1 && stRing[n - 2] == '0') UpRing(n - 1);//if (n > 2) DownRing(n - 2);stRing[n - 1] = '0';++s_nCnt;cout << "下第" << n << "環(huán)" << endl;if (n > 2) UpRing(n - 2);if (n > 1) DownRing(n - 1);} }void Ring::startDownRing() {cout << "拆解九連環(huán):" << stRing << endl;DownRing(nDownRingNum);cout << "拆解完畢" << endl; }void Ring::startUpRing() {cout << "安裝九連環(huán):" << stRing << endl;UpRing(nUpRingNum);cout << "安裝完畢" << endl; }void Ring::totalCnt() {cout << "共累計(jì)上、下環(huán)" << s_nCnt << "次!" << endl << endl; }void Ring::setUpZero() {Ring::s_nCnt = 0; }int main() {// 輸入的九連環(huán)狀態(tài) 01 串string s;cin >> s;// 拆解過(guò)程Ring dring(s);dring.startDownRing();dring.totalCnt();dring.setUpZero();// 安裝過(guò)程Ring uring(s);uring.startUpRing();uring.totalCnt();uring.setUpZero();return 0; }

5.2.4 程序演示

6 九連環(huán)問(wèn)題拓展延伸——連環(huán)鎖與格雷碼

6.1 九連環(huán)與格雷碼的關(guān)系

智力玩具九連環(huán)的狀態(tài) 變化符合格雷碼的編碼規(guī)律，漢諾塔的解法也與格雷碼有關(guān)。

九連環(huán)中的每個(gè)環(huán)都有上下兩種狀態(tài)，如果把這兩種狀態(tài)用0/1來(lái)表示的話，這個(gè)狀態(tài)序列就會(huì)形成一種循環(huán)二進(jìn)制編碼（格雷碼）的序列。所以解決九連環(huán)問(wèn)題所需要的狀態(tài)變化數(shù)就是格雷碼111111111所對(duì)應(yīng)的十進(jìn)制數(shù)341。

6.2 問(wèn)題描述

你現(xiàn)在要操作的是一個(gè)n連環(huán)，n為正整數(shù)，給出n連環(huán)的兩種狀態(tài)，計(jì)算出從第一種狀態(tài)變換到第二種狀態(tài)所需要的最少步數(shù)。

輸入：第一行是一個(gè)正整數(shù)m，表示有m組測(cè)試數(shù)據(jù)。
每組測(cè)試數(shù)據(jù)一共3行，第一行是一個(gè)正整數(shù)n (0 < n < 128)，后兩行每一行描述一種狀態(tài)，n個(gè)數(shù)（0或1），用空格隔開。

輸出：對(duì)于每一組測(cè)試數(shù)據(jù)輸出一行，一個(gè)非負(fù)整數(shù)，表示從第一種狀態(tài)變換到第二種狀態(tài)所需要的最少步數(shù)。

6.3 編程思路

將輸入的兩種狀態(tài)當(dāng)初格雷碼轉(zhuǎn)換成二進(jìn)制再轉(zhuǎn)成十進(jìn)制，最后兩個(gè)十進(jìn)制的差的絕對(duì)值就是結(jié)果。

6.4 轉(zhuǎn)換規(guī)則

二進(jìn)制碼->格雷碼：從最右邊一位起，依次將每一位與左邊一位異或，作為對(duì)應(yīng)格雷碼該位的值，最左邊一位不變；

格雷碼->二進(jìn)制碼：從左邊第二位起，將每位與左邊的所有值異或，作為該位解碼后的值（最左邊一位依然不變）。

6.5 編程實(shí)現(xiàn)

此處只簡(jiǎn)單實(shí)現(xiàn)了格雷碼與二進(jìn)制碼的轉(zhuǎn)換。

int toGray(int x) {// 轉(zhuǎn)化為格雷碼 return x^(x>>1); } int toBinary(int x) {// 格雷碼轉(zhuǎn)化為二進(jìn)制 int y = x; while(x>>=1){ y ^= x; } return y; }

?? 資源

大小： 1.76MB
?? 資源下載：https://download.csdn.net/download/s1t16/87425388

總結(jié)

以上是生活随笔為你收集整理的基于C++实现的九连环递归算法及其拓展【100010683】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。