Sie sollten ein Programm oder eine Funktion schreiben, die eine nicht negative Ganzzahl N
als Eingabe und Ausgabe verwendet oder zwei Ganzzahlen (negativ, null oder positiv) X
und zurückgibt Y
.
Ganzzahlen sind im mathematischen Sinne gemeint, da es unendlich viele davon gibt.
Die implementierte Funktion muss bijektiv sein . Dies bedeutet, dass für jedes N
ein anderes X
Y
Paar X
Y
ausgegeben werden muss und jedes Paar für eine Eingabe ausgegeben werden sollte, dh für einige sollten N
alle folgenden Paare ausgegeben werden N
:
...
┌─────┬─────┬────┬────┬────┐
│-2 -2│-2 -1│-2 0│-2 1│-2 2│
├─────┼─────┼────┼────┼────┤
│-1 -2│-1 -1│-1 0│-1 1│-1 2│
├─────┼─────┼────┼────┼────┤
... │0 -2 │0 -1 │0 0 │0 1 │0 2 │ ...
├─────┼─────┼────┼────┼────┤
│1 -2 │1 -1 │1 0 │1 1 │1 2 │
├─────┼─────┼────┼────┼────┤
│2 -2 │2 -1 │2 0 │2 1 │2 2 │
└─────┴─────┴────┴────┴────┘
...
Beachten Sie, dass U V
und V U
verschiedene Paare sind, wenn U!=V
.
Einzelheiten
- Wenn Ihre Sprache keine willkürlich großen Ganzzahlen unterstützt, ist dies in Ordnung, aber Ihr Algorithmus sollte mit einem willkürlich großen Ganzzahldatentyp arbeiten. Ihr Code sollte mindestens noch Eingabewerte unterstützen
2^31-1
. - Wenn Sie die Ausgabe als Zeichenfolge drucken oder zurückgeben möchten, sind keine führenden Zeichen
0
oder+
Zeichen zulässig. Andernfalls ist die standardmäßige Ganzzahldarstellung Ihrer Sprache in Ordnung.
Beispiel
Wenn die Aufgabe darin bestehen würde, eine bijektive Funktion zu erstellen, die eine nicht negative Ganzzahl verwendet N
und eine Ganzzahl ausgibt, X
könnte eine Lösung die Funktion sein
if (input mod 2 == 0) return N/2 else return -(N+1)/2
,
in einer Sprache implementiert. Diese Funktion gibt X = 0 -1 1 -2 2...
für zurück N = 0 1 2 3 4...
.
10=>11 12, 9=>10 11
ist das ungültig, weil 11 wiederholt wird?Antworten:
Pyth, 15
Probieren Sie es online aus.
Eine Python-Übersetzung:
oder iterativ:
wo
binlist
konvertiert eine Zahl in eine Liste von Ziffern wiebinlist(4) = [1,0,0]
.Wie funktioniert das? Die Binärziffern der Zahl wie in meiner Python-Lösung als zwei verschachtelte Zahlen im Basisnegativ zwei interpretiert .n
Die Binärzahl entspricht dem Paar ( x , y ) = ( b 0 - 2 b 2 + 4 b 4 - 8 b 6 + ⋯ , b 1 - 2 b 3 + 4 b 5 - 8 b 7 + ⋯ )
Wenn wir die letzte Ziffer von n noch nicht verarbeitet hätten , wären alle Indizes um $ 1 $ höher, n ′ = … b 5 b 4 b 3 b 2 b 1 entsprechend dem Paar ( x ′ , y ′ ) = ( b 1 - 2 b 3 + 4 b 5 - 8 b 7 + ⋯ , b 2 - 2 b 4b0 n
Wir können dann die neuen Werte ausdrücken, sobald in Bezug auf die alten Werte gelesen wurdeb0
quelle
CJam,
242221 BytesMein Gehirn hat Probleme, die Mathematik zu verstehen, die andere Lösungen verwenden. Aber mein Gehirn versteht definitiv binär, also hier eine Lösung, die auf Bit-Manipulation basiert!
Probieren Sie es online aus.
Erläuterung
Dieser Ansatz behandelt die Eingabe als zwei verschachtelte Binärwerte, einen für jede Ausgangsnummer. Alle außer dem niedrigstwertigen Bit von jedem codieren eine Größe, und das niedrigstwertige Bit signalisiert, ob das bitweise Komplement dieser Größe genommen werden soll oder nicht. Bei dieser Implementierung entsprechen die ungeradzahlig positionierten Bits der ersten Ausgangsnummer (und die geradzahlig positionierten Bits der zweiten) und einem LSB von
0
Signalen, um das Komplement zu erhalten.Zum Beispiel kann eine Eingabe von bestimmten
73
, uninterleaving ihrer Binärdarstellung1001001b
erzeugt0 1|0
(ungerade positionierte Bits) und1 0 0|1
(selbst positionierten Bits). Der erste Wert hat eine Größe von01b = 1
und sollte für einen Endwert von ergänzt werden~1 = -2
, und der zweite Wert hat eine Größe von100b = 4
und sollte nicht ergänzt werden.Informeller Nachweis der Richtigkeit
Ich habe ein Testprogramm erstellt, das jede Eingabe von Null bis zu einer benutzerdefinierten Zahl minus Eins an der Ausgabestelle in einem 2D-Raster platziert. Sie können es auch online ausprobieren . Hier ist eine Ausgabe dieses Programms, die zeigt, wie der Algorithmus abbildet
0-99
:Das Füllmuster sieht etwas seltsam aus, ist aber tatsächlich bijektiv! Mit jeder 4er-Potenz füllt es ein Quadrat mit der doppelten vorherigen Seitenlänge. So ordnet der Algorithmus beispielsweise zu
0-15
:Dies macht das 4x4-Quadrat in der Mitte des 8x8-Quadrats aus
0-63
:Was macht das 8x8-Quadrat in der Mitte des 16x16-Quadrats aus
0-255
:quelle
li4b2fmd2/
anstelle von verwenden0li2b+W%2/W%
. Dies ergibt die gleichen ganzen Zahlen, jedoch in umgekehrter Reihenfolge.Python 2, 49
Bearbeiten: Verbessert auf 49 durch Verwendung einer besseren Ein-Schritt-Rekursion für Basis -2.
Hier ist eine Pyth-Version mit
reduce
.Edit: Verbessert auf 52 durch Umschalten auf Basis -2 vom ausgeglichenen Ternär .
Python 2, 52
Python 2, 54
Hierbei wird wie bei Runer112 eine Ziffernverschachtelung verwendet , jedoch mit ausgeglichener ternärer und nicht signierter Binärdatei. In Python ist keine Basiskonvertierung integriert, sodass der Code diese rekursiv implementiert.
Die Hilfsfunktion
h
(mit3
anstelle von9
) nimmt eine natürliche Zahl und wandelt sie mit den Stellensubstitutionen von ternär in ausgeglichenes ternär umSo wird beispielsweise 19, dessen Basis 201 ist, zu (-1) (0) (+ 1) im ausgeglichenen Ternär, was (-1) * 3 ^ 2 + (0) * 3 ^ 1 + (+) ist 1) * 3 ^ 0 = -8.
Ausgeglichenes Ternär genügt, um jede ganze Zahl zu codieren, und gibt so eine Abbildung von natürlichen Zahlen auf ganze Zahlen.
Um Paare von ganzen Zahlen abzubilden, verschachteln wir die Ziffern in
n
. Zu diesem Zweck betrachten wirh
jede andere Ziffern/9
als rekursiven Schritt und nicht alsn/3
. Dann verschieben wir uns für eine Koordinaten
durch Teilen des Bodens durch3
.Hier sind die ersten 81 Ausgänge, die den Bereich [-4,4] ^ 2 abdecken.
Eine alternative Codierung mit Viertel-Imaginär fiel länger aus, obwohl sie sehr hübsch ist.
Python 2, 63
In einer Sprache mit weniger umständlichem Umgang mit komplexen Konvertierungen wäre dies wahrscheinlich ein besserer Ansatz. Wenn wir komplexe Zahlen ausgeben könnten, könnten wir Folgendes tun:
Python 2, 38
quelle
L&b-%b2*2y/b4,yQy/Q2
ist nur 20 Bytes lang.Python 2, 98 Bytes
Beginnen wir mit einem einfachen Ansatz:
Es bildet einfach eine rechteckige
N
Spiraleinheit, die vom Ursprung ausgehend in einem 2D-Raster lang ist, und gibt die Koordinaten des letzten Punkts zurück.Die Funktion ist bijektiv, da:
Die Spirale sieht ungefähr so aus (außer bei 0 anstatt 1 zu beginnen):
quelle
0**0 == 1
In Python ist es also genau das Gleiche wieif a == 0: a = b/2
a=a or b/2
ist kürzer0^0=1
in Mathe, nicht nur Python.0**0
ist eigentlich unbestimmte Form in Mathematikdc, 49
Dies beginnt damit, dass die nicht negativen ganzen Zahlen in einem Raster angeordnet werden:
Beachten Sie, dass die Gitterpositionen mit zunehmendem N diagonal gefüllt werden. Beachten Sie, dass die Linie Y = 0 die dreieckige Zahlenfolge enthält, die durch gegeben ist
N = X(X+1)/2
. Dies ist eine quadratische Gleichung, die unter Verwendung der normalen Formel unter Verwendung nur der + ve-Wurzel gelöst wird, so dass wir X aus N bestimmen können, wenn Y = 0 ist. Als nächstes folgt ein einfaches arithmetisches Mischen, um für jedes N ein eindeutiges {X, Y} zu erhalten.Dies liefert die erforderliche bijektive Qualität, aber X und Y sind nur nicht negativ, aber die Frage erfordert alle möglichen ganzen Zahlen. Also werden X und Y mit gemappt
((t+1)/2)*((t+1)~2*2-1)
, um alle möglichen ganzen Zahlen zu erhalten.dc
hat eine willkürliche Genauigkeit, daher ist der Eingabebereich bis2^31-1
kein Problem. Beachten Sie auch, dass die Standardgenauigkeit 0 Dezimalstellen beträgt und dassqrt()
und die/
Abrundung das Verhalten ist, das hier benötigt wird.Ausgabe:
quelle
Matlab, 54 Bytes
Der Schlüssel hierbei ist
spiral
, dass dadurch eine Spiralmatrix beliebiger Größe erzeugt wird.kehrt zurück
In Matlab, das funktioniert für ganze Zahlen, aber Sie werden Speicherprobleme Art und Weise vor , dass bekommen, (na ja, ich nehme an, dass Sie als der Befehl4 n2 . Um ungefährn ≃ 104 Diese Matrix belegt mehr als 1 GB Speicherplatz. Mit 1 TB RAM kommen Sie also zurechtn ≃ 105 , und über 2,9 ⋅ 1011 GB RAM bringt Sie dazu n = 232 .
spiral
zuerst eine vollständige Matrix erstellt, die Größe hat von etwaquelle
Haskell,
7874 BytesTestlauf:
So funktioniert es: Listen Sie alle Paare im ersten Quadranten in der folgenden Reihenfolge auf
Spiegeln Sie jeden Punkt in die anderen Quadranten, um eine Liste mit 4 Elementlisten zu erstellen. Verketten Sie alle zu einer einzigen Liste und nehmen Sie das
n
th-Element.Bearbeiten: Funktion benötigt keinen Namen, Mathe neu angeordnet. Ausdrücke.
quelle
do
-notation 4 Bytes sparen: Probieren Sie es online aus!Haskell , 50 Bytes
Probieren Sie es online aus oder versuchen Sie es mit der Umkehrung!
Ungolfed
Erläuterung
Dies nutzt die Tatsache, dass jeder( x , y) ∈ N2 kann 1-zu-1 zugeordnet werden 2x⋅ ( 2 ⋅ y+ 1 ) - 1 ≤ N . Der obige Operator x Durch Teilen der Eingabe, solange sie gerade ist, verfolgen Sie die mit Null initialisierte Variable
(!)
berechnetl
(xCounter
). Sobald wir die gerade Zahl erreicht haben, wird eine Ganzzahldivision berechnety
.Beachten Sie, dass die aktuelle Funktion
f
(ntoN2
) die Eingabe erhöht, bevor Sie mit der Prozedur beginnen.quelle
05AB1E , 35 Bytes
Probieren Sie es online! oder als Testsuite
Erläuterung
Erwägen
Dann überlegen SieG: N × N( m , n )⟶ Z × Z⟼ ( h ( m ) , h ( n ) ),
woher
h : Nn⟶ Z⟼ { n2,- n + 12,n auchn ungerade.
Schon seit f , G und h Alles sind Bijektionen, die Komposition G∘ f: N ≤ Z × Z ist eine Schande.
Das Programm berechnet einfachG∘ f .
quelle
Mathematica, 46
Sortieren Sie die Vektoren nach ihrer Norm und nehmen Sie dann die
n
th.quelle
JavaScript, 166
168Bytes / ZeichenNeuer Ansatz mit einer rechteckigen Spirale wie andere.
Ich habe diese Antwort in Math.SE verwendet, in JS übersetzt und mit UglifyJS komprimiert .
Dieser Ansatz verwendet weder Schleifen noch erzeugt er die Spirale in irgendeiner Weise.
Da die Koordinaten der Spirale alle ganzen Zahlen abdecken, ist die Funktion bijektiv im Sinne vonf: N0→ Z2 .
Update: 2 Zeichen durch Speichern
Math
in gespeichertb
.Update 2: Ersetztf( 0 ) = f( 8 ) . Dies erzeugt keine Spirale mehr, funktioniert aber für alle nicht negativen ganzen ZahlenN0 (alle natürlichen Zahlen einschließlich 0 ).
t-=1
durcht+=4
, um das verursachte Problem zu behebenquelle