Eine Frage, die ich bei meinem letzten Interview bekommen habe:
Entwerfen Sie eine Funktion
f
, so dass:f(f(n)) == -n
Wo
n
ist eine 32-Bit- Ganzzahl mit Vorzeichen ? Sie können keine komplexe Zahlenarithmetik verwenden.Wenn Sie eine solche Funktion nicht für den gesamten Zahlenbereich entwerfen können, entwerfen Sie sie für den größtmöglichen Bereich.
Irgendwelche Ideen?
Antworten:
Wie wäre es mit:
In Python:
Python befördert Ganzzahlen automatisch zu Longs beliebiger Länge. In anderen Sprachen läuft die größte positive Ganzzahl über, sodass sie für alle Ganzzahlen außer dieser funktioniert.
Damit es für reelle Zahlen funktioniert, müssen Sie das n in (-1) n durch ersetzen
{ ceiling(n) if n>0; floor(n) if n<0 }
.In C # (funktioniert für jedes Double, außer in Überlaufsituationen):
quelle
Sie haben nicht gesagt, welche Art von Sprache sie erwartet haben ... Hier ist eine statische Lösung (Haskell). Es spielt im Grunde mit den 2 wichtigsten Bits:
In einer dynamischen Sprache (Python) ist das viel einfacher. Überprüfen Sie einfach, ob das Argument eine Zahl X ist, und geben Sie ein Lambda zurück, das -X zurückgibt:
quelle
class C a b | a->b where { f :: a->b }
;instance C Int (()->Int) where { f=const.negate }
;;instance C (()->Int) Int where { f=($()) }
.Hier ist ein Beweis dafür, warum eine solche Funktion nicht für alle Zahlen existieren kann, wenn sie keine zusätzlichen Informationen verwendet (außer 32 Bit int):
Wir müssen f (0) = 0 haben. (Beweis: Angenommen, f (0) = x. Dann ist f (x) = f (f (0)) = -0 = 0. Nun ist -x = f (f (x) )) = f (0) = x, was bedeutet, dass x = 0.)
Weiter für jeden
x
undy
, nehme anf(x) = y
. Wir wollenf(y) = -x
dann. Undf(f(y)) = -y => f(-x) = -y
. Zusammenfassend: wennf(x) = y
, dannf(-x) = -y
undf(y) = -x
undf(-y) = x
.Wir müssen also alle ganzen Zahlen außer 0 in 4er-Sätze teilen, aber wir haben eine ungerade Anzahl solcher ganzen Zahlen; Nicht nur das, wenn wir die ganze Zahl entfernen, die kein positives Gegenstück hat, haben wir immer noch 2 (mod4) Zahlen.
Wenn wir die 2 verbleibenden Maximalzahlen (nach abs-Wert) entfernen, können wir die Funktion erhalten:
Eine andere Möglichkeit ist natürlich, 0 nicht einzuhalten und die 2 Zahlen, die wir entfernt haben, als Bonus zu erhalten. (Aber das ist nur dumm, wenn.)
quelle
n = -2147483648
(Mindestwert); Sie können nichtabs(n)
in diesem Fall, und das Ergebnis wird (oder eine Ausnahme) nicht definiert werden.Dank Überladung in C ++:
quelle
Oder Sie könnten den Präprozessor missbrauchen:
quelle
Dies gilt für alle negativen Zahlen.
Da es eine negative Zahl mehr gibt als positive Zahlen für zwei komplementäre Ganzzahlen,
f(n) = abs(n)
gilt dies für einen Fall mehr als für einef(n) = n > 0 ? -n : n
Lösung, die dieselbe ist wief(n) = -abs(n)
. Habe dich um eins ...: D.AKTUALISIEREN
Nein, es ist nicht mehr für einen Fall gültig, wie ich gerade durch Litbs Kommentar erkannt habe ...
abs(Int.Min)
wird einfach überlaufen ...Ich habe auch darüber nachgedacht, Mod 2-Informationen zu verwenden, bin aber zu dem Schluss gekommen, dass es nicht funktioniert ... zu früh. Wenn es richtig gemacht wird, funktioniert es für alle Zahlen, außer
Int.Min
weil dies überläuft.AKTUALISIEREN
Ich habe eine Weile damit gespielt und nach einem netten Manipulationstrick gesucht, aber ich konnte keinen schönen Einzeiler finden, während die Mod 2-Lösung in einen passt.
In C # wird dies wie folgt:
Um es für alle Werte arbeitet, müssen Sie ersetzen
Math.Abs()
mit(n > 0) ? +n : -n
und die Berechnung in einem Include -unchecked
Block. Dann werden Sie sogarInt.Min
auf sich selbst abgebildet, wie dies bei ungeprüfter Negation der Fall ist.AKTUALISIEREN
Inspiriert von einer anderen Antwort werde ich erklären, wie die Funktion funktioniert und wie eine solche Funktion aufgebaut wird.
Beginnen wir ganz am Anfang. Die Funktion
f
wird wiederholt auf einen bestimmten Wert angewendet,n
wodurch eine Folge von Werten erhalten wird.Die Frage verlangt
f(f(n)) = -n
, dass zwei aufeinanderfolgende Anwendungenf
das Argument negieren. Zwei weitere Anträge vonf
- insgesamt vier - negieren das Argument erneut und ergebenn
erneut.Jetzt gibt es einen offensichtlichen Zyklus der Länge vier. Das Ersetzen
x = f(n)
und Feststellen, dass die erhaltene Gleichungf(f(f(n))) = f(f(x)) = -x
gilt, ergibt Folgendes.Wir erhalten also einen Zyklus der Länge vier mit zwei Zahlen und den beiden negierten Zahlen. Wenn Sie sich den Zyklus als Rechteck vorstellen, befinden sich negierte Werte an gegenüberliegenden Ecken.
Eine von vielen Lösungen zur Konstruktion eines solchen Zyklus ist die folgende ab n.
Ein konkretes Beispiel ist ein solcher Zyklus
+1 => -2 => -1 => +2 => +1
. Wir sind fast fertig. Wenn wir feststellen, dass der konstruierte Zyklus eine ungerade positive Zahl enthält, sein gerader Nachfolger und beide Zahlen negieren, können wir die ganzen Zahlen leicht in viele solcher Zyklen unterteilen (2^32
ist ein Vielfaches von vier) und haben eine Funktion gefunden, die die Bedingungen erfüllt.Aber wir haben ein Problem mit Null. Der Zyklus muss enthalten,
0 => x => 0
da Null für sich selbst negiert wird. Und weil der Zyklus schon sagt0 => x
, folgt er0 => x => 0 => x
. Dies ist nur ein Zyklus der Länge zwei undx
wird nach zwei Anwendungen in sich selbst umgewandelt, nicht in-x
. Glücklicherweise gibt es einen Fall, der das Problem löst. WennX
gleich Null ist, erhalten wir einen Zyklus der Länge Eins, der nur Null enthält, und wir haben dieses Problem gelöst, indem wir daraus geschlossen haben, dass Null ein fester Punkt von istf
.Erledigt? Fast. Wir haben
2^32
Zahlen, Null ist ein fester Punkt, der2^32 - 1
Zahlen hinterlässt , und wir müssen diese Zahl in Zyklen von vier Zahlen aufteilen. Schlecht, das2^32 - 1
ist kein Vielfaches von vier - es bleiben drei Zahlen in keinem Zyklus der Länge vier.Ich werde den verbleibenden Teil der Lösung anhand des kleineren Satzes von 3-Bit-vorzeichenbehafteten Itegern von
-4
bis erklären+3
. Wir sind mit Null fertig. Wir haben einen vollständigen Zyklus+1 => -2 => -1 => +2 => +1
. Nun konstruieren wir den Zyklus ab+3
.Das auftretende Problem besteht darin, dass
+4
es nicht als 3-Bit-Ganzzahl dargestellt werden kann. Wir würden+4
durch Negieren-3
auf+3
- was immer noch eine gültige 3-Bit-Ganzzahl ist - erhalten, aber dann addieren wir eine zu+3
(binär011
) ergibt100
binär. Als vorzeichenlose Ganzzahl+4
interpretiert ist es, aber wir müssen es als vorzeichenbehaftete Ganzzahl interpretieren-4
. Tatsächlich ist also-4
für dieses Beispiel oderInt.MinValue
im allgemeinen Fall ein zweiter fester Punkt der ganzzahligen arithmetischen Negation -0
undInt.MinValue
werden auf sich selbst abgebildet. Der Zyklus ist also tatsächlich wie folgt.Es ist ein Zyklus der Länge zwei und
+3
tritt zusätzlich über in den Zyklus ein-4
. Infolgedessen-4
wird es nach zwei Funktionsanwendungen korrekt auf sich selbst abgebildet, wird nach zwei Funktionsanwendungen korrekt auf sich selbst+3
abgebildet, wird jedoch-3
nach zwei Funktionsanwendungen-3
fälschlicherweise auf sich selbst abgebildet.Also haben wir eine Funktion konstruiert, die für alle ganzen Zahlen außer einer funktioniert. Können wir es besser machen? Nein Wir können nicht. Warum? Wir müssen Zyklen der Länge vier konstruieren und können den gesamten ganzzahligen Bereich bis zu vier Werten abdecken. Die übrigen Werte sind die beiden Fixpunkte
0
undInt.MinValue
das muss sich selbst zugeordnet werden und zwei beliebige ganze Zahlenx
und-x
das muss durch zwei Funktionsanwendungen aufeinander abgebildet werden.Zur Karte
x
zu-x
und umgekehrt , sie müssen einen Cyclus bilden vier , und sie müssen an gegenüberliegenden Ecken des Zyklus befinden. In der Folge0
undInt.MinValue
müssen auch an gegenüberliegenden Ecken sein. Dadurch werden die beiden Fixpunkte und nach zwei Funktionsanwendungen korrekt zugeordnetx
und-x
ausgetauscht, und es verbleiben zwei fehlerhafte Eingaben. Es ist also nicht möglich, eine Funktion zu konstruieren, die für alle Werte funktioniert, aber wir haben eine, die für alle Werte außer einem funktioniert, und dies ist das Beste, was wir erreichen können.0
Int.MinValue
quelle
Mit komplexen Zahlen können Sie die Aufgabe des Negierens einer Zahl effektiv in zwei Schritte unterteilen:
Das Tolle ist, dass Sie keinen speziellen Handhabungscode benötigen. Nur multiplizieren mit i macht den Job.
Sie dürfen jedoch keine komplexen Zahlen verwenden. Sie müssen also irgendwie Ihre eigene imaginäre Achse erstellen und dabei einen Teil Ihres Datenbereichs verwenden. Da Sie genau so viele imaginäre (Zwischen-) Werte wie Anfangswerte benötigen, bleibt nur die Hälfte des Datenbereichs übrig.
Ich habe versucht, dies in der folgenden Abbildung zu visualisieren, unter der Annahme signierter 8-Bit-Daten. Sie müssten dies für 32-Bit-Ganzzahlen skalieren. Der zulässige Bereich für das anfängliche n liegt zwischen -64 und +63. Folgendes bewirkt die Funktion für positives n:
Für negatives n verwendet die Funktion den Zwischenbereich -65 ..- 128.
quelle
float
vsint
). Der '4-Elemente-Ring', den viele Antworten beschreiben, erfordert 4 Zustände, die als 2 Dimensionen mit jeweils 2 Zuständen dargestellt werden können. Das Problem bei dieser Antwort ist, dass sie zusätzlichen Verarbeitungsspeicherplatz benötigt (funktioniert nur für -64..63, benötigt aber -128..127 Speicherplatz) und keine explizite schriftliche Formel angibt!Funktioniert außer int.MaxValue und int.MinValue
quelle
0
an0
und-2147483648
an,-2147483648
da diese beiden Zahlen Fixpunkte für den Negationsoperator sindx => -x
. Folgen Sie für die restlichen Zahlen den Pfeilen im obigen Bild. Wie aus Surdin Antwort und seine Kommentaren klar ist, gibt es zwei Zahlen, in diesem Fall2147483647
und-2147483647
mit keinem anderen Paar zu tauschen links mit.Die Frage sagt nichts darüber aus, wie der Eingabetyp und der Rückgabewert der Funktion
f
sein müssen (zumindest nicht so, wie Sie sie dargestellt haben) ...... genau das, wenn n dann eine 32-Bit-Ganzzahl ist
f(f(n)) = -n
Also, wie wäre es mit so etwas
Wenn n eine 32-Bit-Ganzzahl ist, ist die Anweisung
f(f(n)) == -n
wahr.Offensichtlich könnte dieser Ansatz erweitert werden, um für einen noch größeren Bereich von Zahlen zu arbeiten ...
quelle
Für Javascript (oder andere dynamisch typisierte Sprachen) kann die Funktion entweder ein int oder ein Objekt akzeptieren und das andere zurückgeben. dh
geben
Alternativ können Sie das Überladen in einer stark typisierten Sprache verwenden, obwohl dies möglicherweise gegen die Regeln verstößt
quelle
Abhängig von Ihrer Plattform können Sie in einigen Sprachen den Status in der Funktion beibehalten. VB.Net zum Beispiel:
IIRC, C ++ erlaubte dies ebenfalls. Ich vermute, sie suchen nach einer anderen Lösung.
Eine andere Idee ist, dass Sie, da sie das Ergebnis des ersten Aufrufs der Funktion nicht definiert haben, mit ungerade / Gleichmäßigkeit steuern können, ob das Vorzeichen invertiert werden soll:
Addiere eins zur Größe aller geraden Zahlen, subtrahiere eins von der Größe aller ungeraden Zahlen. Das Ergebnis von zwei Anrufen hat die gleiche Größe, aber bei dem einen Anruf, bei dem es sich sogar um einen Austausch handelt, tauschen wir das Vorzeichen aus. Es gibt einige Fälle, in denen dies nicht funktioniert (-1, max oder min int), aber es funktioniert viel besser als alles andere, was bisher vorgeschlagen wurde.
quelle
Ausnutzen von JavaScript-Ausnahmen.
quelle
Für alle 32-Bit-Werte (mit der Einschränkung, dass -0 -2147483648 ist)
Grundsätzlich müssen Sie jede -x => x => -x-Schleife mit einer ay => -y => y-Schleife koppeln. Also habe ich die gegenüberliegenden Seiten des gepaart
split
.zB Für 4-Bit-Ganzzahlen:
quelle
Eine C ++ - Version, die wahrscheinlich die Regeln etwas verbiegt, aber für alle numerischen Typen (Floats, Ints, Doubles) und sogar Klassentypen funktioniert, die das unäre Minus überladen:
quelle
x86 asm (AT & T-Stil):
Code überprüft, alle möglichen 32-Bit-Ganzzahlen übergeben, Fehler mit -2147483647 (Unterlauf).
quelle
Verwendet Globals ... aber so?
quelle
Diese Perl-Lösung funktioniert für Ganzzahlen, Gleitkommazahlen und Zeichenfolgen .
Probieren Sie einige Testdaten aus.
Ausgabe:
quelle
n
ein String wäre, den ich machen könnte, wird 548 zu "First_Time_548" und dann, wenn er das nächste Mal die Funktion durchläuft ... if (Präfix == First_Time_ ") ersetzen Sie" First_Time_ "durch" - "Niemand hat jemals gesagt, dass f (x) der gleiche Typ sein muss.
quelle
Ich versuche eigentlich nicht, eine Lösung für das Problem selbst zu finden, habe aber einige Kommentare, da die Frage besagt, dass dieses Problem Teil eines (Job-?) Interviews war:
int.MinValue
bisint.MaxValue
, und für jedenn
Aufruf in diesem Bereichf(f(n))
und Überprüfung des Ergebnisses-n
) und sagen, dass ich dann Test Driven Development verwenden würde, um zu einer solchen Funktion zu gelangen.Oh, diese Antwort geht davon aus, dass das Interview für eine C # -Programmierposition war. Wäre natürlich eine dumme Antwort, wenn das Interview für eine mathematische Position wäre. ;-);
quelle
Ich würde Sie die 2 wichtigsten Bits ändern.
Wie Sie sehen können, ist es nur eine Ergänzung, bei der das getragene Bit weggelassen wird.
Wie bin ich zur Antwort gekommen? Mein erster Gedanke war nur ein Bedürfnis nach Symmetrie. 4 Umdrehungen, um dorthin zurückzukehren, wo ich angefangen habe. Zuerst dachte ich, das ist 2-Bit-Gray-Code. Dann dachte ich eigentlich, Standard Binär ist genug.
quelle
Hier ist eine Lösung, die von der Anforderung inspiriert ist oder behauptet, dass komplexe Zahlen nicht zur Lösung dieses Problems verwendet werden können.
Das Multiplizieren mit der Quadratwurzel von -1 ist eine Idee, die nur zu scheitern scheint, weil -1 keine Quadratwurzel über den ganzen Zahlen hat. Aber mit einem Programm wie mathematica herumzuspielen gibt zum Beispiel die Gleichung
und das ist fast so gut wie eine Quadratwurzel von -1. Das Ergebnis der Funktion muss eine vorzeichenbehaftete Ganzzahl sein. Daher werde ich eine modifizierte Modulo-Operation mods (x, n) verwenden, die die Ganzzahl y kongruent zu x modulo n zurückgibt, die am nächsten bei 0 liegt. Nur sehr wenige Programmiersprachen haben eine erfolgreiche Modulo-Operation, aber sie kann leicht definiert werden . ZB in Python ist es:
Mit der obigen Gleichung kann das Problem nun wie folgt gelöst werden
Dies ist
f(f(x)) = -x
für alle ganzen Zahlen im Bereich ausreichend . Die Ergebnisse von liegen ebenfalls in diesem Bereich, aber für die Berechnung wären natürlich 64-Bit-Ganzzahlen erforderlich.[-2
31
-2, 2
31
-2]
f(x)
quelle
C # für einen Bereich von 2 ^ 32 - 1 Zahlen, alle int32 Zahlen außer (Int32.MinValue)
Drucke:
quelle
Im Wesentlichen muss die Funktion den verfügbaren Bereich in Zyklen der Größe 4 unterteilen, wobei -n am entgegengesetzten Ende des Zyklus von n liegt. 0 muss jedoch Teil eines Zyklus der Größe 1 sein, da sonst
0->x->0->x != -x
. Da 0 alleine ist, müssen 3 andere Werte in unserem Bereich (deren Größe ein Vielfaches von 4 ist) nicht in einem richtigen Zyklus mit 4 Elementen vorhanden sein.Ich habe mich für diese zusätzlichen seltsame Werte zu sein
MIN_INT
,MAX_INT
undMIN_INT+1
. Darüber hinausMIN_INT+1
wird zuMAX_INT
ordnen, aber dort stecken bleiben und nicht zurück zuordnen. Ich denke, dies ist der beste Kompromiss, da er die nette Eigenschaft hat, dass nur die Extremwerte nicht richtig funktionieren. Es bedeutet auch, dass es für alle BigInts funktionieren würde.quelle
Niemand sagte, es müsse staatenlos sein.
Betrug, aber nicht so viel wie viele Beispiele. Noch schlimmer wäre es, den Stapel zu durchsuchen, um zu sehen, ob die Adresse Ihres Anrufers & f ist, aber dies wird portabler (obwohl nicht threadsicher ... die thread-sichere Version würde TLS verwenden). Noch böser:
Natürlich funktioniert keines von beiden für den Fall von MIN_INT32 zu gut, aber es gibt wenig, was Sie dagegen tun können, es sei denn, Sie dürfen einen breiteren Typ zurückgeben.
quelle
Ich könnte mir vorstellen, dass die Verwendung des 31. Bits als imaginäres ( i ) Bit ein Ansatz wäre, der die Hälfte des gesamten Bereichs unterstützt.
quelle
funktioniert für n = [0 .. 2 ^ 31-1]
quelle
Das Problem gibt "32-Bit-Ganzzahlen mit Vorzeichen" an, gibt jedoch nicht an, ob es sich um Zweierkomplement oder Einkomplement handelt .
Wenn Sie Einsen-Komplement verwenden, treten alle 2 ^ 32-Werte in Zyklen der Länge vier auf - Sie benötigen keinen Sonderfall für Null und Sie benötigen auch keine Bedingungen.
In C:
Das funktioniert von
Nach zwei Durchgängen haben wir die bitweise Umkehrung des ursprünglichen Wertes. Was in der Ein-Komplement-Darstellung der Negation entspricht.
Beispiele:
quelle
: D.
quelle
quelle
Ich möchte meinen Standpunkt zu diesem interessanten Problem als Mathematiker teilen. Ich denke, ich habe die effizienteste Lösung.
Wenn ich mich richtig erinnere, negieren Sie eine vorzeichenbehaftete 32-Bit-Ganzzahl, indem Sie nur das erste Bit umdrehen. Wenn beispielsweise n = 1001 1101 1110 1011 1110 0000 1110 1010 ist, dann ist -n = 0001 1101 1110 1011 1110 0000 1110 1010.
Wie definieren wir also eine Funktion f, die eine vorzeichenbehaftete 32-Bit-Ganzzahl verwendet und eine weitere vorzeichenbehaftete 32-Bit-Ganzzahl mit der Eigenschaft zurückgibt, dass die zweimalige Verwendung von f dasselbe ist wie das Umdrehen des ersten Bits?
Lassen Sie mich die Frage umformulieren, ohne arithmetische Konzepte wie ganze Zahlen zu erwähnen.
Wie definieren wir eine Funktion f, die eine Folge von Nullen und Einsen der Länge 32 annimmt und eine Folge von Nullen und Einsen derselben Länge zurückgibt, mit der Eigenschaft, dass das zweimalige Nehmen von f gleich dem Umdrehen des ersten Bits ist?
Beobachtung: Wenn Sie die obige Frage für 32-Bit-Fälle beantworten können, können Sie auch für 64-Bit-Fälle, 100-Bit-Fälle usw. antworten. Sie wenden f einfach auf die ersten 32-Bit-Fälle an.
Wenn Sie nun die Frage für einen 2-Bit-Fall beantworten können, Voila!
Und ja, es stellt sich heraus, dass das Ändern der ersten 2 Bits ausreicht.
Hier ist der Pseudocode
Anmerkung: Schritt 2 und Schritt 3 zusammen können als (a, b) -> (-b, a) zusammengefasst werden. Kommt mir bekannt vor? Das sollte Sie an die 90-Grad-Drehung der Ebene und die Multiplikation mit der Quadratwurzel von -1 erinnern.
Wenn ich nur den Pseudocode alleine ohne das lange Vorspiel präsentieren würde, würde es wie ein Kaninchen aus dem Hut scheinen, ich wollte erklären, wie ich zu der Lösung kam.
quelle