格雷码(Gray Code) C语言版

文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

Description

Gray code is an interesting code sequence and has many applications in computer science. No matter you have known it before or not, here are some introductions about its features:
(1) Gray code has 2^n unique elements;
(2) Each element contains n digits of 0 or 1;
(3) Each pair of adjacent elements has exactly one different digit.
For example, when n=2, one of the gray code sequence is: 00,01,11,10.
Now, the task is quite simple, given a positive integer n, generate the corresponding Gray code sequence.

Input

Input may contain multiple test cases. Each test case consists of one positive integer n(n<=16), Input is terminated by a case with n=0, which should not be processed.

Output

For each test case, output the corresponding Gray code sequence, one element per line. There may be multiple answers, any of them will be accepted. Please output a blank line after each test case.

Tips:注释很重要，很久以前的程序不加注释很容易看不懂...

输出N位前2^N个格雷码，因为每次只改变相邻的一个数，可以使用深度优先搜索，每次改变节点就好了。

#include <stdio.h>
#include <stdlib.h>

int n;
char s[17];

void dfs(int i)
{
    if(i==n) printf("%s\n",s); //到达底部就输出
    else
    {
        dfs(i+1); //深度优先搜索
        if(s[i]=='0') s[i]='1';
        else s[i]='0'; //把当前位逆转
        dfs(i+1); //继续向下搜索
    }
}

int main()
{
    int i;
    while(1)
    {
        scanf("%d",&n);
        if(!n) break;
        for(i=0;i<17;i++) s[i]='0';
        s[n]='\0';
        dfs(0);
        printf("\n");
    }
    system("pause");
    return 0;
}

#include <stdio.h>

#include <stdlib.h>

int n;

char s[17];

void dfs(int i)

{

if(i==n) printf("%s\n",s); //到达底部就输出

else

{

dfs(i+1); //深度优先搜索

if(s[i]=='0') s[i]='1';

else s[i]='0'; //把当前位逆转

dfs(i+1); //继续向下搜索

}

int main()

{

int i;

while(1)

{

scanf("%d",&n);

if(!n) break;

for(i=0;i<17;i++) s[i]='0';

s[n]='\0';

dfs(0);

printf("\n");

}

system("pause");

return 0;

}

转载请注明：Slyar Home » 格雷码(Gray Code) C语言 DFS版

格雷码(Gray Code) C语言 DFS版

与本文相关的文章

Hi，您需要填写昵称和邮箱！

网友最新评论 (6)