神奇的Gray Code可是在1940年就研究出來，用來在PCM (Pusle Code Modulation)方法傳送訊號時避免錯誤，Gray Code可是有專利保護的喔~~
用Javascript征服演算法 (2-Gray Code)

產生Gray Code程式碼

其實這個題目有點私心，因為看了Gray code與幾何之間的對應關係如此奇妙後，就想來實做看看XDDD

何謂Gray Code?

Gray Code是一個數列集合，每個數都是由0和1的組成來表示，而每個相鄰由0和1組成的數之間，都只會有一個位元不同，舉例來說，如果是2位元的Gray Code，那就是 [00,01,11,10]，而透過循環排列或是用反過來的順序寫，也會得到一組Gray Code, 像是 [01,11,10,00]也是一組Gray Code，但其實只是將第一個元素移到最後而已

而Gray Code與幾何之間的關係是這樣的，2位元的Gray Code的其中一集合式[00,01,11,10],而這可以對應成一個平面，如下圖所示，因此3位元的Gray Code就能夠對應成立方體，十分有趣阿XD，沿著邊界走不重複的話，每一條邊界都走過後，回到原點就剛好形成一組Gray Code，不同出發點就可以得到不同組的Gray Code欸XDDDD，超級能夠結合圖像的啦XDDD

咳咳，有點過high克制一下XD 在了解Gray Code的定義之後, 我們就來觀察如何產生n位元的Gray Code, 由上述可知，n位元的所有Gray Code,其實都是透過所產生出的第一組Gray Code之後，藉由循環排列或是反過來寫就可以得到n位元Gray Code的其他組合集合，所以主要我們必須來觀察如何產生出n位元的第一組Gray Code

以下介紹兩種觀察出來的解法(一個較為簡單，但不容易利用程式碼建構出來，一個較難觀察出來，但卻容易去用架構程式碼)

第一種解法如下圖

透過觀察可發現，由右側開始往左側來觀察，最右邊就是01 -> 10 -> 01 這樣遞迴的轉換，而右側數來第二列，就是由0011->1100->0011如此遞迴下去，依此類推，而究竟要多少開始由0轉換成1? 最右側可看見上方有個2的0次方，及表示最右側的遞迴從第2的0次方開始(也就是1)就要轉換成1，而右側數來第二列，就表示從2的1次方開始(也就是2)就要轉成1,也就是00後就要轉換成11,而後就重複11再轉換成00 如此不斷下去。

以上為第一個解法，假設要求n個bit的Gray Code, 那可以先求n-1個bit的Gray Code然後在每個元素的左邊加上0，而後再將n-1個bit的Gray Code顛倒放，然後在左邊加上1，以2個bit的Gray code為例

[0,1] //(2-1) bit的gray code
    //因此先將1 bit的gray code直式放在最右側
	0
	1
	//之後再左邊加上0
	0 0
	0 1
	//而後在顛倒順序，並在左側加上1
	0 0
    0 1
    1 1
    1 0

第二種解法

接下來這解法就是透過觀察奇偶項來得到統一的解法
由下圖我們來將轉換的位數記錄起來，由 0000 轉換成 0001是由右邊數來第1位改變，依此類推，我們將會歸納出下圖結果

可以發現奇數傳變成下一列時都是為1，表示都是最右邊那一位數從0變成1或者從1變成0，那偶數列轉變成下一列呢呢，從觀察上一列變成下一列的變化中，可發現，偶數列的位數變化，是從上一列最右邊數過來為1的位數的左邊那個位數的來轉變的，如第四列變成第五列(0010->0110)是由右邊數來第二位的左邊那位數由0變成1而產生出0110的

由上述觀察可以歸納出一個判斷奇偶列就能算出Gray Code的方式，奇數列要變成下一列就是把最右邊那一位數轉變成1或0，而偶數列就是觀察本身最右邊的1為哪一位數，那下一列肯定就是那一位數左邊的數字由0變成1或1變成0啦

以上是今天的Gray Code介紹，不知道大家比較喜歡哪一個解法呢0.0~~~