Re: [問題] 二進位蟲

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者hank5925 (樹爺)時間13年前 (2013/01/16 18:06)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

43 拋磚引玉一下剛剛閒來沒事想說用暴力法畫出 N = 2~5 的 state diagram 在列出來之前要先說明一個大前提就是說要得到全部0的A目標是以最少次數達到目標阻止A的B自然也不會無緣無故幫助A更快達到目標因為畫出完整的 state diagram 有些麻煩所以我用下面的數列呈現 N = 2 00110 N = 3 0001110100 N = 4 0000111101100101000 N = 5 000001111101110011010110001010010000 ------------------------------------------------- 下面解釋數列怎樣形成的以 N = 3 為例有 000, 001, 010, 011, 100, 101, 110, 111 8種可能 000 (end) | 000 001 > 000 (> 100 不合前提) | 001 010 | 010 < 101 (< 001 不合前提) 011 > 001 (> 101 不合前提) | 011 100 | 100 101 | 101 110 | 110 < 111 (< 011 不合前提) 111 > 011 (> 111 不合前提) | 111 化簡後 100 010 < 101 110 < 111 > 011 > 001 > 000 顯然 101 > 110 (> 010 loop 不合前提) 所以 010 < 101 > 110 < 111 > 011 > 001 > 000 最後 100 < 010 (< 110 不合前提) 結果便產生一個數列 100, 010, 101, 110, 111, 011, 001, 000 整理後 100 010 101 110 111 011 001 000 ---------- 0001110100 就是前面 N = 3 的數列換句話說 N = 4 的數列 0000111101100101000 用另一種呈現方式就是 1000, 0100, 1010, 0101, 0010, 1001, 1100, 0110, 1011, 1101, 1110, 1111, 0111, 0011, 0001, 0000 ------------------------------------------------- 從 N = 2 ~ 5 可以看到幾點有趣的現象: 1) 在大前提成立下看不出有什麼可以阻止A勝出的方法 2) 第一項永遠都是 1000.....000 這大概就是讓A步數最多的解吧 3) 個人比較喜歡下面的呈現方式雖然說還看不出有什麼規則就是... 1000 1100 1110 1111 0100 0110 0111 1010 1011 0011 0101 1101 0001 0010 0000 1001 附上 N = 5 的情形 10000 11000 11100 11110 11111 01000 01100 01110 01111 00100 10110 10111 00111 10010 01011 11011 00011 01001 10101 11101 00001 10100 11010 00000 01010 01101 00101 00110 00010 10011 10001 11001 4) 每組數字 0000 ~ 1111 都有出現在數列裡總覺得這種數列應該很有名才對吧但怎麼查都查不到以上 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.109.135.110