阿~~有逐漸上手jacascript的感覺啊...真是開心，今天就把Gray Code實作出來吧: 目
用Javascript征服演算法 (2-Gray Code-Javascript實作)

看完上一篇的Gray Code解法後，是不是非常躍躍欲試啊!!!!(摩拳擦掌)

首先在實作之前，我們就來分析分析我們的解法中，需要那些功能吧(方便模組化)

1. 首先來初始化n bit的array
2. 判斷為奇數列or偶數列
   2-1. 如果奇數列，就直接將最後一位數值轉變成1或0(總之就是要相反)
   2-2. 如果為偶數列,就需要由右往左找到第一個為1的位數值,然後將之左邊的位數值改成0或1

其實就是如此的簡單啊!!!!!!!!!!!!!!!!(跟上一個遞迴比XDDD)

OKOK 那就來針對逐一功能寫code吧!

首先建立了一個Gray function來當最作待會Object的建構子

function Gray(code, isOdd) {
    this.code = code;
    this.isOdd = isOdd;
	}

接下來就是初始化一下我們的init array吧

//initial array
    var my_array = new Array();
    for (i = 0; i < length; i++) {
        my_array[i] = 0;
    }
    
    var init = new Gray(my_array, 
               true);

再來判斷奇數列or偶數列,因為我們利用物件屬性，可以直接來判斷為奇或偶

	this.isOdd ? ' odd' : ' even'

最重要的2-1 2-2功能就寫在一起囉

//奇數列i就表示為最後一位元(length - 1)
    //偶數列就是最右往左邊數為1得數字的左邊那個(所以減1位數)
    //-1則是在Gray code最後一組只有最左邊的數字為1其餘為0的狀況下,lastIndexOf(1)才會為0
    var i = (this.isOdd ? this.code.length : this.code.lastIndexOf(1)) - 1;
    console.log(this.code.lastIndexOf(1));
    
    return new Gray(i === -1 ? [] : 
               this.code.slice(0, i)
                        .concat([1 - this.code[i]])
                        .concat(this.code.slice(
                            i + 1, this.code.length)), 
           !this.isOdd);

在這邊特別說明一下上面實作變換位元的部分

this.code.slice(0, i)
             .concat([1 - this.code[i]])
             .concat(this.code.slice(
             i + 1, this.code.length))

這邊用了slice跟concat就能統整出一個對於奇偶數列的統一解法，透過i的計算,第一個slice是將陣列從左邊數過來到第i個位數之前取出來,因此如果為奇數列就是最後一個位數之前的數值取出來,而後的concat就加上是1就為0,是0就為1的結果,因此奇數列在此已經解決

而在偶數列部分,因為i是需要變動的位數,因此也是將i位數值之前的值取出來,轉變0->1, 1->0後,再加上後面的位數,就完成下一列的變化: )

最後寫點recursive讓他自動去跑完所有組別吧

function successors(gray) {
        var nx = gray.next();
        //等到最後一組產生空陣列後才會將所有組別回傳
        return nx.code.length === 0 ? [] : [nx].concat(successors(nx));//稍微用到一點recursiveXD
        
    }

附上能夠執行的所有程式碼囉: )

//建構式
	function Gray(code, isOdd) {
    this.code = code;
    this.isOdd = isOdd;
	}

	Gray.prototype.toString = function() {
    return this.code + (this.isOdd ? ' odd' : ' even');
	};

	Gray.prototype.next = function() {
	    //奇數列i就表示為最後一位元(length - 1)
	    //偶數列就是最右往左邊數為1得數字的左邊那個(所以減1位數)
	    //-1則是在Gray code最後一組只有最左邊的數字為1其餘為0的狀況下,lastIndexOf(1)才會為0
	    var i = (this.isOdd ? this.code.length : this.code.lastIndexOf(1)) - 1;
	    console.log(this.code.lastIndexOf(1));
	    
	    return new Gray(i === -1 ? [] : 
	               this.code.slice(0, i)
	                        .concat([1 - this.code[i]])
	                        .concat(this.code.slice(
	                            i + 1, this.code.length)), 
	           !this.isOdd);
	};

	function gray(length) {
	    function successors(gray) {
	        var nx = gray.next();
	        //等到最後一組產生空陣列後才會將所有組別回傳
	        return nx.code.length === 0 ? [] : [nx].concat(successors(nx));//稍微用到一點recursiveXD
	        
	    }
	    //initial array
	    var my_array = new Array();
	    for (i = 0; i < length; i++) {
	        my_array[i] = 0;
	    }
	    
	    var init = new Gray(my_array, 
	               true);
	   
	    return [init].concat(successors(init));//[init]是在object外再加一層[]這樣才會變成array,因為concat需要由array來呼叫
	}

	gray(4).forEach(function(code) {
	    //alert(code);
	});

以上就是Gray Code的實作囉~大家有沒有懂阿

時間有限就只做這個解法，另外一個解法大家可以試試看練習寫javascript來解喔!!!!

附上我的Jsfiddle連結~(怕大家討厭彈跳視窗，要執行前記得把最下面的//alert()拿掉唷)

http://jsfiddle.net/stanney/Ft3yn/3/