Hintergrund
Die meisten Leute hier sollten mit einigen ganzzahligen Basissystemen vertraut sein: dezimal, binär, hexadezimal, oktal. ZB im Hexadezimalsystem würde eine Zahl abc.de 16 darstellen
a*16^2 + b*16^1 + c*16^0 + d*16^-1 + e*16^-2
Man kann jedoch auch nicht ganzzahlige Basen wie irrationale Zahlen verwenden. Sobald eine solche Basis verwendet das goldene Verhältnis φ = (1 + √5) / 2 ≈ 1,618 ... . Diese werden analog zu ganzzahligen Basen definiert. So würde eine Zahl abc.de φ (wobei a bis e ganzzahlige Ziffern sind) darstellen
a*φ^2 + b*φ^1 + c*φ^0 + d*φ^-1 + e*φ^-2
Beachten Sie, dass im Prinzip jede der Ziffern negativ sein kann (obwohl wir das nicht gewohnt sind) - wir werden eine negative Ziffer mit einem führenden darstellen ~
. Für diese Frage beschränken wir uns auf die Ziffern von ~9
bis 9
, damit wir eine Zahl eindeutig als eine Zeichenfolge schreiben können (mit Tilden dazwischen). So
-2*φ^2 + 9*φ^1 + 0*φ^0 + -4*φ^-1 + 3*φ^-2
würde geschrieben werden als ~290.~43
. Wir nennen eine solche Nummer eine Phinarennummer .
A phinary Nummer kann immer in dargestellt wird Standardform , was bedeutet , dass die Darstellung verwendet nur Ziffern 1
und 0
ohne enthalten 11
überall und optional mit einem Minuszeichen , um anzuzeigen , dass die gesamte Zahl negativ ist. (Interessanterweise hat jede Ganzzahl eine eindeutige endliche Darstellung in Standardform.)
Darstellungen, die nicht in Standardform vorliegen, können immer mit den folgenden Überlegungen in Standardform umgewandelt werden:
- 011 φ = 100 φ (weil φ 2 = φ + 1)
- 0200 φ = 1001 φ (weil φ 2 + 1 / φ = 2φ)
- 0 ~ 10 φ = ~ 101 φ (weil φ - 1 / φ = 1)
Und dazu:
- Wenn die höchstwertige Ziffer
~1
(wobei der Rest der Zahl die Standardform ist) ist, ist die Zahl negativ, und wir können sie in die Standardform konvertieren, indem Sie alle1
und~1
vertauschen, ein Minuszeichen voranstellen und die obigen drei Regeln erneut anwenden, bis wir fertig sind Besorgen Sie sich das Standardformular.
Hier ist ein Beispiel für eine solche Normalisierung von (ich verwende zusätzliche Leerzeichen für positive Ziffern, um jede Ziffernposition ausgerichtet zu halten):
1~3.2~1φ
1~3. 2~1φ Rule:
= 0~2. 3~1φ (3)
= ~1~1. 4~1φ (3)
= ~1 0 0. 4~1φ (3)
= ~1 0 0. 3 0 1φ (3)
= ~1 0 1. 1 0 2φ (2)
= ~1 1 0. 0 0 2φ (1)
= ~1 1 0. 0 1 0 0 1φ (2)
= - 1~1 0. 0~1 0 0~1φ (4)
= - 0 0 1. 0~1 0 0~1φ (3)
= - 0 0 1.~1 0 1 0~1φ (3)
= - 0 0 0. 0 1 1 0~1φ (3)
= - 0 0 0. 0 1 1~1 0 1φ (3)
= - 0 0 0. 0 1 0 0 1 1φ (3)
= - 0 0 0. 0 1 0 1 0 0φ (1)
Nachgeben .-0.0101φ
Für die weitere Lektüre hat Wikipedia einen sehr informativen Artikel zum Thema.
Die Herausforderung
Schreiben Sie daher oder auf andere Weise ein Programm oder eine Funktion, die bei gegebener Zeichenfolge, die eine Phinärzahl darstellt (wie oben beschrieben), ihre Standardform ohne führende oder nachfolgende Nullen ausgibt. Die Eingabe enthält nicht notwendigerweise den Phinärpunkt, sondern immer die Ziffer links davon (also nein .123
). Die Ausgabe muss immer den Phinary Point und mindestens eine Ziffer links davon enthalten.
Sie können Eingaben über STDIN, ARGV oder Funktionsargumente vornehmen und das Ergebnis entweder zurückgeben oder an STDOUT ausgeben.
Sie können einen anderen Algorithmus als den oben beschriebenen verwenden, sofern dieser im Prinzip für beliebige (gültige) Eingaben korrekt und genau ist. Das heißt, die einzigen Grenzen, die möglicherweise Ihre Implementierung sprengen könnten, sollten technische Einschränkungen wie die Größe der integrierten Funktionen sein Datentypen oder den verfügbaren RAM. Beispielsweise ist es nicht zulässig, die Eingabe als Gleitkommazahl auszuwerten und dann gierig nach Ziffern zu suchen, da Eingaben gefunden werden könnten, bei denen Gleitkommazahlungenauigkeiten zu falschen Ergebnissen führen würden.
Dies ist Code Golf, die kürzeste Antwort (in Bytes) gewinnt.
Testfälle
Input Output
1 1.
9 10010.0101
1.618 10000.0000101
1~3.2~1 -0.0101
0.~1021 0. (or -0.)
105.~2 1010.0101
~31~5.~1 -100000.1001
quelle
Antworten:
Javascript (ES6) -
446418422420 BytesMinimiert:
Erweitert:
Der Code erzeugt eine Funktion
F
, die die angegebene Konvertierung ausführt.Es ist ein schweres Problem, Golf zu spielen. Es entstehen zahlreiche Randfälle, die eine Vereinfachung des Codes verhindern. Insbesondere der Umgang mit Negativen ist sowohl im Hinblick auf das Parsen als auch im Hinblick auf den logischen Umgang ein Schmerz.
Ich sollte beachten, dass der Code nur einen "angemessenen Bereich" von Eingaben behandelt. Um die Domäne der Funktion ohne
z
Begrenzung zu erweitern, kann die Anzahl der Nullen erhöht werden, und die konstante Begrenzung derwhile( c++ < 99 )
Schleife kann erhöht werden. Der derzeit unterstützte Bereich ist für die gelieferten Testfälle bereits überschritten.Beispielausgaben
Das
-0.
ist nicht schön, aber die Antwort ist immer noch richtig. Ich kann es bei Bedarf beheben.quelle
n
Bauchgefühl ist, dass die Anzahl der Durchläufe, die zur Normalisierung einer zweistelligen Eingabe erforderlich sind, irgendwo zwischenn
und liegen würden log(n)
. In jedem Fall kann die Anzahl der Durchgänge für jedes hinzugefügte Zeichen um den Faktor 10 erhöht werden. Die Anzahl der Nullen in derz
Konstanten ist ebenfalls ein interessantes Problem. Ich vermute, dass 9 für jede mögliche Eingabe übertrieben ist .$0
betrifft, unterstützt Javascript es nicht. Zumindest Firefox nicht. : Pfor( i = e = 0; i < n-3; i = j )
durchfor(; i < n-3; i = j )
und die Erklärungen nach oben zu bewegen, wirdN = t = n = 0;
mit ersetztN = t = n = i = e = 0;
j
nicht konstant auf einem Wert von gehalteni+1
. Hinweis in den dreiif
Blöckenj
wird auf zurückgesetzt0
. Daher kann es zu keinem Zeitpunkt nach dem erstenif
Block als Proxy für verwendet werdeni+1
. Die Variablei
selbst kann erst am Ende der Schleife aktualisiert werden (mit der dritten Anweisung infor
), da ihr Wert bis zum Ende der Schleife verwendet wird. Aber nachdem ich das gesagt habe, fehlt mir vielleicht etwas. Wenn Sie den Code kürzen, testen und überprüfen können, ob er noch funktioniert, senden Sie eine Kopie an pastebin.com und einen Link hierher. Ich werde Ihnen in der Antwort die gebührende Ehre erweisen. :)Haskell, 336 Bytes
Dies ist der Greedy-Algorithmus, jedoch mit einer exakten Darstellung
[a,b]
der Zahlen a + bφ ( a , b ∈ ∈), um Gleitkommafehler zu vermeiden.g[a,b]
testet ob a + bφ <0. Anwendungsbeispiel :quelle