Schreiben Sie auf der Grundlage der in diesem Numberphile-Video erwähnten "binären, aber mit Zweien" -Notation eine Funktion, die eine einzelne Zahl als Eingabe verwendet und alle Variationen dieser Zahl in einem "binären" System ausgibt , in dem Zweien zulässig sind.
Regeln
- Code darf nur eine Funktion / Methode sein, kein vollständiges Programm
- Die Eingabe ist eine Ganzzahl, die als einziger Parameter an die Funktion übergeben wird
- Bei der Ausgabe handelt es sich um alle gültigen Variationen der eingegebenen Nummer, die in "binär, aber mit Zweier-Notation" konvertiert wurden
- Die Ausgabe ist der Rückgabewert der Funktion, kann jedoch in jedem beliebigen Format erfolgen, sofern dies offensichtlich ist (z. B. 3 Ints, 3 Strings, durch Kommas / Leerzeichen getrennte Strings, Array von Ints usw.). Die Reihenfolge ist unwichtig
- In dem unwahrscheinlichen Fall, dass eine Sprache eine eingebaute Funktion enthält, um das Ergebnis zu erzielen, ist dies nicht zulässig
- Kürzester Code in Bytes ist der Gewinner
Erklärung der Ausgabe
Wenn Sie beispielsweise die Zahl übergeben haben 9
, können Sie sie in binär als konvertieren. 1001
Wenn Sie jedoch 2
s an jeder Position zulassen , können Sie sie auch als 201
(dh 2*4 + 0*2 + 1*1
) oder 121
(dh 1*4 + 2*2 + 1*1
) schreiben , wie in der folgenden Tabelle gezeigt:
+----+----+----+----+
| 8s | 4s | 2s | 1s |
+----+----+----+----+
| 1 | 0 | 0 | 1 |
| 0 | 2 | 0 | 1 |
| 0 | 1 | 2 | 1 |
+----+----+----+----+
Wenn also bestanden 9
, müsste Ihre Funktion die drei Zahlen 1001
, 201
und zurückgeben 121
.
Format und Ordnung ist irrelevant, solange es offensichtlich ist (dh [121,201,1001]
, "0201 0121 1001"
, ("1001","121","201")
sind gültige Ergebnisse , wenn eine Eingabe gegeben 9
).
Beispiele
2
=>10, 2
9
=>1001, 201, 121
10
=>1010, 210, 202, 1002, 122
23
=>2111, 10111
37
=>100101, 20101, 100021, 20021, 12101, 12021, 11221
quelle
Antworten:
GolfScript (25 Bytes) / CJam (
19 -17 Bytes)GolfScript:
Dadurch wird eine anonyme Funktion erstellt (siehe Metadiskussion zur Zulässigkeit anonymer Funktionen ).
Online-Demo
Eine direkte Übersetzung in CJam ist (danke an Martin Büttner für das Rasieren einiger Charaktere)
Präparation
Der Grund für die Quadrierungsoperation ist, dass wir bis zum größtmöglichen Wert iterieren müssen, dessen ternäre Darstellung, in Binärform interpretiert, gleich ist
^
. Da2 = 10
ist die "normale" Binärdarstellung^
derjenige, auf den es ankommt. Wenn wir das in ternäre umwandeln, stellen wir fest, dass die "schlimmsten" Fälle Potenzen von 2 sind. Ein optimaler Ansatz wäre, das Argument auf die Potenz von zu setzenln 3/ln 2 ~= 1.585
, aber die Quadratur ist viel kürzer.quelle
Python 2 (59 Bytes)
(Vielen Dank an @grc, @xnor und @PeterTaylor für die Hilfe im Chat)
Einfache Rekursion, Aufruf mit
S(23)
oder ähnlich.Erläuterung
Die allgemeine Idee ist, dass, wenn
n
die binäre Erweiterung mit a endet1
, jede pseudobinäre Erweiterung ("binär, aber mit zwei") auch mit a enden muss1
. Andernfalls könnte es mit0
oder enden2
.Daher schauen wir uns das letzte Stück an
n
, teilen es auf und verzweigen es entsprechend.Präparation
Variablen:
n
: Die Zahl, deren pseudobinäre Erweiterungen wir finden wollenB
: Eine Pseudo-Binärzeichenfolge, die von rechts nach links erstellt wirdquelle
Bash + Coreutils, 77
(Das ist ein TABZeichen im grep-Ausdruck.)
Das verbiegt diese Regel ein bisschen:
"In dem unwahrscheinlichen Fall, dass eine Sprache eine eingebaute Funktion enthält, um das Ergebnis zu erzielen, ist dies nicht zulässig."
Es stellt sich heraus , dass
dc
hat das Gegenteil von dem, was wir in gebaut brauchen. Zum Beispiel , wenn wir die Eingangsbasis 2 und Eingang eine binäre Zahl mit Zweien gesetzt, es wird es richtig analysieren. (In ähnlicher Weise werden AF als dezimale "Ziffern" 10-15 analysiert, wenn der Eingabemodus "Basis 10" ist.)seq
Erstellt eine Liste aller Dezimalzahlen bis zur binären Standarddarstellung von n, die als Dezimalzahl analysiert werden. Dann werden alle Zahlen, die etwas anderes als {0,1,2} enthalten, herausgefiltert. Dann werdendc
die verbleibenden Zahlen als binär analysiert, um zu sehen, welche zurück zu n ausgewertet werden.Bash-Funktionen können nur skalare Ganzzahlen von 0 bis 255 "zurückgeben". Daher erlaube ich mir, die Liste als "Rückkehr" zu STDOUT auszudrucken. Dies ist typisch für Shell-Skripte.
Ausgabe:
quelle
Haskell, 82
Dies ist nur eine Brute-Force-Lösung. es ist sehr ineffizient, da erwartet wird, dass es 3 ^ n Möglichkeiten durchbricht.
quelle
Jelly , 10 Bytes, Sprachnachstellung
Probieren Sie es online!
Eine Bruteforce-Lösung bis zu einer Anzahl von Hyperbits, die der Eingabe entsprechen (dieses Format wird als "hyperbinary" bezeichnet). Als solches ist es unglaublich ineffizient und läuft in O (3 n ).
Erläuterung
quelle
PHP, 138 Bytes
Nervenzusammenbruch
quelle
C ++, 159 Bytes
Teste es hier
quelle
k, 21 Bytes
Verwendet die gleiche Methode wie die Golfscript-Antwort von Peter Taylor
Beispiele:
quelle