iT邦幫忙

DAY 4
3

用Javascript征服演算法系列 第 4

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

  • 分享至 

  • xImage
  •  

神奇的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~~~飛


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

1 則留言

0
azole
iT邦新手 5 級 ‧ 2013-09-29 12:15:42

試著實作第一種解法,其實不會很難架構程式,這個解法既然想法上已經是比較直接簡單了,通常做起來也就不會太難,做出來後倒是發現,效能上不夠好,會是O(n*2^n), 這還頗糟。

不曉得第二種解法的big O是多少就是了,是一定都要掃過2^n列,但每一次做的時候,只要判斷是奇偶跟最右邊的1的位置,不需掃完一整列的code,這方面光這樣想起來效率上應該就比第一種來得好很多了。

小賴真是認真~~等我寫完鐵人再來跟你討論兒~

不過我直覺也是認為第二種解法的複雜度應該較低就是了飛

我當初是覺得第一種解法要用到的更改方式相對繁瑣很多,就有點抗拒去寫它XDDD

azole iT邦新手 5 級 ‧ 2013-09-30 10:54:57 檢舉

XDD 沒辦法,喜歡跟你討論演算法

azole iT邦新手 5 級 ‧ 2013-09-30 10:55:23 檢舉

另外請教一個問題,gray code有什麼實際上的用途嗎? 謝謝。

我要留言

立即登入留言