Weź jako liczbę całkowitą dodatnią n i wyślij (niektóre z) liczby dziesiętne, które można utworzyć za pomocą n bitów, uporządkowane w następujący sposób:

Najpierw wypisz wszystkie liczby, które można utworzyć za pomocą tylko jednej 1, a pozostałe 0w reprezentacji binarnej (posortowane), a następnie wszystkie liczby, które można utworzyć za pomocą dwóch kolejnych 1 , reszty 0, a następnie trzech kolejnych 1 i tak dalej.

Zobaczmy, jak to wygląda dla n = 4 :

0001  -  1
0010  -  2
0100  -  4
1000  -  8
0011  -  3
0110  -  6
1100  -  12
0111  -  7
1110  -  14
1111  -  15

Zatem dane wyjściowe dla n = 4 to: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (opcjonalny format wyjściowy).

Przypadki testowe:

n = 1
1

n = 2
1 2 3

n = 3
1, 2, 4, 3, 6, 7

n = 8
1, 2, 4, 8, 16, 32, 64, 128, 3, 6, 12, 24, 48, 96, 192, 7, 14, 28, 56, 112, 224, 15, 30, 60, 120, 240, 31, 62, 124, 248, 63, 126, 252, 127, 254, 255

n = 17
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 7, 14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 14336, 28672, 57344, 114688, 15, 30, 60, 120, 240, 480, 960, 1920, 3840, 7680, 15360, 30720, 61440, 122880, 31, 62, 124, 248, 496, 992, 1984, 3968, 7936, 15872, 31744, 63488, 126976, 63, 126, 252, 504, 1008, 2016, 4032, 8064, 16128, 32256, 64512, 129024, 127, 254, 508, 1016, 2032, 4064, 8128, 16256, 32512, 65024, 130048, 255, 510, 1020, 2040, 4080, 8160, 16320, 32640, 65280, 130560, 511, 1022, 2044, 4088, 8176, 16352, 32704, 65408, 130816, 1023, 2046, 4092, 8184, 16368, 32736, 65472, 130944, 2047, 4094, 8188, 16376, 32752, 65504, 131008, 4095, 8190, 16380, 32760, 65520, 131040, 8191, 16382, 32764, 65528, 131056,16383, 32766, 65532, 131064, 32767, 65534, 131068, 65535, 131070, 131071

To jest golf golfowy , więc wygrywa najkrótszy kod w każdym języku !

Zachęcamy do dobrych wyjaśnień , także dla rozwiązań w „zwykłych językach”!

Python , 53 bajty

f=lambda n,i=1:n*[f]and[i]+f(n-1,2*i)+i%2*f(n-1,i-~i)

Wypróbuj online!

Funkcja rekurencyjna generuje posortowaną listę jako spacer w dół tego drzewa (przykład z n=4):

      1
     / \
    2   3
   /   / \
  4   6   7
 /   /   / \
8   12  14  15

1 2 4 8 3 6 12 7 14 15

Lewe gałęzie podwoją wartość, a prawe gałęzie i->i*2+1istnieją i istnieją tylko dla nieparzystych i. Tak więc spacer w przedsprzedaży dla osób niebędących liśćmi jest T(i)=[i]+T(i*2)+i%2*T(i*2+1).

Drzewo kończy się na głębokości n, gdzie njest wejście. Osiąga się to poprzez zmniejszanie nz każdym krokiem w dół i zatrzymywanie, gdy wynosi 0.

Alternatywną strategią byłoby kończenie na wartościach iprzekraczających 2**n, a nie śledzenie głębokości. Znalazłem to o jeden bajt dłużej:

f=lambda n,i=1:2**n/i*[f]and[i]+f(n,2*i)+i%2*f(n,i-~i)
f=lambda n,i=1:[f][i>>n:]and[i]+f(n,2*i)+i%2*f(n,i-~i)

Galaretka , 6 bajtów

Ḷ2*ẆS€

To kwalifikuje się do wyimaginowanej premii .

Wypróbuj online!

Jak to działa

Ḷ2*ẆS€  Main link. Argument: n

