Frage Designfunktion f (f (n)) == -n [geschlossen]


Eine Frage, die ich bei meinem letzten Interview bekam:

Entwerfen Sie eine Funktion f, so dass:

f(f(n)) == -n

Woher n ist ein 32 Bit Vorzeichen mit Vorzeichen; Sie können keine komplexe Zahlenarithmetik verwenden.

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

Irgendwelche Ideen?


836


Ursprung


Antworten:


Wie wäre es mit:

f (n) = Vorzeichen (n) - (-1)n * n

In Python:

def f(n): 
    if n == 0: return 0
    if n >= 0:
        if n % 2 == 1: 
            return n + 1
        else: 
            return -1 * (n - 1)
    else:
        if n % 2 == 1:
            return n - 1
        else:
            return -1 * (n + 1)

Python fördert Ganzzahlen automatisch auf beliebige Längen. In anderen Sprachen wird die größte positive Ganzzahl überlaufen, so dass sie für alle Ganzzahlen mit Ausnahme der einen funktioniert.


Damit es für echte Zahlen funktioniert, müssen Sie die ersetzen n in 1)n mit { ceiling(n) if n>0; floor(n) if n<0 }.

In C # (funktioniert für jedes Double, außer in Überlaufsituationen):

static double F(double n)
{
    if (n == 0) return 0;

    if (n < 0)
        return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
    else
        return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}

374



Du hast nicht gesagt, welche Art von Sprache sie erwarteten ... Hier ist eine statische Lösung (Haskell). Es ist im Grunde mit den 2 wichtigsten Bits rum:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

Es ist viel einfacher in einer dynamischen Sprache (Python). Überprüfen Sie, ob das Argument eine Zahl X ist und geben Sie ein Lambda zurück, das -X zurückgibt:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()

439



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 Bits von int):

Wir müssen f (0) = 0 haben. (Beweis: Angenommen, f (0) = x. Dann ist f (x) = f (f (0)) = -0 = 0. Jetzt ist -x = f (f (x )) = f (0) = x, was bedeutet, dass x = 0 ist.)

Weiter für jeden x und y, annehmen f(x) = y. Wir wollen f(y) = -x dann. Und f(f(y)) = -y => f(-x) = -y. Zusammenfassend: wenn f(x) = y, dann f(-x) = -y, und f(y) = -x, und f(-y) = x.

Also müssen wir alle Ganzzahlen außer 0 in Vierergruppen aufteilen, aber wir haben eine ungerade Anzahl solcher Ganzzahlen; nicht nur das, wenn wir die Ganzzahl entfernen, die kein positives Gegenstück hat, haben wir noch 2 (mod4) Zahlen.

Wenn wir die 2 maximalen Zahlen entfernen (durch den abs-Wert), können wir die Funktion erhalten:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

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

Natürlich ist eine andere Option, nicht für 0 zu erfüllen und die 2 Zahlen, die wir entfernt haben, als Bonus zu bekommen. (Aber das ist nur dumm, wenn.)


280



Dank Überladen in C ++:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}

146



Oder Sie könnten den Präprozessor missbrauchen:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

135



Dies gilt für alle negativen Zahlen.

    f (n) = abs (n)

Weil es noch eine negative Zahl gibt als positive Zahlen für zwei komplementäre ganze Zahlen, f(n) = abs(n) gilt für einen weiteren Fall als f(n) = n > 0 ? -n : n Lösung, die das gleiche ist wie f(n) = -abs(n). Hast du eins ...: D

AKTUALISIEREN

Nein, es gilt nicht für einen Fall mehr, wie ich gerade durch Litbs Kommentar erkannt habe ... abs(Int.Min) wird einfach überlaufen ...

Ich dachte darüber nach, auch mod 2-Informationen zu verwenden, kam aber zu dem Schluss, dass es nicht funktioniert ... zu früh. Wenn es richtig gemacht wird, funktioniert es für alle Zahlen außer Int.Min weil das ü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.

    f (n) = 2n (abs (n)% 2) - n + sgn (n)

In C # wird dies das Folgende:

public static Int32 f(Int32 n)
{
    return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}

Damit es für alle Werte funktioniert, müssen Sie es ersetzen Math.Abs() mit (n > 0) ? +n : -nund schließe die Berechnung in ein unchecked Block. Dann bekommst du sogar Int.Min auf sich selbst als ungeprüfte Negation abgebildet.

AKTUALISIEREN

Inspiriert von einer anderen Antwort werde ich erklären, wie die Funktion funktioniert und wie eine solche Funktion aufgebaut wird.

Fangen wir gleich am Anfang an. Die Funktion f wird wiederholt auf einen bestimmten Wert angewendet n ergibt eine Folge von Werten.

    n => f (n) => f (f (n)) => f (f (f (n))) => f (f (f (f (n)))) => ...

Die Frage verlangt f(f(n)) = -n, das sind zwei aufeinanderfolgende Anwendungen von f negiere das Argument. Zwei weitere Anwendungen von f - insgesamt vier - negieren das Argument wieder nachgeben n nochmal.

    n => f (n) => -n => f (f (f (n))) => n => f (n) => ...

Jetzt gibt es einen offensichtlichen Zyklus der Länge vier. Substituierend x = f(n) und bemerke, dass die erhaltene Gleichung f(f(f(n))) = f(f(x)) = -x hält, ergibt folgendes.

    n => x => -n => -x => n => ...

