iT邦幫忙

DAY 5
4

用Javascript征服演算法系列 第 5

用Javascript征服演算法 (2-Gray Code-Javascript實作)

  • 分享至 

  • xImage
  •  

阿~~有逐漸上手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/

開心開心開心開心開心開心開心開心


上一篇
用Javascript征服演算法 (2-Gray Code)
下一篇
用Javascript征服演算法 (5-bubble sort&實作)
系列文
用Javascript征服演算法10
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
azole
iT邦新手 5 級 ‧ 2013-09-28 12:22:18

var newcode = this.code.slice(0);
newcode[i] = 1-newcode[i];
這樣就可以做出新的array,省了兩次concat,參考一下。

我要留言

立即登入留言