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

PHP, ohne eine globale Variable zu verwenden:

function f($num) {
  static $mem;

  $answer = $num-$mem;

  if ($mem == 0) {
    $mem = $num*2;
  } else {
    $mem = 0;
  }

  return $answer;
}

Funktioniert mit ganzen Zahlen, Gleitkommazahlen UND numerischen Zeichenketten!

Ich habe gerade festgestellt, dass dies unnötige Arbeit macht, aber was soll's

Answer 2

Reicht es nicht aus, wenn Sie sich an Ihren letzten Zustand erinnern?

int f (int n)
{
    //if count 
    static int count = 0;

    if (count == 0)
        { 
            count = 1;
            return n;
        }

    if (n == 0)
        return 0;
    else if (n > 0)
    {
        count = 0;
        return abs(n)*(-1);
    } 
    else
    {
        count = 0;
        return abs(n);
    }
}

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

Answer 3

Mit einer zyklischen Permutationsmethode zu tun.

-b a b -a

a b -a -b

in der trivialen Situation f(0) ergibt 0

sorry für meine grobe Antwort durch mein Telefon, nach dem 28. werde ich eine vollständige Version posten (jetzt Prüfung... ) Kurz gesagt, denke f(n) ist eine zyklische Permutation, die Frage ist wie man sie konstruiert.

definieren fk = f(f(f(f(...f(n))))) (k fs) Situation k=2 0.triviale Situation f(0) ergibt 0 1. Gruppen bilden, in Situation k=2, Gruppen: {0} {1,2} {3,4} ... {n,n+1 | (n+1)%2 = 0 } , Achtung: Ich verwende NUR Z+, weil die Konstruktion keine negativen Zahlen braucht. 2.konstruiere eine Permutation : wenn n % 2 = 0, also a=n-1 b=n wenn n % 2 = 1, also a=n b=n+1

wird die gleiche Permutation erzeugt, da n und f(n) in der gleichen Gruppe liegen.

notieren Sie die Permutation als P Rückgabe P(n)

für k=2t , nur die gleichen Schritte wie oben, nur MOD k. für k=2t-1 funktioniert die Methode zwar, aber sie macht keinen Sinn (f(n) = -n ist ok).

Answer 4

Es ist Betrug durch Speichern des Status, aber es funktioniert, brechen Operation in zwei: -n = (~n + 1) für ganze Zahlen

int f(int n) {
    static int a = 1;
    a = !a;
    if (a) {
        return (~n);
    } else {
        return (n+1);
    }
}

Answer 5

Ich habe mir die anderen Antworten noch nicht angesehen, aber ich gehe davon aus, dass die bitweisen Techniken bereits ausführlich diskutiert wurden.

Ich dachte, ich würde mir etwas Böses in C++ ausdenken, das hoffentlich keine Fälschung ist:

struct ImplicitlyConvertibleToInt
{
    operator int () const { return 0; }
};

int f(const ImplicitlyConvertibleToInt &) { return 0; }

ImplicitlyConvertibleToInt f(int & n)
{
    n = 0; // The problem specification didn't say n was const
    return ImplicitlyConvertibleToInt();
}

Die gesamte ImplicitlyConvertibleToInt Typ und Überladung ist notwendig, weil Temporäre nicht an eine Nicht-Konst-Referenz gebunden werden können.

Natürlich ist es jetzt unklar, ob f(n) ausgeführt wird, bevor -n .

Vielleicht ist eine bessere Lösung bei diesem Grad des Übels einfach:

struct ComparesTrueToInt
{
    ComparesTrueToInt(int) { } // implicit construction from int
};
bool operator == (ComparesTrueToInt, int) const { return true; }

ComparesTrueToInt f(ComparesTrueToInt ct) { return ComparesTrueToInt(); }