{"id":518,"date":"2008-12-30T20:13:04","date_gmt":"2008-12-30T12:13:04","guid":{"rendered":"http:\/\/www.slyar.com\/blog\/?p=518"},"modified":"2014-04-22T14:02:40","modified_gmt":"2014-04-22T06:02:40","slug":"gray-code-dfs","status":"publish","type":"post","link":"http:\/\/www.slyar.com\/blog\/gray-code-dfs.html","title":{"rendered":"\u683c\u96f7\u7801(Gray Code) C\u8bed\u8a00 DFS\u7248"},"content":{"rendered":"

\u6587\u7ae0\u4f5c\u8005\uff1a\u59dc\u5357(Slyar) <\/span>\u6587\u7ae0\u6765\u6e90\uff1aSlyar Home (www.slyar.com<\/a>) \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff0c\u8c22\u8c22\u5408\u4f5c\u3002<\/p>\n

Description<\/span><\/p>\n

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:
\n(1) Gray code has 2^n unique elements;
\n(2) Each element contains n digits of 0 or 1;
\n(3) Each pair of adjacent elements has exactly one different digit.
\nFor example, when n=2, one of the gray code sequence is: 00,01,11,10.
\nNow, the task is quite simple, given a positive integer n, generate the corresponding Gray code sequence.<\/p>\n

Input<\/span><\/p>\n

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.<\/p>\n

Output<\/span><\/p>\n

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.<\/p>\n

Tips:\u6ce8\u91ca\u5f88\u91cd\u8981\uff0c\u5f88\u4e45\u4ee5\u524d\u7684\u7a0b\u5e8f\u4e0d\u52a0\u6ce8\u91ca\u5f88\u5bb9\u6613\u770b\u4e0d\u61c2...<\/span><\/p>\n

\u8f93\u51faN\u4f4d\u524d2^N\u4e2a\u683c\u96f7\u7801\uff0c\u56e0\u4e3a\u6bcf\u6b21\u53ea\u6539\u53d8\u76f8\u90bb\u7684\u4e00\u4e2a\u6570\uff0c\u53ef\u4ee5\u4f7f\u7528\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\uff0c\u6bcf\u6b21\u6539\u53d8\u8282\u70b9\u5c31\u597d\u4e86\u3002<\/span><\/p>\n

\r\n#include \r\n#include \r\n\r\nint n;\r\nchar s[17];\r\n\r\nvoid dfs(int i)\r\n{\r\n    if(i==n) printf(\"%s\\n\",s); \/\/\u5230\u8fbe\u5e95\u90e8\u5c31\u8f93\u51fa\r\n    else\r\n    {\r\n        dfs(i+1); \/\/\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\r\n        if(s[i]=='0') s[i]='1';\r\n        else s[i]='0'; \/\/\u628a\u5f53\u524d\u4f4d\u9006\u8f6c\r\n        dfs(i+1); \/\/\u7ee7\u7eed\u5411\u4e0b\u641c\u7d22\r\n    }\r\n}\r\n\r\nint main()\r\n{\r\n    int i;\r\n    while(1)\r\n    {\r\n        scanf(\"%d\",&n);\r\n        if(!n) break;\r\n        for(i=0;i<17;i++) s[i]='0';\r\n        s[n]='\\0';\r\n        dfs(0);\r\n        printf(\"\\n\");\r\n    }\r\n    system(\"pause\");\r\n    return 0;\r\n}\r\n<\/pre>\n
\u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff1aSlyar Home<\/a> » \u683c\u96f7\u7801(Gray Code) C\u8bed\u8a00 DFS\u7248<\/a><\/p>","protected":false},"excerpt":{"rendered":"
\u6587\u7ae0\u4f5c\u8005\uff1a\u59dc\u5357(Slyar) \u6587\u7ae0\u6765\u6e90\uff1aSlyar Home (www.slyar.com) \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff0c\u8c22\u8c22\u5408\u4f5c\u3002 Description Gray code is an interesting code sequence and has many […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17],"tags":[304,258],"class_list":["post-518","post","type-post","status-publish","format-standard","hentry","category-programing","tag-304","tag-258"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t