引用Matrix67
Gray碼 假如我有4個潛在的GF澳化，我需要決定最終到底和誰在一起蒋纬。一個簡單的辦法就是，依次和每個MM交往一段時間狡逢，最后選擇給我?guī)淼摹皾M意度”最大的MM。但看了dd牛的理論后拼卵，事情開始變得復(fù)雜了：我可以選擇和多個MM在一起。這樣蛮艰，需要考核的狀態(tài)變成了2^4=16種（當(dāng)然包括0000這一狀態(tài)腋腮，因為我有可能是玻璃）∪副耍現(xiàn)在的問題就是，我應(yīng)該用什么順序來遍歷這16種狀態(tài)呢即寡？ 傳統(tǒng)的做法是徊哑，用二進制數(shù)的順序來遍歷所有可能的組合。也就是說聪富，我需要以0000->0001->0010->0011->0100->…->1111這樣的順序?qū)γ糠N狀態(tài)進行測試莺丑。這個順序很不科學(xué)，很多時候狀態(tài)的轉(zhuǎn)移都很耗時墩蔓。比如從0111到1000時我需要暫時甩掉當(dāng)前所有的3個MM梢莽，然后去把第4個MM。同時改變所有MM與我的關(guān)系是一件何等巨大的工程啊奸披。因此昏名，我希望知道，是否有一種方法可以使得阵面，從沒有MM這一狀態(tài)出發(fā)轻局，每次只改變我和一個MM的關(guān)系（追或者甩），15次操作后恰好遍歷完所有可能的組合（最終狀態(tài)不一定是1111）样刷。大家自己先試一試看行不行仑扑。 解決這個問題的方法很巧妙。我們來說明置鼻，假如我們已經(jīng)知道了n=2時的合法遍歷順序镇饮，我們?nèi)绾蔚玫絥=3的遍歷順序。顯然沃疮，n=2的遍歷順序如下：
00011110
你可能已經(jīng)想到了如何把上面的遍歷順序擴展到n=3的情況盒让。n=3時一共有8種狀態(tài)，其中前面4個把n=2的遍歷順序照搬下來司蔬，然后把它們對稱翻折下去并在最前面加上1作為后面4個狀態(tài)：
000001011010 ↑——–110 ↓111101100
用這種方法得到的遍歷順序顯然符合要求邑茄。首先，上面8個狀態(tài)恰好是n=3時的所有8種組合俊啼，因為它們是在n=2的全部四種組合的基礎(chǔ)上考慮選不選第3個元素所得到的肺缕。然后我們看到，后面一半的狀態(tài)應(yīng)該和前面一半一樣滿足“相鄰狀態(tài)間僅一位不同”的限制授帕，而“鏡面”處則是最前面那一位數(shù)不同同木。再次翻折三階遍歷順序，我們就得到了剛才的問題的答案：
0000000100110010011001110101010011001101111111101010101110011000
這種遍歷順序作為一種編碼方式存在跛十，叫做Gray碼（寫個中文讓蜘蛛來抓：格雷碼）彤路。它的應(yīng)用范圍很廣。比如芥映，n階的Gray碼相當(dāng)于在n維立方體上的Hamilton回路洲尊，因為沿著立方體上的邊走一步远豺，n維坐標(biāo)中只會有一個值改變。再比如坞嘀，Gray碼和Hanoi塔問題等價躯护。Gray碼改變的是第幾個數(shù)，Hanoi塔就該移動哪個盤子丽涩。比如棺滞，3階的Gray碼每次改變的元素所在位置依次為1-2-1-3-1-2-1，這正好是3階Hanoi塔每次移動盤子編號矢渊。如果我們可以快速求出Gray碼的第n個數(shù)是多少继准，我們就可以輸出任意步數(shù)后Hanoi塔的移動步驟。現(xiàn)在我告訴你昆淡，Gray碼的第n個數(shù)（從0算起）是n xor (n shr 1)锰瘸，你能想出來這是為什么嗎？先自己想想吧昂灵。
下面我們把二進制數(shù)和Gray碼都寫在下面避凝，可以看到左邊的數(shù)異或自身右移的結(jié)果就等于右邊的數(shù)。
二進制數(shù) Gray碼 000 000 001 001 010 011 011 010 100 110 101 111 110 101 111 100
從二進制數(shù)的角度看眨补，“鏡像”位置上的數(shù)即是對原數(shù)進行not運算后的結(jié)果管削。比如，第3個數(shù)010和倒數(shù)第3個數(shù)101的每一位都正好相反撑螺。假設(shè)這兩個數(shù)分別為x和y含思，那么x xor (x shr 1)和y xor (y shr 1)的結(jié)果只有一點不同：后者的首位是1，前者的首位是0甘晤。而這正好是Gray碼的生成方法含潘。這就說明了，Gray碼的第n個數(shù)確實是n xor (n shr 1)线婚。
? 今年四月份mashuo給我看了這道題遏弱，是二維意義上的Gray碼。題目大意是說塞弊，把0到2(n+m)-1的數(shù)寫成2n * 2^m的矩陣漱逸，使得位置相鄰兩數(shù)的二進制表示只有一位之差。答案其實很簡單游沿，所有數(shù)都是由m位的Gray碼和n位Gray碼拼接而成饰抒，需要用左移操作和or運算完成。完整的代碼如下：
var x,y,m,n,u:longint;
begin
readln(m,n);
for x:=0 to 1 shl m-1 do
begin
u:=(x xor (x shr 1)) shl n; //輸出數(shù)的左邊是一個m位的Gray碼
for y:=0 to 1 shl n-1 do
write(u or (y xor (y shr 1)),' '); //并上一個n位Gray碼
writeln;
end;
end.
