Bestimmung der Funktion f(f(n)) == -n

Question

Eine Frage, die mir bei meinem letzten Vorstellungsgespräch gestellt wurde:

Eine Funktion entwerfen f , so dass:

f(f(n)) == -n

Wo n ist ein 32-Bit vorzeichenbehaftete Ganzzahl Sie können nicht mit komplexen Zahlen arithmetisch rechnen.

Wenn Sie eine solche Funktion nicht für den gesamten Zahlenbereich entwickeln können, entwickeln Sie sie für den größtmöglichen Bereich.

Irgendwelche Ideen?

Answer 1

Wenn Sie komplexe Zahlen verwenden, können Sie die Aufgabe, eine Zahl zu negieren, effektiv in zwei Schritte unterteilen:

• Multipliziere n mit i, und du erhältst n*i, was n um 90° gegen den Uhrzeigersinn gedreht ist.
• wieder mit i multiplizieren, und man erhält -n

Das Tolle daran ist, dass Sie keinen speziellen Bearbeitungscode benötigen. Die Multiplikation mit i reicht völlig aus.

Aber Sie dürfen keine komplexen Zahlen verwenden. Also müssen Sie irgendwie Ihre eigene imaginäre Achse erstellen, indem Sie einen Teil Ihres Datenbereichs verwenden. Da Sie genau so viele imaginäre (Zwischen-)Werte wie Anfangswerte benötigen, steht Ihnen nur die Hälfte des Datenbereichs zur Verfügung.

Ich habe versucht, dies in der folgenden Abbildung zu veranschaulichen, wobei ich von 8-Bit-Daten mit Vorzeichen ausgegangen bin. Für 32-Bit-Ganzzahlen müssten Sie dies skalieren. Der zulässige Bereich für das anfängliche n ist -64 bis +63. Hier sehen Sie, was die Funktion für positive n tut:

• Liegt n im Bereich 0..63 (Anfangsbereich), wird durch den Funktionsaufruf 64 hinzugefügt, wodurch n dem Bereich 64..127 (Zwischenbereich) zugeordnet wird.
• Wenn n im Bereich 64..127 (Zwischenbereich) liegt, subtrahiert die Funktion n von 64 und ordnet n dem Bereich 0..-63 zu.

Für negative n verwendet die Funktion den Zwischenbereich -65..-128.

Answer 2

Funktioniert außer int.MaxValue und int.MinValue

    public static int f(int x)
    {

        if (x == 0) return 0;

        if ((x % 2) != 0)
            return x * -1 + (-1 *x) / (Math.Abs(x));
        else
            return x - x / (Math.Abs(x));
    }

Answer 3

Die Frage sagt nichts darüber aus, was der Eingabetyp und der Rückgabewert der Funktion f sein müssen (zumindest nicht so, wie Sie es dargestellt haben)...

...nur dass, wenn n eine 32-Bit-Ganzzahl ist, dann f(f(n)) = -n

Wie wäre es also mit etwas wie

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}

Wenn n eine 32-Bit-Ganzzahl ist, wird die Anweisung f(f(n)) == -n wahr sein wird.

Natürlich könnte dieser Ansatz auf eine noch größere Anzahl von Zahlen erweitert werden...

Answer 4

Für Javascript (oder andere dynamisch typisierte Sprachen) können Sie die Funktion entweder ein int oder ein Objekt akzeptieren und das andere zurückgeben, d.h..

function f(n) {
    if (n.passed) {
        return -n.val;
    } else {
        return {val:n, passed:1};
    }
}

Geben

js> f(f(10))  
-10
js> f(f(-10))
10

alternativ könnte man die Überladung in einer stark typisierten Sprache verwenden, obwohl das die Regeln brechen kann, z.B.

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}

Answer 5

Je nach Plattform können Sie in einigen Sprachen den Status in der Funktion beibehalten. VB.Net, zum Beispiel:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

IIRC, C++ erlaubt dies auch. Ich vermute jedoch, dass sie nach einer anderen Lösung suchen.

Eine andere Idee ist, dass man, da das Ergebnis des ersten Funktionsaufrufs nicht definiert wurde, mit ungerade/ungerade steuern könnte, ob das Vorzeichen invertiert werden soll:

int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}

Addiere eins zum Betrag aller geraden Zahlen, subtrahiere eins vom Betrag aller ungeraden Zahlen. Das Ergebnis von zwei Aufrufen hat denselben Betrag, aber bei dem einen Aufruf, bei dem es gerade ist, vertauschen wir das Vorzeichen. 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.