挑战
按字符数计算的最短程序，输出 n 位格雷码。n将是一个小于（由于用户建议）从标准输入中获取的任意数字。格雷码将打印在标准输出中，如示例中所示。1000100000
注意：我不希望程序在合理的时间内打印格雷码（n=100000有点矫枉过正）；我确实希望它开始打印。
例子
输入：
4
预期输出：
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
问问题
7720 次
17 回答
23
Python - 53 个字符
n=1<<input()
for x in range(n):print bin(n+x^x/2)[3:]
这个 54 字符版本克服了 Python2 中范围的限制，所以 n=100000 可以工作！
x,n=0,1<<input()
while n>x:print bin(n+x^x/2)[3:];x+=1
69 个字符
G=lambda n:n and[x+y for x in'01'for y in G(n-1)[::1-2*int(x)]]or['']
75 个字符
G=lambda n:n and['0'+x for x in G(n-1)]+['1'+x for x in G(n-1)[::-1]]or['']
于 2010-11-07T21:10:23.190 回答
17
于 2010-11-08T00:13:57.377 回答
14
不可能的！语言（54 58个字符）
#l{'0,'1}1[;@l<][%;~['1%+].>.%['0%+].>.+//%1+]<>%[^].>
测试运行：
./impossible gray.i! 5
Impossible v0.1.28
00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000
（实际上我不知道是否允许使用个人语言，因为Impossible!仍在开发中，但我还是想发布它..）
于 2010-11-07T22:07:56.090 回答
14
Golfscript - 27 个字符
从标准输入读取，写入标准输出
~2\?:),{.2/^)+2base''*1>n}%
样品运行
$ echo 4 | ruby golfscript.rb gray.gs
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
于 2010-11-08T01:42:52.827 回答
12
红宝石 - 49 个字符
(1<<n=gets.to_i).times{|x|puts"%.#{n}b"%(x^x/2)}
这适用于 n=100000 没有问题
于 2010-11-08T02:08:20.770 回答
7
C++，168 个字符，不包括空格：
#include <iostream>
#include <string>
int r;
void x(std::string p, char f=48)
{
if(!r--)std::cout<<p<<'\n';else
{x(p+f);x(p+char(f^1),49);}
r++;
}
int main() {
std::cin>>r;
x("");
return 0;
}
于 2010-11-08T19:31:43.707 回答
6
Haskell，82 个字符：
f a=map('0':)a++map('1':)(reverse a)
main=interact$unlines.(iterate f[""]!!).read
无积分风格，赢得胜利！（或至少少 4 次）。向 FUZxxl 致敬。
上一个：86 个字符：
f a=map('0':)a++map('1':)(reverse a)
main=interact$ \s->unlines$iterate f[""]!!read s
用interact 剪出两笔，一笔用unlines。
较旧：89 个字符：
f a=map('0':)a++map('1':)(reverse a)
main=readLn>>= \s->putStr$concat$iterate f["\n"]!!s
请注意，懒惰让您免费获得即时输出。
于 2010-11-08T18:22:32.333 回答
5
Mathematica 50 Chars
Nest[Join["0"<>#&/@#,"1"<>#&/@Reverse@#]&,{""},#]&
Thanks to A. Rex for suggestions!
Previous attempts
Here is my attempt in Mathematica (140 characters). I know that it isn't the shortest, but I think it is the easiest to follow if you are familiar with functional programming (though that could be my language bias showing). The addbit function takes an n-bit gray code and returns an n+1 bit gray code using the logic from the wikipedia page.. The make gray code function applies the addbit function in a nested manner to a 1 bit gray code, {{0}, {1}}, until an n-bit version is created. The charactercode function prints just the numbers without the braces and commas that are in the output of the addbit function.
addbit[set_] :=
Join[Map[Prepend[#, 0] &, set], Map[Prepend[#, 1] &, Reverse[set]]]
MakeGray[n_] :=
Map[FromCharacterCode, Nest[addbit, {{0}, {1}}, n - 1] + 48]
于 2010-11-08T00:16:11.030 回答
4
在 Wikipedia 上Constructing an n- bit Gray code中描述的简单 Python 实现：
import sys
def _gray(n):
if n == 1:
return [0, 1]
else:
p = _gray(n-1)
pr = [x + (1<<(n-1)) for x in p[::-1]]
return p + pr
n = int(sys.argv[1])
for i in [("0"*n + bin(a)[2:])[-n:] for a in _gray(n)]:
print i
（233 个字符）
测试：
$ python gray.py 4
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
于 2010-11-07T21:04:20.237 回答
4
C、203 个字符
这是一个牺牲品，在 C 中：
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
char s[256];
int b, i, j, m, g;
gets(s);
b = atoi(s);
for (i = 0; i < 1 << b; ++i)
{
g = i ^ (i / 2);
m = 1 << (b - 1);
for (j = 0; j < b; ++j)
{
s[j] = (g & m) ? '1' : '0';
m >>= 1;
}
s[j] = '\0';
puts(s);
}
return 0;
}
于 2010-11-07T21:04:55.543 回答
3
C#，149 143 个字符
C# 不是代码高尔夫的最佳语言，但我想我还是会去做。
static void Main(){var s=1L<<int.Parse(Console.ReadLine());for(long i=0;i<s;i++){Console.WriteLine(Convert.ToString(s+i^i/2,2).Substring(1));}}
可读版本：
static void Main()
{
var s = 1L << int.Parse(Console.ReadLine());
for (long i = 0; i < s; i++)
{
Console.WriteLine(Convert.ToString(s + i ^ i / 2, 2).Substring(1));
}
}
于 2010-11-08T20:28:05.193 回答
2
这是我的 Fantom 祭品
public static Str[]grayCode(Int i){if(i==1)return["0","1"];else{p:=grayCode(i-1);p.addAll(p.dup.reverse);p.each|s,c|{if(c<(p.size/2))p[c]="0"+s;else p[c]="1"+s;};return p}}
（177 个字符）
或扩展版本：
public static Str[] grayCode(Int i)
{
if (i==1) return ["0","1"]
else{
p := grayCode(i-1);
p.addAll(p.dup.reverse);
p.each |s,c|
{
if(c<(p.size/2))
{
p[c] = "0" + s
}
else
{
p[c] = "1" + s
}
}
return p
}
}
于 2010-11-07T22:45:32.927 回答
2
F#, 152 characters
let m=List.map;;let rec g l=function|1->l|x->g((m((+)"0")l)@(l|>List.rev|>m((+)"1")))(x - 1);;stdin.ReadLine()|>int|>g["0";"1"]|>List.iter(printfn "%s")
于 2010-11-08T00:15:05.040 回答
2
F# 180 175字符太多
今天早上我做了另一个版本，简化了递归版本，但是由于递归，它不会做 100000。
递归解决方案：
let rec g m n l =
if(m = n) then l
else List.map ((+)"0") l @ List.map ((+)"1") (List.rev(l)) |> g (m+1) n
List.iter (fun x -> printfn "%s" x) (g 1 (int(stdin.ReadLine())) ["0";"1"]);;
完成后，我为“100000”要求创建了一个工作版本 - 与此处显示的其他解决方案竞争太长了，我可能多次重新发明轮子，但与我在这里看到的许多解决方案不同可以使用非常非常多的位，嘿，对于 F# 菜鸟来说，这是一个很好的学习体验——我没有费心去缩短它，因为它无论如何都太长了 ;-)
迭代解决方案：（使用 100000+）
let bits = stdin.ReadLine() |>int
let n = 1I <<< bits
let bitcount (n : bigint) =
let mutable m = n
let mutable c = 1
while m > 1I do
m <- m >>>1
c<-c+1
c
let rec traverseBits m (number: bigint) =
let highbit = bigint(1 <<< m)
if m > bitcount number
then number
else
let lowbit = 1 <<< m-1
if (highbit&&& number) > 0I
then
let newnum = number ^^^ bigint(lowbit)
traverseBits (m+1) newnum
else traverseBits (m+1) number
let res = seq
{
for i in 0I..n do
yield traverseBits 1 i
}
let binary n m = seq
{
for i = m-1 downto 0 do
let bit = bigint(1 <<< i)
if bit &&&n > 0I
then yield "1"
else yield "0"
}
Seq.iter (fun x -> printfn "%s" (Seq.reduce (+) (binary x bits))) res
于 2010-11-08T00:22:17.367 回答
0
Lua，156 个字符
这是我在 Lua 中的尝试，尽我所能。
LuaJIT（或带有 lua-bitop 的 lua）：156 字节
a=io.read()n,w,b=2^a,io.write,bit;for x=0,n-1 do t=b.bxor(n+x,b.rshift(x,1))for k=a-1,0,-1 do w(t%2^k==t%n and 0 or 1)t=t%2^k==t and t or t%2^k end w'\n'end
Lua 5.2：154 字节
a=io.read()n,w,b=2^a,io.write,bit32;for x=0,n-1 do t=b.XOR(n+x,b.SHR(x,1))for k=a-1,0,-1 do w(t%2^k==t%n and 0 or 1)t=t%2^k==t and t or t%2^k end w'\n'end
于 2010-11-19T17:48:55.343 回答
0
在无剪切的 Prolog 中（如果删除 '<<' 之后的空格，则为 138 个字节；提交编辑器会截断没有它的最后一行）：
b(N,D):-D=0->nl;Q is D-1,H is N>>Q/\1,write(H),b(N,Q).
c(N,D):-N=0;P is N xor(N//2),b(P,D),M is N-1,c(M,D).
:-read(N),X is 1<< N-1,c(X,N).
于 2010-11-30T11:47:07.500 回答
-1
红宝石，50 个字符
(2**n=gets.to_i).times{|i|puts"%0#{n}d"%i.to_s(2)}
于 2011-01-18T21:07:34.740 回答