Nehmen Sie eine positive Ganzzahl n als Eingabe und geben Sie (einige der) Dezimalzahlen aus, die mit n Bits in der folgenden Reihenfolge erstellt werden können:
Listen Sie zuerst alle Nummern auf, die mit nur einer erstellt werden können 1
, und den Rest 0
in der Binärdarstellung (sortiert), dann alle Nummern, die mit zwei aufeinanderfolgenden 1
, den Rest 0
, dann drei aufeinanderfolgenden 1
usw. erstellt werden können.
Mal sehen, wie das für n = 4 aussieht :
0001 - 1
0010 - 2
0100 - 4
1000 - 8
0011 - 3
0110 - 6
1100 - 12
0111 - 7
1110 - 14
1111 - 15
Die Ausgabe für n = 4 ist also: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (optionales Ausgabeformat).
Testfälle:
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
Das ist Code-Golf , also gewinnt der kürzeste Code in jeder Sprache !
Gute Erklärungen sind sehr erwünscht , auch für Lösungen in "regulären Sprachen"!
code-golf
sorting
base-conversion
binary
Stewie Griffin
quelle
quelle
Antworten:
Python , 53 Bytes
Probieren Sie es online!
Die rekursive Funktion generiert die sortierte Liste als Vorbestellung in diesem Baum (Beispiel mit
n=4
):Linke Zweige verdoppeln den Wert und rechte Zweige
i->i*2+1
existieren nur für ungeradei
. Der Vorbestellungsspaziergang für Nicht-Blätter ist alsoT(i)=[i]+T(i*2)+i%2*T(i*2+1)
.Der Baum endet in der Tiefe
n
, won
die Eingabe ist. Dies wird erreicht, indemn
mit jedem Abwärtsschritt verringert und angehalten wird, wenn es 0 ist.Eine alternative Strategie besteht darin, bei Werten zu enden,
i
die die2**n
Tiefe überschreiten , anstatt sie zu verfolgen. Ich fand das ein Byte länger:quelle
[f]
ist eine amüsante Geste, ich kann nicht sagen, dass ich das schon mal gesehen habe.Gelee , 6 Bytes
Dies qualifiziert sich für den imaginären Bonus .
Probieren Sie es online!
Wie es funktioniert
quelle
Ẇ
ist ein idealer Baustein für diese Herausforderung und wird so implementiert, dass die Ergebnisse genau in der richtigen Reihenfolge für diese Herausforderung sind. Gut gemacht :-)Mathematica, 40 Bytes
Jede Zahl in der gewünschten Liste ist der Unterschied zwischen zwei Zweierpotenzen, daher generieren wir sie einfach in der Reihenfolge, in der
Table
die Liste verwendet und dann abgeflacht wird. Ich denke, das bringt Stewie Griffins imaginären Bonus :)Mathematica, 35 Bytes
Ein Port von Dennis 'Jelly-Algorithmus . Ich wusste es
Subsequences
vorher nicht! (Ich habe auch nicht gesehen, dass Miles genau diese Antwort gepostet hat ... stimmt dem zu!)quelle
JavaScript (ES6),
595855 ByteEin vollständiges Programm, das Eingaben über eine Eingabeaufforderung vornimmt und jede Nummer nacheinander benachrichtigt. Dies gilt auch für den imaginären Bonus .
Testschnipsel
(Hinweis: verwendet
console.log
anstelle vonalert
)Code-Snippet anzeigen
quelle
JavaScript (ES6),
5551 ByteGibt eine durch Leerzeichen getrennte Liste von Ganzzahlen zurück.
Imaginärer Bonus freundlich.
Formatiert und kommentiert
Testfälle
Code-Snippet anzeigen
quelle
Python 2 ,
6461 Bytes-3 Bytes dank Dennis
Probieren Sie es online!
quelle
Mathematica, 35 Bytes
quelle
Python 2 ,
656358 BytesProbieren Sie es online!
quelle
(2<<i)-1<<j
... und du hast es bereits herausgefunden. Gut gemacht! Auch gute Arbeit bei der Beseitigung der doppelten BereicheHaskell , 37 Bytes
Probieren Sie es online!
quelle
Haskell, 47 Bytes
Anwendungsbeispiel:
f 4
->[1,2,4,8,3,6,12,7,14,15]
. Probieren Sie es online! .So funktioniert es: Beginnen Sie für jede Zahl
b
in und verdoppeln Sie wiederholt den Wert und nehmen Sie Elemente aus dieser Liste.[1..n]
2^b-1
n-b+1
quelle
05AB1E , 6 Bytes
Probieren Sie es online! oder als Testsuite
Erläuterung
Verwendet den Sublistensummentrick wie in Dennis 'Jelly-Antwort gezeigt
quelle
Groovy,
9089 BytesBinäre Konvertierung ist in Groovy so dumm.
-1 danke an Gurupad Mamadapur
quelle
{(1..<2**it)...
Speichert ein Byte.Pyth, 7 Bytes
Probieren Sie es online aus.
Verwendet Dennis 'Algorithmus.
quelle
Bash + Unix-Dienstprogramme, 51 Bytes
Probieren Sie es online!
Die Eingabe n wird in einem Argument übergeben.
Verwenden Sie seq, um alle Zahlen mit n oder weniger Ziffern zu drucken. (Dies sind Basis-10-Zahlen, daher gibt es hier viele zusätzliche Zahlen. Es ist verschwenderisch und zeitaufwändig, aber das ist Codegolf!)
Der Aufruf von grep behält nur die Zahlen bei, die genau aus einer 1 gefolgt von einer 0 bestehen.
Verwenden Sie dann sort -r, um diese in umgekehrter lexikografischer Reihenfolge zu sortieren.
Als letztes wird dc auf die Eingabe zur Basis 2 gesetzt - es schiebt die sortierten Zahlen auf einen Stapel und druckt den Stapel dann von oben nach unten. (Dies druckt das letzte Element, das zuerst verschoben wurde usw., weshalb ich sort -r anstelle von sort verwende.)
Fehler behoben: Ich habe die Option -f% .f für seq weggelassen, die ab 1000000 für ganzzahlige Zählungen erforderlich ist. (Vielen Dank an @TobySpeight für den Hinweis, dass ein Problem aufgetreten ist.)
quelle
dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -
nur 12 Werte gemeldet. Ich denke du willstgrep ^1[01]*$
stattdessen.Mathematica / Mathics , 69 Bytes
Probieren Sie es online!
quelle
Perl 6 , 38 Bytes
Wie es funktioniert
Dh es konstruiert die Zahlen wie folgt:
Der Code:
Perl 6 , 44 Bytes
Dies war mein erster Ansatz, bevor ich über die (eigentlich einfachere) Bit-Shift-Lösung nachdachte.
Wie es funktioniert
Dh es konstruiert die Zahlen wie folgt:
quelle
Haskell
5946 BytesIch habe angefangen mit
f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]
Aus Nimis Antwort oben ist die Erkenntnis hervorgegangen,
sum.map(2^)$[0..x]
die sich auf diese Weise zusammenfassen lässt2^x-1
Am Ende mit
e n=[1..n]>>= \x->map(\y->2^y*(2^x-1))[0..n-x]
[1..n] - Liste mit der Anzahl der aufeinanderfolgenden Bits, die wir durchlaufen wollen`
>> = --grob übersetzt für jedes Element in der Liste auf der linken Seite übergeben Sie es an die Funktion auf der rechten Seite und verketten Sie alle Ergebnisse
\ x -> - Lambda-Funktionsdeklaration mit einem Argument
map xy - Wendet die Funktion x auf alle Mitglieder der Liste y an
In unserem Fall ist x = (\ y-> 2 ^ y * (2 ^ x-1)) - eine andere Lambda-Funktion 2 ^ y * (2 ^ x-1)). Diese Formel ergibt sich aus der Multiplikation mit zwei und der Addition einer Null nach rechts im Binärformat (Beispiel 0001 bis 0010). 2 ^ x - 1 ist die Anzahl der Bits, mit denen wir arbeiten. also haben wir für 11 2 ^ 0 * 3 (dh überhaupt nicht verschieben) == 0011, dann 2 ^ 1 * 3 = 0110, dann 2 ^ 2 * 3 - 1100.
[0..nx] Erstellt die Liste, wie oft wir die Bits verschieben können. Wenn wir mit einer einzelnen 1 arbeiten und dann 0001 betrachten, möchten wir 3-mal verschieben (4-1). Wenn wir zwei 11 arbeiten, wollen wir 4-2 und so weiter.
quelle
Python 3, 59 Bytes
Hinweis: Dies wurde unabhängig von den Lösungen von ovs und Dennis gemacht , obwohl es beiden sehr ähnlich ist.
Wie es funktioniert:
Probieren Sie es online!
Trinkgelder (sowohl Codierung als auch Bargeld) sind immer willkommen!
quelle
Japt , 11 Bytes
Online testen!
Erläuterung
Dies verwendet ziemlich genau den Ansatz von @ Dennis:
quelle
Python ,
6159 BytesProbieren Sie es online!
quelle
PHP,
59 5653 Bytesnimmt Eingaben von STDIN entgegen; renn mit
-R
.Nervenzusammenbruch
quelle
$argn
sehr gute Idee verwenden. Nach dem Lesen der Frage habe ich eine Lösung mit über 200 Bytes im KopfJ , 19 Bytes
Dies geschieht in @Dennis ' Lösung auf die gleiche Weise .
Probieren Sie es online!
Erläuterung
quelle
Python 3, 91 Bytes
Vollständiges Programm mit durch Kommas und Leerzeichen getrennter Ausgabe, wie angegeben.
Erläuterung:
Sternnotation entpackt Listen. So
print(*[1,2,3])
ist das gleiche wieprint(1,2,3)
. Übergeben Sie demint()
Konstruktor eine Folge aufeinanderfolgender Einsen.-~b
ergibtb+1
, aber Sie müssen es nicht mit eckigen Klammern umgeben, wenn Sie eine Zeichenfolge multiplizieren.Verschieben Sie die erzeugte Ganzzahl mehrmals mit Bits.
print()
hat das optionale Argument sep, das die Zeichenfolge angibt, die zwischen die einzelnen Elemente in einer entpackten Liste eingefügt werden soll.quelle
Java 7, 108 Bytes
Verdoppelt den Anfangswert, solange das Ergebnis kleiner als ist
2^n
. Anschließend wird der Anfangswert aktualisiert(initial_value * 2) + 1
und von dort erneut gestartet, bis er schließlich erreicht wird(2^n)-1
.zB für
n=4
:Probieren Sie es online!
quelle
Ruby, 50 Bytes
Ich habe einige "clevere" Ansätze ausprobiert, aber dies scheint die kürzeste zu sein (befolge buchstäblich die Anweisungen)
Erläuterung:
Jede Iteration beginnt mit 2 ^ n-1 und multipliziert sich mit 2, bis die Obergrenze erreicht ist. Nichts Besonderes, nur einfache Mathematik.
quelle
QBIC , 37 Bytes - imaginärer Bonus = noch 37 Bytes ...
while-wend
Schade, dass ich QBIC noch nicht eingebaut habe ... Erläuterung:EDIT: QBIC unterstützt jetzt
WHILE
:Das sind nur 26 Bytes! Hier ist der
WHILE
:quelle
MATL,
1918 Bytes1 Byte gespart dank @Luis
Probieren Sie es online
quelle
R ,
694846 ByteJede Dezimalzahl, die einer Zahl
i in 1..n
im Binärsystem entspricht, wird mit der2^(0..n-i)
erstenn-i+1
Zweierpotenz (1, 2, 4, ...) multipliziert .Probieren Sie es online!
quelle
Stax , 9 Bytes
Online ausführen und debuggen!
Erläuterung
Nun, hier gibt es keine Basiskonvertierung.
Verwendet die entpackte Version (10 Bytes), um zu erklären.
quelle
Stapel, 92-0 = 92 Bytes
Subtrahieren von 0 für den imaginären Bonus von @ StewieGriffin.
quelle