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

Sie haben nicht gesagt, welche Art von Sprache sie erwarten... Hier ist eine statische Lösung (Haskell). Es ist im Grunde durcheinander mit den 2 höchstwertigen Bits:

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

In einer dynamischen Sprache (Python) ist das viel einfacher. Prüfen Sie einfach, ob das Argument eine Zahl X ist und geben Sie ein Lambda zurück, das -X liefert:

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

Answer 2

Wie wäre es damit:

f(n) = sign(n) - (-1) \* 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 wandelt ganze Zahlen automatisch in Longs beliebiger Länge um. In anderen Sprachen wird die größte positive ganze Zahl überlaufen, so dass es für alle ganzen Zahlen außer dieser einen funktionieren wird.

---

Damit es mit echten Zahlen funktioniert, müssen Sie die n in (-1) 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));
}

Answer 3

Hier ist ein Beweis dafür, warum eine solche Funktion nicht für alle Zahlen existieren kann, wenn sie keine zusätzlichen Informationen (außer 32bits von int) verwendet:

Wir müssen f(0) = 0 haben. (Beweis: Nehmen wir an, 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 ist).

Außerdem ist für jede x und y angenommen, dass f(x) = y . Wir wollen f(y) = -x dann. Und f(f(y)) = -y => f(-x) = -y . Zusammengefasst: Wenn f(x) = y dann f(-x) = -y und f(y) = -x und f(-y) = x .

Wir müssen also alle ganzen Zahlen außer 0 in 4er-Gruppen aufteilen, aber wir haben eine ungerade Anzahl solcher 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 entfernen (durch abs-Wert), erhalten wir die Funktion:

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 gibt es auch die Möglichkeit, die 0 nicht einzuhalten und die 2 Zahlen, die wir entfernt haben, als Bonus zu erhalten. (Aber das ist nur ein dummes Wenn.)

Answer 4

Dank der Überladung 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));
}

Answer 5

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