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 0
w 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”!
code-golf
sorting
base-conversion
binary
Stewie Griffin
źródło
źródło
Odpowiedzi:
Python , 53 bajty
Wypróbuj online!
Funkcja rekurencyjna generuje posortowaną listę jako spacer w dół tego drzewa (przykład z
n=4
):Lewe gałęzie podwoją wartość, a prawe gałęzie
i->i*2+1
istnieją i istnieją tylko dla nieparzystychi
. Tak więc spacer w przedsprzedaży dla osób niebędących liśćmi jestT(i)=[i]+T(i*2)+i%2*T(i*2+1)
.Drzewo kończy się na głębokości
n
, gdzien
jest wejście. Osiąga się to poprzez zmniejszanien
z każdym krokiem w dół i zatrzymywanie, gdy wynosi 0.Alternatywną strategią byłoby kończenie na wartościach
i
przekraczających2**n
, a nie śledzenie głębokości. Znalazłem to o jeden bajt dłużej:źródło
[f]
zabawny dotyk, nie mogę powiedzieć, że widziałem to wcześniej.Galaretka , 6 bajtów
To kwalifikuje się do wyimaginowanej premii .
Wypróbuj online!
Jak to działa
źródło
Ẇ
jest idealnym rozwiązaniem dla tego wyzwania i jest zaimplementowany w taki sposób, aby wyniki były w odpowiedniej kolejności dla tego wyzwania. Dobra robota :-)Mathematica, 40 bajtów
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,
Table
a następnie spłaszczając listę. Myślę, że to zarabia wymyśloną premię Stewie Griffin :)Mathematica, 35 bajtów
Port algorytmu Jelnisa Jelly . Nie wiedziałem o
Subsequences
tym wcześniej! (Nie widziałem też, żeby mile opublikowały tę dokładną odpowiedź ... idź to zagłosować!)źródło
JavaScript (ES6),
595855 bajtówPeł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.log
zamiastalert
)Pokaż fragment kodu
źródło
JavaScript (ES6),
5551 bajtówZwraca rozdzieloną spacjami listę liczb całkowitych.
Wyobrażony bonus przyjazny.
Sformatowane i skomentowane
Przypadki testowe
Pokaż fragment kodu
źródło
Python 2 ,
6461 bajtów-3 bajty dzięki Dennisowi
Wypróbuj online!
źródło
Mathematica, 35 bajtów
źródło
Python 2 ,
656358 bajtówWypróbuj online!
źródło
(2<<i)-1<<j
... a ty już to rozgryzłeś. Dobra robota! Dobra robota w pozbyciu się podwójnych zakresówHaskell , 37 bajtów
Wypróbuj online!
źródło
Haskell, 47 bajtów
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
b
w[1..n]
, początek2^b-1
i wielokrotnie podwoić wartość i zabraćn-b+1
elementy z tej listy.źródło
05AB1E , 6 bajtów
Wypróbuj online! lub jako pakiet testowy
Wyjaśnienie
Używa sztuczki suma podlisty, jak pokazano w odpowiedzi Jelly'ego na Jelly
źródło
Groovy,
9089 bajtówKonwersja binarna jest tak głupia.
-1 dzięki Gurupad Mamadapur
źródło
{(1..<2**it)...
zapisuje bajt.Pyth, 7 bajtów
Wypróbuj online.
Wykorzystuje algorytm Dennisa.
źródło
Narzędzia Bash + Unix, 51 bajtów
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.)
źródło
dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -
zgłasza tylko 12 wartości. Myślę, żegrep ^1[01]*$
zamiast tego chcesz .Mathematica / Mathics , 69 bajtów
Wypróbuj online!
źródło
Perl 6 , 38 bajtów
Jak to działa
To znaczy konstruuje takie liczby:
Kod:
Perl 6 , 44 bajtów
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
To znaczy konstruuje takie liczby:
źródło
Haskell
5946 bajtówZaczął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.
źródło
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.
Jak to działa:
Wypróbuj online!
Wskazówki (zarówno kodowania, jak i gotówki) są zawsze mile widziane!
źródło
Japt , 11 bajtów
Przetestuj online!
Wyjaśnienie
To w zasadzie wykorzystuje podejście @ Dennisa:
źródło
Python ,
6159 bajtówWypróbuj online!
źródło
PHP,
59 5653 bajtówpobiera dane wejściowe ze STDIN; biegać z
-R
.awaria
źródło
$argn
Bardzo dobry pomysł. Po przeczytaniu pytania mam w głowie rozwiązanie z ponad 200J , 19 bajtów
Używa tej samej metody w rozwiązaniu @Dennis .
Wypróbuj online!
Wyjaśnienie
źródło
Python 3, 91 bajtów
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 coprint(1,2,3)
. Przekażint()
konstruktorowi ciąg kolejnych „1”.-~b
ocenia nab+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.źródło
Java 7, 108 bajtów
Podwaja wartość początkową, o ile wynik jest mniejszy niż
2^n
. Następnie aktualizuje wartość początkową(initial_value * 2) + 1
i zaczyna od tego momentu, aż w końcu osiągnie(2^n)-1
.np. dla
n=4
:Wypróbuj online!
źródło
Rubinowy, 50 bajtów
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.
źródło
QBIC , 37 bajtów - wymyślony bonus = wciąż 37 bajtów ...
Szkoda, że nie
while-wend
wbudowałem jeszcze QBIC ... Objaśnienie:EDYCJA: QBIC obsługuje teraz
WHILE
:To tylko 26 bajtów! Oto
WHILE
:źródło
MATL,
1918 bajtów1 bajt zapisany dzięki @Luis
Wypróbuj online
źródło
R ,
694846 bajtówKażda liczba dziesiętna odpowiadająca liczbie
i in 1..n
w systemie binarnym jest mnożona przez2^(0..n-i)
, tj. Pierwszen-i+1
potęgi dwóch (1, 2, 4, ...).Wypróbuj online!
źródło
Stax , 9 bajtów
Uruchom i debuguj online!
Wyjaśnienie
Cóż, tutaj nie ma konwersji podstawowej.
Używa do rozpakowania wersji (10 bajtów).
źródło
Partia, 92-0 = 92 bajty
Odejmowanie 0 za wymyślony bonus @ StewieGriffin.
źródło