以前回復(fù)一個關(guān)于9連環(huán)解法的問題,看過《計算機(jī)程序設(shè)計藝術(shù)》的人都知道，這個問題的是中國的古老游戲，其解法就是“格雷二進(jìn)制”的描述。

?九連環(huán)是一種傳統(tǒng)的中國玩具，它有九個連在一起的環(huán)河一根長棒組成。一開始，九個環(huán)都裝在榜上，由于其特殊的構(gòu)造，只能按以下規(guī)則從棒上取下或裝上環(huán)：

1）所有環(huán)只能從棒的一端取下。將環(huán)按距離這一端的遠(yuǎn)近從近到遠(yuǎn)依次編號為1~9號環(huán)。無論知名移動環(huán)，環(huán)的順序都不會改變

2）1號環(huán)隨時可以取下或裝上

3）當(dāng)K-1(K=2-9)號之前的環(huán)（不包含K-1號環(huán)）全部被取下，K-1號環(huán)還在棒上時，可將K號環(huán)取下或裝上
已有以下兩個函數(shù)

UpOne（int idx）；//裝上某個序號的環(huán)（無法裝上時不會有動作）

DownOne（int idx）；//卸下某個序號的環(huán)（無法卸下時不會有動作）
請寫出裝上和卸下全部環(huán)的函數(shù)，并且將具體實現(xiàn)的C#代碼寫出（需用控制臺輸出）

?

有很多網(wǎng)友提出了各種不同的解決方案，也不乏寫了大篇代碼的。

其實這個問題說起來很簡單，下面是我的解決方案

這個問題上帝已經(jīng)解決把公式描述出來了,是格雷二進(jìn)制編碼的問題,大師的名字就叫高納德.克努特?

公式就是

T0=空

Tn+1="0"+Tn,"1"+Tn的逆?

參考<<計算機(jī)程序設(shè)計藝術(shù) 第四卷 第二冊>>

比如

T0=空

T1={0,1}?

T2=0{0,1},1{1,0}=00,01,11,10?

T3=0{00,01,11,10},1{10,11,01,00}? =000,001,011,010,110,111,101,100?

...

依次類推 T9=...

這個組合里包含了所有的可能性,注意到按這個方法形成的組合無論往左還是往右,都只有一個位變化了? 比如

“000,001,011,010,110,111,101,100?”：000->001->011->010-110->111->101-100,每一步都只變化了一位

如果是3連環(huán)的話，將環(huán)套上的順序是

000,001,011,010,110,111

環(huán)取下的順序正好相反?

要判斷在每個狀態(tài)下具體一個環(huán)是否能套上，則判斷該狀態(tài)右邊的值是否與該環(huán)對應(yīng)的值不同?

要判斷在每個狀態(tài)下具體一個環(huán)是否能取下，則判斷該狀態(tài)左邊的值是否與該環(huán)對應(yīng)的值不同?

算法就是這樣，是否能套上，就把T（N）預(yù)先計算出來，然后逐個對比就OK

轉(zhuǎn)載于:https://www.cnblogs.com/stst/p/4909734.html

總結(jié)

以上是生活随笔為你收集整理的九连环算法--《计算机程序设计艺术》的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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