<dd id="mqxjw"><track id="mqxjw"></track></dd>
  1. <dd id="mqxjw"><track id="mqxjw"></track></dd>
    <em id="mqxjw"><acronym id="mqxjw"><blockquote id="mqxjw"></blockquote></acronym></em>

    <legend id="mqxjw"></legend>
    <tbody id="mqxjw"></tbody>

    菜單導航

    [趣味數學]趣談“九連環與格雷碼”_大學微博

    作者:?楊超月 發布時間:?2020年02月19日 00:02:21
    九連環的解法  九連環的歷史

      分析解九連環的完全記法,由于每次只動一個環,故兩步的表示也只有一個數字不同。下面以五個環為例分析。左邊起第一列的五位數是5個環的狀態,依次由第一環到第五環。第二列是把這個表示反轉次序的五位數,似乎是二進制數,但是與第四列比較就可以看出這不是步數的二進制數表示。第三列是從初始狀態到這個狀態所用的步數。最右邊一列才是步數的二進制表示。

      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

      我們發現,右邊一列數恰好是十進制數0到21的二進制數的格雷碼! 這當然需要21步。如果把5位二進制數依次寫完,就是

      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

      這說明,對于只有5個環的五連環,從初始到狀態11111用的不是并不是最多,到狀態00001才是最多,用31步。類似,對于九連環,從初始到狀態111111111用的不是并不是最多,到狀態000000001才是最多,用511步。由于格雷碼111111111表示二進制數101010101,表示十進制數341,故從初始狀態到9個環全部上去用341步。這就是九連環中蘊涵的數學內涵。

      注 由二進制數轉換為格雷碼:從右到左檢查,如果某一數字左邊是0,該數字不變;如果是1,該數字改變(0變為1,1變為0)。例,二進制數11011的格雷碼是10110.

      由格雷碼表示變為二進制數:從右到左檢查,如果某一數字的左邊數字和是偶數,該數字不變;如果是奇數,該數字改變。

      例 格雷碼11011表示為二進制數是10010.

      以上可以用口訣幫助記憶:2G一改零不改,G2奇變偶不變。

      例 設九連環的初始狀態是110100110,要求終止狀態是001001111,簡單解法與完整解法各需要多少步?過程如何?

      解 初始狀態110100110,格雷碼是011001011,轉換為二進制數是010001101,相應十進制數是141.終止狀態是001001111,格雷碼是111100100,轉換為二進制數是101000111,相應十進制數是327.二者差326-141=186,完整解法需要186步。

      簡單解法步數,我們由141,327分別求相應的簡單步數,

      對于N=141,得到N0=103;對于N=327,N0=242.二者差139,故簡單步數139.這個結果很容易在下一頁九連環電腦游戲上驗證。

    熱門標簽