[趣味數學(xué)]趣談“九連環(huán)與格雷碼”
2006-12-28 15:17:34中國高中生網(wǎng)
分析解九連環(huán)的完全記法，由于每次只動(dòng)一個(gè)環(huán)，故兩步的表示也只有一個(gè)數字不同。下面以五個(gè)環(huán)為例分析。左邊起第一列的五位數是5個(gè)環(huán)的狀態(tài)，依次由第一環(huán)到第五環(huán)。第二列是把這個(gè)表示反轉次序的五位數，似乎是二進(jìn)制數，但是與第四列比較就可以看出這不是步數的二進(jìn)制數表示。第三列是從初始狀態(tài)到這個(gè)狀態(tài)所用的步數。最右邊一列才是步數的二進(jìn)制表示。
00000－00000－0－00000
10000－00001－1－00001
11000－00011－2－00010
01000－00010－3－00011
01100－00110－4－00100
11100－00111－5－00101
10100－00101－6－00110
00100－00100－7－00111
00110－01100－8－01000
10110－01101－9－01001
11110－01111－10－01010
01110－01110－11－01011
01010－01010－12－01100
11010－01011－13－01101
10010－01001－14－01110
00010－01000－15－01111
00011－11000－16－10000
10011－11001－17－10001
11011－11011－18－10010
01011－11010－19－10011
01111－11110－20－10100
11111－11111－21－10101
我們發(fā)現，右邊一列數恰好是十進(jìn)制數0到21的二進(jìn)制數的格雷碼！ 這當然需要21步。如果把5位二進(jìn)制數依次寫(xiě)完，就是
10111－11101－22－10110
00111－11100－23－10111
00101－10100－24－11000
10101－10101－25－11001
11101－10111－26－11010
01101－10110－27－11011
01001－10010－28－11100
11001－10011－29－11101
10001－10001－30－11110
00001－10000－31－11111
這說(shuō)明，對于只有5個(gè)環(huán)的五連環(huán)，從初始到狀態(tài)11111用的不是并不是最多，到狀態(tài)00001才是最多，用31步。類(lèi)似，對于九連環(huán)，從初始到狀態(tài)111111111用的不是并不是最多，到狀態(tài)000000001才是最多，用511步。由于格雷碼111111111表示二進(jìn)制數101010101，表示十進(jìn)制數341，故從初始狀態(tài)到9個(gè)環(huán)全部上去用341步。這就是九連環(huán)中蘊涵的數學(xué)內涵。
注 由二進(jìn)制數轉換為格雷碼：從右到左檢查，如果某一數字左邊是0，該數字不變；如果是1，該數字改變（0變?yōu)?，1變?yōu)?）。例，二進(jìn)制數11011的格雷碼是10110.
由格雷碼表示變?yōu)槎M(jìn)制數：從右到左檢查，如果某一數字的左邊數字和是偶數，該數字不變；如果是奇數，該數字改變。
例 格雷碼11011表示為二進(jìn)制數是10010.
以上可以用口訣幫助記憶：2G一改零不改，G2奇變偶不變。
例 設九連環(huán)的初始狀態(tài)是110100110，要求終止狀態(tài)是001001111，簡(jiǎn)單解法與完整解法各需要多少步？過(guò)程如何？
解 初始狀態(tài)110100110，格雷碼是011001011，轉換為二進(jìn)制數是010001101，相應十進(jìn)制數是141.終止狀態(tài)是001001111，格雷碼是111100100，轉換為二進(jìn)制數是101000111，相應十進(jìn)制數是327.二者差326－141＝186，完整解法需要186步。
簡(jiǎn)單解法步數，我們由141，327分別求相應的簡(jiǎn)單步數，
對于N=141，得到N0=103；對于N=327，N0=242.二者差139，故簡(jiǎn)單步數139.這個(gè)結果很容易在下一頁(yè)九連環(huán)電腦游戲上驗證。
