Ответ 1

Python - 53 символа

n=1<<input()
for x in range(n):print bin(n+x^x/2)[3:]

Эта версия 54 char преодолевает ограничение диапазона в 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['']

Ответ 2

APL (29 символов)

С функцией F как (⌽ является "поворот" char)

z←x F y
z←(0,¨y),1,¨⌽y

Выдает серый код с 5 цифрами (⍴ теперь является "rho" char)

F/5⍴⊂0,1

Число "5" можно изменить или быть переменной.

(Извините за непечатаемые символы APL. SO не позволит мне отправлять изображения в качестве нового пользователя)

Ответ 3

Невозможный! язык (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

(на самом деле я не знаю, разрешены ли личные языки, так как Невозможно! все еще находится в разработке, но я все равно хотел его опубликовать..)

Ответ 4

Golfscript - 27 символов

Чтение из stdin, запись в stdout

~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

Ответ 5

Ruby - 49 символов

(1<<n=gets.to_i).times{|x|puts"%.#{n}b"%(x^x/2)}

Это работает для n = 100000 без проблем

Ответ 6

С++, 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;
}

Ответ 7

Haskell, 82 символа:

f a=map('0':)a++map('1':)(reverse a)
main=interact$unlines.(iterate f[""]!!).read

Бесподобный стиль для победы! (или, по крайней мере, на 4 меньше ударов). Престижность к FUZxxl.

previous: 86 символов:

f a=map('0':)a++map('1':)(reverse a)
main=interact$ \s->unlines$iterate f[""]!!read s

Вырезать два удара с помощью взаимодействия, один с unline.

старше: 89 символов:

f a=map('0':)a++map('1':)(reverse a)
main=readLn>>= \s->putStr$concat$iterate f["\n"]!!s

Обратите внимание, что лента дает вам немедленный выход бесплатно.

Ответ 8

Mathematica 50 Chars

Nest[Join["0"<>#&/@#,"1"<>#&/@[email protected]#]&,{""},#]&

Спасибо А. Рексу за предложения!

Предыдущие попытки

Вот моя попытка в Mathematica (140 символов). Я знаю, что это не кратчайший, но я думаю, что это проще всего, если вы знакомы с функциональным программированием (хотя это может быть мой язык). Функция addbit принимает n-разрядный серый код и возвращает сериальный код n + 1 бит с использованием логики со страницы wikipedia. Функция make grey code применяет функцию добавления вложенной формы к 1-битовому серому коду, {{ 0}, {1}}, пока не будет создана n-разрядная версия. Функция charactercode печатает только числа без фигурных скобок и запятых, которые находятся на выходе функции добавления.

addbit[set_] := 
 Join[Map[Prepend[#, 0] &, set], Map[Prepend[#, 1] &, Reverse[set]]]
MakeGray[n_] := 
 Map[FromCharacterCode, Nest[addbit, {{0}, {1}}, n - 1] + 48]

Ответ 9

Простая реализация Python, описанная в Построение n-разрядного кода Grey в Википедии:

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

Ответ 10

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;
}

Ответ 11

С#, 149 143 символа

С# - не лучший язык для кодового гольфа, но я думал, что все равно пойду.

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));
    }
}

Ответ 12

И вот мое жертвоприношение Фантом

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 char)

Или расширенная версия:

 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
    }
  }

Ответ 13

F #, 152 символа

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")

Ответ 14

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 # noob - я не стал его укорачивать, так как он слишком длинный в любом случае; -)

Итеративное решение: (работает с 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

Ответ 15

Lua, 156 символов

Это мой бросок на него в Луа, как можно ближе к нему.

LuaJIT (или lua с lua-bitop): 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

Ответ 16

В безрежимном прологе (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).

Ответ 17

Ruby, 50 Chars

(2**n=gets.to_i).times{|i|puts"%0#{n}d"%i.to_s(2)}