Ḷ       Unlength; yield [0, ..., n-1].
 2*     Yield [2**0, ..., 2**(n-1)].
   Ẇ    Sliding window; yield all subarrays of consecutive elements.
        The subarrays are sorted by length, then from left to right.
    S€  Map the sum atom over the substrings.

Mathematica, 40 bajtów

Join@@Table[2^j(2^i-1),{i,#},{j,0,#-i}]&

Każda liczba na pożądanej liście jest różnicą dwóch potęg 2, więc po prostu generujemy je w kolejności, używając, Tablea następnie spłaszczając listę. Myślę, że to zarabia wymyśloną premię Stewie Griffin :)

Mathematica, 35 bajtów

Tr/@Rest@Subsequences[2^Range@#/2]&

Port algorytmu Jelnisa ​​Jelly . Nie wiedziałem o Subsequencestym wcześniej! (Nie widziałem też, żeby mile opublikowały tę dokładną odpowiedź ... idź to zagłosować!)

JavaScript (ES6), 59 58 55 bajtów

for(q=prompt(n=1);p=q--;n-=~n)for(m=n;p--;m*=2)alert(m)

Pełny program, który pobiera dane z monitu i ostrzega kolejno o każdym numerze. To także kwalifikuje się do wyimaginowanej premii .

Testowy fragment kodu

(Uwaga: używa console.logzamiast alert)

for(q=prompt(n=1);p=q--;n-=~n)for(m=n;p--;m*=2)console.log(m)

JavaScript (ES6), 55 51 bajtów

Zwraca rozdzieloną spacjami listę liczb całkowitych.

n=>(F=k=>k>>n?--j?F(k>>j|1):'':k+' '+F(k*2))(1,j=n)

Wyobrażony bonus przyjazny.

Sformatowane i skomentowane

n => (                    // main function, takes n as input
  F = k =>                // recursive function, takes k as input
    k >> n ?              // if k is greater or equal to 1 << n:
      --j ?               //   decrement j ; if j is > 0:
        F(k >> j | 1)     //     do a recursive call with an additional bit set
      :                   //   else
        ''                //     stop recursion
    :                     // else
      k + ' ' + F(k * 2)  //   append k to output and do a recursive call with k * 2
  )(1, j = n)             // start the recursion with k = 1 and j = n

Przypadki testowe

let f =

n=>(F=k=>k>>n?--j?F(k>>j|1):'':k+' '+F(k*2))(1,j=n)

console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(8))
console.log(f(17))

Python 2 , 64 61 bajtów

^{-3 bajty dzięki Dennisowi}

n=2**input()
j=i=1
while j<n:
 print i;i*=2
 if i/n:i=j=2*j+1

Wypróbuj online!

Mathematica, 35 bajtów

Tr/@Rest@Subsequences[2^Range@#/2]&

Python 2 , 65 63 58 bajtów

lambda n:[(2<<k/n)-1<<k%n for k in range(n*n)if k/n+k%n<n]

Wypróbuj online!

Haskell , 37 bajtów

f n=[2^b-2^(b-a)|a<-[1..n],b<-[a..n]]

Wypróbuj online!

Haskell, 47 bajtów

f n=[1..n]>>= \b->take(n-b+1)$iterate(2*)$2^b-1

Przykład użycia: f 4-> [1,2,4,8,3,6,12,7,14,15]. Wypróbuj online! .

Jak to działa: dla każdego numeru bw [1..n], początek 2^b-1i wielokrotnie podwoić wartość i zabrać n-b+1elementy z tej listy.

05AB1E , 6 bajtów

L<oΎO

Wypróbuj online! lub jako pakiet testowy

Wyjaśnienie

Używa sztuczki suma podlisty, jak pokazano w odpowiedzi Jelly'ego na Jelly

L       # range [1 ... input]
 <      # decrement each
  o     # raise 2 to each power
   Π   # get all sublists
    é   # sort by length
     O  # sum

Groovy, 90 89 bajtów

{(0..<2**it).collect{0.toBinaryString(it)}.sort{it.count("1")}.collect{0.parseInt(it,2)}}

Konwersja binarna jest tak głupia.

-1 dzięki Gurupad Mamadapur

Pyth, 7 bajtów

sM.:^L2

Wypróbuj online.

Wykorzystuje algorytm Dennisa.

Narzędzia Bash + Unix, 51 bajtów

dc<<<2i`seq -f%.f $[10**$1-1]|grep ^1*0*$|sort -r`f

Wypróbuj online!

Dane wejściowe n są przekazywane w argumencie.

Użyj seq, aby wydrukować wszystkie liczby z n lub mniej cyframi. (Są to liczby podstawowe 10, więc jest tu wiele dodatkowych liczb. Jest to marnotrawstwo i czasochłonne, ale to jest golf golfowy!)

Wezwanie grep zachowuje tylko te liczby, które składają się dokładnie z 1, a następnie 0.

Następnie użyj sort -r, aby posortować je w odwrotnej kolejności leksykograficznej.

Na koniec, dc jest ustawiane na dane wejściowe podstawy 2 - wypycha posortowane liczby na stosie, a następnie drukuje stos od góry do dołu. (Spowoduje to wydrukowanie ostatniego elementu wypchniętego jako pierwszy itd., Dlatego używam sort -r zamiast sortować).

Poprawiony błąd: Pominąłem opcję -f% .f do seq, która jest wymagana dla liczb całkowitych od 1000000. (Podziękowania dla @TobySpeight za zwrócenie uwagi na problem.)

Mathematica / Mathics , 69 bajtów

{0,1}~Tuples~#~SortBy~Count@1/.n:{a=0...,1..,a}:>Print@Fold[#+##&,n]&

Wypróbuj online!

Perl 6 , 38 bajtów

->\n{map {|(2**$_-1 X+<0..n-$_)},1..n}

Jak to działa

->\n{                                }  # A lambda with argument n.
                                 1..n   # Numbers from 1 to n.
     map {                     },       # Replace each one with a list:
            2**$_-1                     #   2 to that power minus 1,
                    X+<                 #   bit-shifted to the left by each element of
                       0..n-$_          #   the range from 0 to n minus the number.
          |(                  )         #   Slip the list into the outer list.

To znaczy konstruuje takie liczby:

1 2 4 8 = (2^1)-1 bit-shifted to the left by 0 1 2 3 places
3 6 12  = (2^2)-1 bit-shifted to the left by 0 1 2   places
7 14    = (2^3)-1 bit-shifted to the left by 0 1     places
15      = (2^4)-1 bit-shifted to the left by 0       places     ← n rows
             ↑                                     ↑
             n                                     n-1

Kod:

Perl 6 , 44 bajtów

->\n{map {|(2**$_-1,* *2...^*>2**n-1)},1..n}

To było moje pierwsze podejście, zanim pomyślałem o (właściwie prostszym) rozwiązaniu z przesunięciem bitów powyżej.

Jak to działa

->\n{                                      }  # A lambda with argument n.
                                       1..n   # Numbers from 1 to n.
     map {                           }        # Replace each one with:
            2**$_-1                              # 2 to that power minus 1,
                   ,* *2                         # followed by the result of doubling it,
                        ...^                     # repeated until (but not including)
                            *>2**n-1             # it's larger than 2^n-1.
          |(                        )            # Slip the list into the outer list.

To znaczy konstruuje takie liczby:

1 2 4 8 = (2^1)-1, times 2, times 2, times 2
3 6 12  = (2^2)-1, times 2, times 2
7 14    = (2^3)-1, times 2
15      = (2^4)-1                                ← n rows
             ↑                       ↑
             n                       as many columns as possible in
                                     each row without exceeding (2^n)-1

Haskell 59 46 bajtów

Zacząłem od f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]

z powyższej odpowiedzi nich uzyskał wgląd, który sum.map(2^)$[0..x]można skondensować2^x-1

Kończąc z

e n=[1..n]>>= \x->map(\y->2^y*(2^x-1))[0..n-x]

[1..n] - lista z liczbą kolejnych bitów, przez które chcemy przechodzić`

>> = - przetłumaczone do końca dla każdego elementu na liście po lewej stronie, przekazujemy go do funkcji po prawej i łączymy wszystkie wyniki

\ x -> - deklaracja funkcji lambda z jednym argumentem

map xy - stosuje funkcję x do wszystkich członków listy y

W naszym przypadku x = (\ y-> 2 ^ y * (2 ^ x-1)) - kolejna funkcja lambda 2 ^ y * (2 ^ x-1)). Ta formuła wynika z mnożenia przez dwa dodawanie zera do binarnego (przykład 0001 do 0010). 2 ^ x - 1 to liczba bitów, z którymi pracujemy. więc dla 11 mamy 2 ^ 0 * 3 (tj. wcale nie przesuwaj) == 0011, następnie 2 ^ 1 * 3 = 0110, a następnie 2 ^ 2 * 3 - 1100.

[0..nx] Buduje listę, ile razy możemy przesunąć bity. Jeśli pracujemy z jednym 1, to patrząc na 0001, chcemy przesunąć 3 razy (4-1). Jeśli pracujemy dwa 11, chcemy 4-2 i tak dalej.

Python 3, 59 bajtów

Uwaga: zostało to zrobione niezależnie od rozwiązań ovsa i Dennisa , mimo że jest bardzo podobne do obu.

lambda n:[(2<<i)-1<<j for i in range(n)for j in range(n-i)]

Jak to działa:

for i in range(n)for j in range(n-i)  # Iterate over number of ones, then number of places
                                      # shifted over. i = ones, j = shifts

(2<<i)                                # Create a one followed by i zeroes
      -1                              # Subtract one from above to get i ones.
        <<j                           # Shift j places.

Wypróbuj online!

Wskazówki (zarówno kodowania, jak i gotówki) są zawsze mile widziane!

Japt , 11 bajtów

o@o!²ãXÄ mx

Przetestuj online!

Wyjaśnienie

To w zasadzie wykorzystuje podejście @ Dennisa:

o@ o!²  ãXÄ  mx
oX{o!p2 ãX+1 mx}
                  // Implicit: U = input integer
oX{            }  // Create the range [0...U) and map each item X by this function:
   o              //   Create the range [0...U)
    !p2           //     and map each item Z to 2.p(Z); that is, 2**Z.
                  //     (p2 would map each item Z to Z.p(2); ! reverses the arguments.)
        ãX+1      //   Get all overlapping slices of length X + 1.
             mx   //   Map each of these slices Z through Z.x(); that is, sum each slice.
                  // Implicit: output result of last expression

Python , 61 59 bajtów

lambda n:[2**-~i-1<<j for i in range(n)for j in range(n-i)]

Wypróbuj online!

PHP, 59 56 53 bajtów

for(;$p>($k*=2)?:($p=1<<$argn)>$k=$i+=$i+1;)echo$k,_;

pobiera dane wejściowe ze STDIN; biegać z -R.

awaria

for(;$p>($k*=2)         // 3. inner loop: shift-0 $k while $k<$p (false in first iteration)
    ?:
    ($p=1<<$argvn)      // 1. init $p=2^N, outer loop:
    >$k=$i+=$i+1        // 2. shift-1 $i while $i<$p, init $k to new $i
;)
    echo$k,_;           // 4. print $k

J , 19 bajtów

(0-.~&,>:+/\2&^)@i.

Używa tej samej metody w rozwiązaniu @Dennis .

Wypróbuj online!

Wyjaśnienie

(0-.~&,>:+/\2&^)@i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
(              )@    Operate on that range
            2&^        Compute 2^x for each x in that range
       >:              Increment each in that range
           \           For each overlapping sublist of size (previous) in powers of 2
         +/              Reduce by addition
 0                     The constant 0
     &,                Flatten each
  -.~                  Remove zeroes

Python 3, 91 bajtów

a=int(input())
print(*[int('1'*-~b,2)<<c for b in range(a)for c in range(a-b)],sep=', ')

Pełny program, z wyjściem oddzielonym przecinkami i spacjami, jak określono.

Wyjaśnienie:

Notacja gwiazdowa rozpakowuje listy. Więc print(*[1,2,3])to samo co print(1,2,3). Przekaż int()konstruktorowi ciąg kolejnych „1”.

-~bocenia na b+1, ale nie musisz otaczać go nawiasami podczas mnożenia łańcucha.

Przesunięcie bitowe wyprodukowanej liczby całkowitej rośnie coraz częściej. print()ma opcjonalny argument sep, określający ciąg znaków, który należy wstawić między każdy element na rozpakowanej liście.

Java 7, 108 bajtów

static void x(int i){int a=0,t=1<<i,b;while((a=(a<<1)+1)<t){b=a;do System.out.println(b);while((b<<=1)<t);}}

Podwaja wartość początkową, o ile wynik jest mniejszy niż 2^n. Następnie aktualizuje wartość początkową (initial_value * 2) + 1i zaczyna od tego momentu, aż w końcu osiągnie (2^n)-1.

np. dla n=4:

0001 -> init
0010
0100
1000
return, double init and add one
0011 -> init
0110
1100
return, double init and add one
0111 -> init
1110
return, double init and add one
1111 -> init
done

Wypróbuj online!

Rubinowy, 50 bajtów

->r{1.upto(r){|x|p a=2**x-1;p a while(a*=2)<2**r}}

Próbowałem kilku „sprytnych” podejść, ale wydaje się to być najkrótsze (dosłownie postępuj zgodnie z instrukcjami)

Wyjaśnienie:

Każda iteracja rozpoczyna się od 2 ^ n-1 i mnoży przez 2, aż do osiągnięcia górnego limitu. Nic szczególnego, tylko podstawowa matematyka.

QBIC , 37 bajtów - wymyślony bonus = wciąż 37 bajtów ...

:[a|e=2^b-1┘while e<2^a┘?e┘e=e*2┘wend

Szkoda, że ​​nie while-wendwbudowałem jeszcze QBIC ... Objaśnienie:

:       Get N from the command line
[a|     For b = 1 to N; The sequence is reset N times
e=2^b-1 Set the first number of this sub-sequence (yields 1, 3, 7, 15 ...)
┘       Line-break - syntactic separation of commands because there's no command for WHILE yet.
while   Pure QBasic code - lower-case is not (really) interpreted by QBIC
e<2^a   Continue as long as we don't exceed the maximum value
┘?e     Print the number in the sequence
┘e=e*2  Double the number
┘wend   And loop as long as we're not exceeding maximum, reset the sequence otherwise.
        FOR loop auto-closed by QBIC

EDYCJA: QBIC obsługuje teraz WHILE:

:[a|e=2^b-1≈e<2^a|?e┘e=e*2

To tylko 26 bajtów! Oto WHILE:

≈e<2^a|          ≈ = WHILE, and the TRUE condition is everything up to the |
       ...       Loop code goes here
          ]      Close construct: adds a WEND instruction
                 In the program above, this is done implicitly because of EOF.

MATL, 19 18 bajtów

1 bajt zapisany dzięki @Luis

:q2w^XJfP"J@YC2&sv

Wypróbuj online

R , 69 48 46 bajtów

n=scan();for(i in 1:n)print((2^i-1)*2^(i:n-i))

Każda liczba dziesiętna odpowiadająca liczbie i in 1..nw systemie binarnym jest mnożona przez 2^(0..n-i), tj. Pierwsze n-i+1potęgi dwóch (1, 2, 4, ...).

Wypróbuj online!

Stax , 9 bajtów

übg▓}╥é►╪

Uruchom i debuguj online!

Wyjaśnienie

Wyimaginowany bonus, jeśli ktoś zrobi to bez jakiejkolwiek formy konwersji podstawowej (używając zwykłych starych matematyki).

Cóż, tutaj nie ma konwersji podstawowej.

Używa do rozpakowania wersji (10 bajtów).

m|2vx_-DQH
m             For input=`n`, loop over `1..n`
 |2v          Power of two minus one
    x_-D      Do `n-j` times, where `j` is the current 1-based loop index
        Q     Output the current value
         H    And double it

Partia, 92-0 = 92 bajty

@for /l %%i in (1,1,%1)do @for /l %%j in (%%i,1,%1)do @cmd/cset/a"(1<<%%i)-1<<%%j-%%i"&echo(

Odejmowanie 0 za wymyślony bonus @ StewieGriffin.