Wir erhalten also einen Zyklus der Länge vier mit zwei Zahlen und zwei negierten Zahlen. Wenn Sie sich den Zyklus als Rechteck vorstellen, befinden sich negierte Werte an gegenüberliegenden Ecken.

Eine von vielen Lösungen, um einen solchen Zyklus zu konstruieren, ist das Folgende, beginnend mit n.

 n => negiere und subtrahiere eins
-n - 1 = - (n + 1) => addiere eins
-n => negiere und füge eins hinzu
 n + 1 => eins subtrahieren
 n

Ein konkretes Beispiel dafür ist ein solcher Zyklus +1 => -2 => -1 => +2 => +1. Wir sind fast fertig. Wenn man bedenkt, dass der konstruierte Zyklus eine ungerade positive Zahl, seinen geraden Nachfolger und beide Zahlen enthält, können wir die ganzen Zahlen in viele solcher Zyklen aufteilen (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 weil Null für sich selbst negiert ist. Und weil der Zyklus schon sagt 0 => x es folgt 0 => x => 0 => x. Dies ist nur ein Zyklus der Länge zwei und x wird nach zwei Anwendungen in sich selbst verwandelt, nicht in -x. Glücklicherweise gibt es einen Fall, der das Problem löst. Ob X Gleich Null, erhalten wir einen Zyklus der Länge eins, der nur Null enthält, und wir haben dieses Problem gelöst, indem wir schließen, dass Null ein fester Punkt von ist f.

Erledigt? Fast. Wir haben 2^32 Zahlen, Null ist ein fester Punkt verlassen 2^32 - 1 Zahlen, und wir müssen diese Nummer in Zyklen von vier Zahlen teilen. Schlecht das 2^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 mit dem kleineren Satz von 3 Bit signierten Itegern von -4 zu +3. Wir sind mit Null fertig. Wir haben einen kompletten Zyklus +1 => -2 => -1 => +2 => +1. Lassen Sie uns nun den Zyklus beginnen +3.

    +3 => -4 => -3 => +4 => +3

Das Problem, das auftritt, ist das +4 ist nicht als 3-Bit-Integer darstellbar. Wir würden erhalten +4 durch Negieren -3 zu +3 - was immer noch eine gültige 3-Bit-Ganzzahl ist - aber dann eins zu +3 (binär 011) Erträge 100binär. Interpretiert als vorzeichenlose Ganzzahl ist es +4 aber wir müssen es als vorzeichenbehaftete Ganzzahl interpretieren -4. Also eigentlich -4 für dieses Beispiel oder Int.MinValue im allgemeinen Fall ist ein zweiter fester Punkt der ganzzahligen arithmetischen Negation - 0  und Int.MinValue sind auf sich selbst abgebildet. Also ist der Zyklus eigentlich wie folgt.

    +3 => -4 => -3 => -4 => -3

Es ist ein Zyklus der Länge zwei und zusätzlich +3 betritt den Zyklus über -4. Als Folge -4 ist nach zwei Funktionsanwendungen korrekt auf sich selbst abgebildet, +3 ist korrekt zugeordnet -3 nach zwei Funktionsanwendungen, aber -3 wird nach zwei Funktionsanwendungen fälschlicherweise auf sich selbst abgebildet.

Also haben wir eine Funktion konstruiert, die für alle Ganzzahlen außer eins 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 ganzen ganzzahligen Bereich bis zu vier Werten abdecken. Die restlichen Werte sind die zwei Fixpunkte 0 und Int.MinValue das muss sich selbst und zwei beliebigen ganzen Zahlen zugeordnet werden x und -x Diese müssen durch zwei Funktionsanwendungen miteinander verknüpft werden.

Zu mappen x zu -x und umgekehrt müssen sie einen vierfachen Zyklus bilden und sie müssen sich an gegenüberliegenden Ecken dieses Zyklus befinden. Als Folge 0 und Int.MinValue müssen auch an gegenüberliegenden Ecken sein. Dies wird korrekt zugeordnet x und -x aber vertausche die beiden Fixpunkte 0 und Int.MinValue nach zwei Funktionsanwendungen und lassen uns mit zwei fehlerhaften 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 das ist das Beste, was wir erreichen können.


103



Mithilfe komplexer Zahlen können Sie die Aufgabe, eine Zahl zu negieren, in zwei Schritte unterteilen:

  • Multiply n mit i, und Sie erhalten n * i, die um 90 ° gegen den Uhrzeigersinn gedreht ist
  • multipliziere erneut mit i und du bekommst -n

Das Besondere ist, dass Sie keinen speziellen Handling-Code benötigen. Ich multipliziere nur mit dem Job.

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

Ich habe versucht, dies in der folgenden Abbildung zu visualisieren, indem ich signierte 8-Bit-Daten annahm. Sie müssten dies für 32-Bit-Ganzzahlen skalieren. Der zulässige Bereich für das anfängliche n ist -64 bis +63. Hier ist, was die Funktion für positive n tut:

  • Wenn n in 0..63 (Anfangsbereich) ist, addiert der Funktionsaufruf 64, wobei n dem Bereich 64..127 zugeordnet wird (mittlerer Bereich).
  • Wenn n in 64..127 (Zwischenbereich) ist, 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.

alt text


96



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));
    }

pictorial


61