Diese Herausforderung wurde von einem Programmierblog inspiriert, den ich häufig betreibe. Den Originalbeitrag finden Sie hier: Ein Programmierpuzzle
Herausforderung
Definieren Sie eine Funktion f:Q->Q
so, dass sie f(f(n)) = -n
für alle Ganzzahlen ungleich Null n
gilt und wo Q
die Menge der rationalen Zahlen liegt.
Einzelheiten
In welcher Sprache bevorzugen Sie, definieren Sie eine Funktion oder ein Programm , f
das als Parameter akzeptiert eine Nummer n
und gibt oder gibt eine Zahl f(n)
.
Die Eingabe kann über den für Ihre Sprache am besten geeigneten Mechanismus erfolgen: Funktionsargument, Lesen von STDIN, Befehlszeilenargument, Stapelposition, Spracheingabe, Gruppenzeichen usw.
Die Ausgabe sollte ein Rückgabewert einer Funktion / eines Programms sein oder auf STDOUT gedruckt werden.
Ich möchte Antworten auf Funktionen beschränken, die den Programmstatus oder den globalen Speicher / die Daten, die von außerhalb der Funktion sichtbar sind, nicht nutzen f
. Wenn Sie zum Beispiel einen Zähler außerhalb f
dieses Zählers belassen , zählt, wie oft f
aufgerufen wurde, und nur eine Negation auf der Grundlage dieses Zählers durchzuführen , ist für niemanden eine große Herausforderung oder ein großes Interesse. Die Entscheidungen f
sollten sich nur auf Daten im f
lexikalischen Bereich stützen .
Diese Einschränkung ist jedoch wahrscheinlich für einige stapelorientierte Sprachen oder andere Arten von Sprachen ungeeignet, die diese Arten von Daten oder Bereichen nicht unterscheiden. Bitte verwenden Sie Ihr bestes Urteilsvermögen, um dem Geist dieser Herausforderung gerecht zu werden.
Wertung
Es gelten die allgemeinen Code-Golfregeln. Ihre Punktzahl ist die Anzahl der Bytes in Ihrem Quellcode.
Die minimale Antwort erfordert, dass die Domäne und die Codomäne von f
eine Teilmenge der Rationalen sind Q
. Wenn Sie Ihre Domain und Codomain f
auf die ganzen Zahlen beschränken Z
, entspricht Ihre Punktzahl der Obergrenze von 90% der Anzahl der Bytes in Ihrem Quellcode.
Tiebreak
Im Falle eines Unentschieden wird Folgendes verwendet:
- Nur wenige druckbare Nicht-Leerzeichen- Symbole in Ihrem Quellcode
- Frühestes Datum und Uhrzeit der Beantwortung
Bearbeiten
Sie müssen keine Zahlen mit beliebiger Größe unterstützen. Bitte interpretieren Sie die Mengen Z
und Q
Datentypen in der von Ihnen gewählten Sprache (in der Regel Integer bzw. Floating Point).
Wenn sich Ihre Lösung ausschließlich auf die zugrunde liegende Struktur oder das zugrunde liegende Bitmuster eines Datentyps stützt, beschreiben Sie bitte dessen Einschränkungen und die Verwendung.
f:Q->Q
bedeutet?f
es sich um eine Funktion handelt, die Mitglieder vonQ
(rationale Zahlen) anderen Mitgliedern (möglicherweise denselben) von (rationale Zahlen) zuordnetQ
. siehe en.wikipedia.org/wiki/Function_(mathematics)#NotationAntworten:
J, 9 Punkte (10 Zeichen)
Basierend auf der Stackoverflow-Antwort :
Erste Idee (13 Zeichen):
quelle
Python:
61 34 30 2927 Punktef: Q -> Q
in Mathe:
in Python:
getestet mit
Logik dahinter:
Wenn Sie eine ganze Zahl nehmen
n
und in sief
einfügen, erhalten Siex+0.5
. Dies ist nicht eine ganze Zahl nicht mehr, so dass die nächste Anwendung wird0.5-(x+0.5)
das ist-x
.Credits
Dank an
Anmerkungen
Zuerst dachte ich, das wäre in Ordnung
aber es ist f: N-> C und das ist nicht erlaubt: - /
quelle
f=lambda x:x%1>0and(-x+x%1)or x+.1
sind nur 34 Zeichen.f=lambda x:[x+.1,x%1-x](x%1>0)
ist nur 30f=lambda x:[x+.5,.5-x][x%1>0]
. Beachten Sie die Verwendung von .5 anstelle von .1, um Präzisionsprobleme zu umgehenf:Q->Q
bedeutet nur, dass f rationale Zahlen auf rationale Zahlen abbildet. Was meine Definition von f tut.C, 41 Punkte (41 oder 45 Zeichen)
Funktioniert mit 32- und 64-Bit.
f : Z -> Z
(außerINT_MAX
):Wenn wir nicht einschließen müssen, können
0
wir einige Zeichen (41 Zeichen) abschneiden:f : Z -> Z
(außer0
&INT_MAX
):Diese Funktion teilt alle Ganzzahlen auf der Grundlage ihres Vorzeichens und ihrer Parität in 4 Gruppen auf.
Wir haben also die 4 verschiedenen Kombinationen:
Da wir nach zwei Durchgängen das Vorzeichen der Zahl, aber nicht die Parität wechseln müssen, erhalten wir zwei verschiedene mögliche Folgen:
In diesem Beispiel habe ich das erste ausgewählt.
Zuerst müssen wir alle geraden positiven Ganzzahlen auf ungerade negative Ganzzahlen abbilden. Wir tun dies, indem wir das Vorzeichen ändern und die Zahl erhöhen (Sie können stattdessen auch die Zahl verringern):
Wir müssen dann alle ungeraden negativen Ganzzahlen auf gerade negative Ganzzahlen abbilden. Wir müssen sicherstellen, dass
f2(f1(n)) = -n
:Mit den gleichen Methoden finden wir
f3
undf4
:Um diese Funktionen zu einer einzigen Funktion zu kombinieren, beobachten wir, dass wir jedes Mal,
n
wenn das Vorzeichen gleich istn
und jedes Mal, wennn
es positiv ist, um eins inkrementieren und ansonsten um eins dekrementieren:Dies kann also umgeschrieben werden als:
wo
odd(n)
Renditen1
für ungerade Zahlen und-1
für gerade Zahlen.Es gibt insgesamt 4 Lösungen:
INT_MIN
könnte in allen 4 Funktionen immer als-INT_MIN == INT_MIN
Kantenfall betrachtet werden als =>f(f(INT_MIN)) = INT_MIN
.quelle
0
und 3 andere Nummern.Z
Bonus nur nehmen sollten, wenn Sie mindestens 0 decken.Hier ist mein Versuch.
Live Beispiel :
Die Eingabetypen können beliebig auf Ihre Bedürfnisse zugeschnitten werden. Diese Version funktioniert für ganzzahlige Literale, deren Größe kleiner als 2 ^ 32-1 ist.
quelle
f:Q->Q
nichtf:Z->Z
.f:Z->Z
, entschuldigen Sie die verwirrende Formulierungreturn -i
JavaScript, 18
Verwenden der neuen Fettpfeilnotation (Firefox 22).
Andere Version (18):
Vorherige Version (20):
Beispiel:
quelle
Mathematica 18
Hier
⌊...⌋
ist die Bodenfunktion. Es werden nur rationale Zahlen verwendet (keine Listen, komplexe Zahlen usw.)quelle
x86-Assemblersprache (FASM). Das Argument und das Ergebnis befinden sich im eax-Register.
Es funktioniert ordnungsgemäß für -2 ^ 30 <N <+ 2 ^ 30-1
16 Byte ausführbarer Code.
quelle
Common Lisp: 35 Bytes
Schema (und Schläger): 36 Bytes
Ungolfed mit Kommentaren und Erklärungen:
Für jede Zahl
x
in[1,->]
derif
wird in die Fraktion drehen ,1/2
die in beiden Sprachen eine echte genaue Zahl ist.Der Teilungsteil wird dann
(/ 1/2 x)
so , dass der Bruchteil wird,1/(x*2)
der immer darunter liegt1
. Denn1
es wird sein1/2
, denn2
es ist1/4
, etc.Für jede Zahl unter 1 das
if
wird wiederum in der Fraktion-1/2
, die die Funktion tun macht(/ -1/2 x)
was-1/(2*x)
aber da wir der Wert erwarten können, aufgrund der vorherigen Ausführung sein , die wir für / 1 (x * 2) Herstellung einer doppelten Anwendung ersetzen kann x-1/((1/(x*2))*2) = -x
ZB da
1
wird in1/2
die zweite Anwendung verwandelt(/ -1/2 1/2) ==> -1
quelle
C, 60 (~ 66 * .9 ~)
Hier ist eine unkondensierte Version:
Diese Methode funktioniert nur mit ganzen Zahlen, sodass der 90% -Bonus gutgeschrieben wird. Ich schrieb es ursprünglich in Java, erkannte jedoch, dass dieses Programm insbesondere von logischen Operatoren im C-Stil profitieren kann.
Da es keine ganze Zahl ist , entspricht
-INT_MIN
,f(f(INT_MIN))
zurückINT_MIN
statt.Das zugrunde liegende Mapping ist algebraisch eher einfach. Das Ausführen der Anweisung
x=f(x)
ersetzt x durch:x+1
, wennx
positiv und ungerade ist-x+1
, wennx
positiv und gerade istx-1
, wennx
negativ und ungerade ist-x-1
, wennx
negativ und gerade istDas Ergebnis eines jeden Falls fällt beim nächsten Anwenden der Funktion auf x unter den nächsten Fall.
Wie Sie sehen können, ergibt sich, wenn Sie einen Fall mit dem darauf folgenden Fall erstellen
-x
.Der Code ist das Ergebnis einer cleveren Vereinfachung der Funktion, um die Bitstruktur von Zweierkompliment-Ganzzahlen auszunutzen.
quelle
> <> , 21 + 3 = 24 Bytes, 22 Punkte
Verwenden Sie den offiziellen Python-Interpreter und die
-v
Befehlszeilenoption, um eine Eingabe für 3 Byte einzugeben.Ich habe das Gefühl, dass dies besser sein könnte - ich werde es weiter untersuchen und versuchen, es nach unten zu spielen.
Bei Eingabe
n
gibt das Programm auswo
(n>0)
und(n<0)
sind Booleaner. Dies entspricht der Python-Antwort von GelatinEs gibt jedoch
><>
keinen eingebauten Exponentiationsoperator, daher verwenden wir(1 - 2*(n%2))
anstelle von(-1)**n
.Was folgt, ist mathematische Theorie - lesen Sie, wenn (und nur wenn) Sie interessiert sind:
Bei einer
f: Z -> Z
solchen Funktion , dassf(f(n)) = -n
für allen
inZ
, sehen wir sofort, dassf(f(f(f(n)))) = n
, oder mit anderen Worten,f^4
die Identitätsfunktion ist. Insbesonderef
ist invertierbar und seine Umkehrfunktion istf^3
. Somitf
ist eine PermutationZ
, und daf^4 = Id
, so folgt daraus , daß jede Umlaufbahn (oder Zyklus) derf
Größe entweder1
,2
oder4
.Als nächstes sehen wir das
f(0) = 0
. Beweis:f(0) = f(-0) = f(f(f(0))) = -f(0)
alsof(0) = 0
, wie gewünscht. Umgekehrt sei angenommen,x
in einem Zyklus der Länge1
oder2
sof(f(x)) = x
. Dann-x = x
alsox = 0
.Es besteht also
f
bis auf den Fixpunkt (1-Takt) vollständig aus 4-Takten0
.Ferner muss jeder 4-Zyklus die Form hat
(x, y, -x, -y)
, und durch den Zyklus Drehung um uns annehmen könnenx
undy
beide positiv. Umgekehrt bestimmt jedes solche Produkt von 4 Zyklen, in denen die ganzen Zahlen ungleich Null partitioniert werden, eine Auswahl vonf
.Somit entspricht jede Auswahl von
f
eindeutig einem gerichteten Graphen, dessen Scheitelpunkte die positiven ganzen Zahlen sind, so dass jeder Scheitelpunkt auf genau einen Pfeil fällt, der entweder eintritt oder austritt. Genauer gesagt hat jeder Scheitelpunkt im zugrunde liegenden ungerichteten Graphen einen genauen Grad1
. (Jeder 4-Takt(x y -x -y)
mitx
undy
positiv entspricht dem Pfeilx --> y
.)Die Funktion in dieser Antwort (und einige andere Antworten hier) entspricht dem Graphen , wo
1 --> 2
,3 --> 4
und im Allgemeinen2k-1 --> 2k
.Solche Diagramme sind in Bijektion mit unendlichem Sequenzen von geordneten Paaren
(a_n, p_n)
, wobei jedesa_n
eine positive ganze Zahl ist und jedesp_n
ist entweder0
oder1
: Bei einem gegebenen Sequenz(a_1, p_1), (a_2, p_2), (a_3, p_3), ...
, wir erste Paar1
mit1 + a_1
, und dann bilden wir entweder den Pfeil1 --> 1 + a_1
oder auf den Pfeil1 + a_1 --> 1
in Abhängigkeit davon , obp_1
ist0
oder1
. Im Wesentlichen ist der Pfeil entweder ein<
Zeichen oder ein>
Zeichen, abhängig von der Parität vonp_1
.Nehmen Sie als nächstes die kleinste ungepaarte positive Ganzzahl
k
und zählen Sie abk
, genau ina_2
Schritten, indem Sie eine beliebige Zahl überspringen, die bereits mit etwas gepaart ist. Koppeln Siek
mit dem Ergebnis und stellen Sie die Pfeilrichtungp_2
wie oben beschrieben ein. Wiederholen Sie dann mit(a_3, p_3)
usw.Jeder Pfeil wird schließlich auf diese Weise bestimmt, sodass der Prozess genau definiert ist. Die Funktion in dieser Antwort entspricht der Sequenz
(1,0), (1,0), (1,0), ...
, da im Schrittn
die kleinste ungepaarte ganze Zahl ist2n-1
und keine ganzen Zahlen größer2n-1
sind, als mit irgendetwas gepaart wurden. Wir erhalten also2n-1 --> 2n
für jeden
(Pfeile sind auf diese Weise ausgerichtet, weil jedep_n
gleich ist0
).Die Mächtigkeit dieser Menge ist
(N*2)^N = N^N
, die durch den letzten Absatz dieser Antwort ist gleich2^N
, die Mächtigkeit der reellen Zahlen.quelle
So korrigieren Sie die frühere J-Antwort (ich habe nicht genug Reputation, um das Original zu kommentieren):
Es ersetzt nur das
_1&^
mit1-~2*2|]
, was das entgegengesetzte Vorzeichen gibt. Also habe ich das-
zu a geändert+
(was nur bei Eingabe von1
und zählt_1
).Hier sind die Tests:
Wie Sie sehen können, handelt es sich bei Domäne und Bereich um alle reellen Zahlen, dies funktioniert jedoch nur für ganze Zahlen (einschließlich 0).
Erläuterung:
quelle
GolfScript
ceiling(26*.9)=24
Golfscript verarbeitet nur Ganzzahlen. Wenden Sie also den
Z
Bonus für insgesamt 24 Punkte an:Der Sonderfall 0 umfasst 8 Zeichen. Wenn wir 0 ignorieren, können wir eine 17-Punkte-Antwort haben:
Dieser Code verarbeitet eine Ganzzahl
x
über dem Stapel wie folgt :x
0 ist, belasse es0
auf dem Stapel und wende keine Regeln mehr an.x
ist, negierex
.x
positiv, addieren1
.x
negativ ist, subtrahieren1
.Dies verbindet logisch Sätze von 4 Zahlen in einem Zyklus, wobei
f
Elemente des Zyklus durchquert werden und gegenüberliegende Ecken des Zyklus Negative voneinander sind. Jede Ganzzahl ist Teil von genau 1 solcher Zyklen, mit Ausnahme von 0, die in einem speziellen Fall geschrieben ist. Zum Beispiel für{-8, -7, 7, 8}
:7 f -> 8
8 f -> -7
-7 f -> -8
-8 f -> 7
Die einzigen relevanten Testfälle, an die ich denken konnte, waren eine negative Quote, eine negative Quote, eine positive Quote, eine positive Quote
0
, und dann habe ich eingeworfen,-1
und1
da ihre Nähe zu0
möglicherweise Probleme verursacht hat:Ich bin sicher, dass das aktuelle GolfScript etwas verbessert werden kann. Es fühlt sich nicht so an, als ob es 26 Zeichen aufnehmen sollte! Würde gerne ein paar Vorschläge hören.
quelle
Java, nur zum Spaß
Hier ist eine Implementierung, die eine tatsächliche Bijektion zwischen ℤ und ℤ² ausführt, was gleichzeitig eine ungerade Funktion ist (g (-x) == -g (x)). Es behandelt das entsprechende ℤ²-Element als komplexe Zahl, multipliziert es mit "i" und konvertiert es dann zurück zu back.
f (x) = g & supmin; ¹ (ig (x))
f (f (x)) = g & supmin; ¹ (-g (x)) = - x
Die Funktion läuft in O (1).
PS Frohes Neues Jahr!
quelle
Python 3 - 38
Ähnlich wie @ Elch Antwort, aber
f(n) == n
. Funktioniert für alle ganzzahligen Werte.quelle
Perl, 33 (ohne Leerzeichen)
Bearbeiten:
$=.".1"
verkürzt auf"$=.1"
(danke ardnew).Mathematik:
Ungolfed:
Beispiele:
quelle
sub f{yzxzzc?-$_:x.$_}
sub f{yzxzzc?-$_:x.$_}
ist nicht zustandsfrei, sondern verwendet einen Zustand über die Variable$_
. Aus diesem Grundf
ist (im mathematischen Sinne) keine Funktion mehr, da je nach Zustand unterschiedliche Werte für den gleichen Eingabewert möglich sind (Wetter$_
enthält ax
oder nicht). Mein Algorithmus verwendet keinen Status. Die Informationen werden im Ausgabewert codiert. Ganzzahlen werden durch Addition in reelle Zahlen umgewandelt.1
. Und reelle Zahlen werden mit umgeschaltetem Vorzeichen wieder in ganze Zahlen umgewandelt.$=
?f
definiert werdenQ->Q
) mit diesemx
Zeichen nicht erfüllt habe . auch$=.".1"
kann verkürzt werden"$=.1"
$=
ist nur, dass es nur ganzzahlige Zahlen akzeptiert . Das gleiche kann unter Verwendung eines gewöhnlichen Variable erreicht werden:$a=int$_[0]
. Das kostet aber drei zusätzliche Bytes wegen der Funktionint
.Julia, 26
Nicht sehr wettbewerbsfähig, aber sehr julianisch, da es auf mehrfachen Versand ankommt. Es macht nur na Rational, wenn es ein Int ist, oder ein Int mit einem Minuszeichen, wenn es etwas anderes ist. Man könnte einwenden, dass dies 2 Funktionen sind, aber Julia betrachtet dies als eine Funktion mit zwei Methoden und entspricht der Definition einer Funktion mit einer if-Anweisung über den Typ von
n
.quelle
3==3//1
kehrt zurück, kehrttrue
aberf(3//1)==f(3)
zurückfalse
.Süßigkeit ,
2018 BytesVerwendet den 3 -> 4 -> -3 -> -4 -> 3-Trick.
Zum Aufrufen verwenden Sie den Schalter -i am Interpreter
Beispiel für einen Doppelaufruf:
Lange Form:
quelle
Dyalog APL, 9 Punkte
Die Quelle ist 9 Bytes lang und qualifiziert sich für den Bonus (was überhaupt nicht hilft). Es wird auch die Formel aus der obersten SO-Antwort verwendet.
quelle
Python: 32 Bytes (29 Punkte)
f: Z -> Z
Nach Ben Reichs Methode.
quelle
(n>0)-(n<0)
mitcmp(n,0)
, ein paar Bytes zu speichern. (Aber nicht in Python 3: docs.python.org/3/whatsnew/3.0.html#ordering-comparisons )GTB , 22
quelle
Java, 113 Bytes
Der Ansatz ist ziemlich einfach. Es endete mehr Bytes, als ich erwartet hatte, kann aber vielleicht ein bisschen heruntergolfen werden.
Es erzeugt im Grunde 4 verschiedene "Bereiche" von x, wobei die Tatsache ausgenutzt wird, dass Java Variablen glücklich herumlaufen lässt. Ich musste einige knifflige Konvertierungen für negative Zahlen durchführen, was der Hauptgrund dafür ist, dass diese größer als erwartet ausfielen.
Funktioniert für alle x außer -2147483648.
quelle
Gleiche Zahlenfolge (3, 4, -3, -4, 3 ...) wie die Antwort auf das Golfscript, jedoch in Perl implementiert (42 Zeichen nach Entfernen des Leerzeichens)
Besser leserlich:
Oder noch besser lesbar:
Ausgabe:
quelle
Sed, 25 Bytes.
Verwendungszweck:
quelle
Matlab, 26 Zeichen
quelle
C ++ -
6355.8So sieht der Code aus:
Es funktioniert nicht bei Ganzzahlen, deren viertes Byte gleich 0xB ist, da dieser Wert verwendet wird, um die Durchläufe zu verfolgen. Andernfalls funktioniert für jedes Mitglied von Z, einschließlich Null.
quelle
f
mit einer statischen Variablen führen. aber worum geht es dannsqrt
?sqrt
da es sowieso beim Type Casting abgerundet wird. Ich werde es so umgestalten, dass es ohne die statische Variable funktioniert.55.8
, aber Ihr aktueller Code ist 62 Bytes lang. Edit: Egal, ich habe die Frage nicht richtig gelesen.Aktualisiert mit einer von Synthetica bereitgestellten Funktion (offensichtlich diejenige, die dies jetzt gutschreiben sollte)
Sprache: Python
Anzahl der Zeichen: 41 einschließlich Leerzeichen
quelle
f=lambda x:-float(x) if str(x)==x else`x`
ist ziemlich viel kürzer: 41 einschließlich Leerzeichenf
eine Zeichenfolge zurückgegeben. Die Spezifikation besagt, dass eine rationale Zahl zurückgegeben werden muss.Prolog, 36 Bytes
Code:
Erklärt:
Beispiel:
quelle
Javascript ES6,
2726 Bytesquelle
Mouse-2002 ,
211912 BytesDefiniert eine Funktion
A
; Rufen Sie es wie#A,#A,?;;
folgt auf (der Benutzer wartet, bis er eine beliebige Nummer eingibt). Alternativ rufen Sie es wie in#A,#A,n;;
demn
eine beliebige Zahl.quelle
Julia, 21
Dann
p // q ist Julias wörtliche Notation rationaler Zahlen.
quelle