簡介
Gray Code，是幾十年前貝爾實(shí)驗(yàn)室的科學(xué)家Frank Gray提出的一種編碼方案，當(dāng)時(shí)主要用于傳輸信號(hào)以防止出錯(cuò)。Gray Code 除了在通信，硬件設(shè)計(jì)領(lǐng)域中應(yīng)用以外，在計(jì)算機(jī)相關(guān)科學(xué)的其他方面也有廣泛的應(yīng)用，例如按序產(chǎn)生集合的所有子集。
Gray Code實(shí)現(xiàn)按序產(chǎn)生集合的所有子集
子集的按序產(chǎn)生，這個(gè)概念很簡單，舉個(gè)例子，假設(shè)我們的集合為{a,b,c}，那么按序產(chǎn)生的子集應(yīng)該是：
空集 （000） —— 0（編號(hào) 從0開始按順序排序）
a （100） —— 1
ab （110） —— 2
abc （111） —— 3
ac
b
bc
c
那么Gray Code是如何產(chǎn)生這樣的序列的呢？
Gray Code的思想非常的巧妙，我們可以將所產(chǎn)生的子集編號(hào)（范圍為0～2^n-1），第一個(gè)子集為空集（編號(hào)為0，是偶數(shù)）。在其后的每個(gè)子集由前一個(gè)子集來決定，如果前一個(gè)子集編號(hào)為偶數(shù)，那么則改變前一個(gè)子集的第一位（從左邊數(shù)）的二進(jìn)制值（0變成1或者1變成0）作為新的子集。如果前一個(gè)子集的編號(hào)為奇數(shù)，那么就將前一個(gè)子集二進(jìn)制左邊數(shù)第一個(gè)1后面的那位改變其值（0變成1或者1變成0）作為新的子集。
根據(jù)上面的Gray Code的思想，還是以集合{a,b,c}為例，第一個(gè)子集（000）的編號(hào)為0（偶數(shù)），推算出第二個(gè)子集是第一個(gè)子集改變左邊數(shù)的第一位的數(shù)值所產(chǎn)生，為100，也就是a（只取為1的字符，a為最左邊的字符對(duì)應(yīng)100中的1）。那么根據(jù)第二個(gè)子集的編號(hào)1（奇數(shù)），推算出第三個(gè)子集是由第二個(gè)子集改變從左數(shù)第一個(gè)1后面那一位的值所產(chǎn)生（100->110），那么110對(duì)應(yīng)的是ab。后面的子集都以此類推即可全部按順序產(chǎn)生。
Gray Code非遞歸的C語言實(shí)現(xiàn)
以下代碼在VS2008下調(diào)試通過
- int sum(int n)
- {
- if(1<=n) return n+sum(n-1);
- else return 0;
- }
-
- void gray(char *ptr)
- {
- int len=strlen(ptr);
- int num=(1<<len);
- // printf("num=%d \n",num);
- int i,j,k;
- int mod,tmp,mask,tmp1,tmp2;
- mask=1<<len-1;
- // printf("mask=%d \n",mask);
- mod=0;//(1<<len)-1;
- for(i=0;i<num-1;i++)
- {
- if(i%2==0)
- {
- tmp=mod&mask;
- // printf("tmp=%d ",tmp);
- if(0!=tmp) {mod=mod&(~mask);}
- else {mod=mod|(mask);}
- }
- else
- {
- tmp1=1<<(len-1);
- for(j=0;j<len;j++)
- {
- // printf(" in else");
- if(mod&tmp1) break;
- tmp1=tmp1>>1;
- // printf("tmp1=%d ",tmp1);
- }
- tmp1=tmp1>>1;
- // printf(">>1 tmp1=%d ",tmp1);
- if(tmp1!=0)
- {
- tmp=mod&tmp1;
- if(0!=tmp) {mod=mod&(~tmp1);}
- else {mod=mod|(tmp1);}
- }
- }
- tmp2=1<<len-1;
- for(k=0;k<len;k++)
- {
- if(mod&tmp2) printf("%c",ptr[k]);
- tmp2=tmp2>>1;
- }
- printf("\n");
- }
- }
-
- int main()
- {
- // printf(" result=%d ",sum(4));
- char *p="abcd";
- gray(p);
- system("pause");
- }