Question d'entrevue: f(f(n)) == -n

Question

Une question que j'ai eu sur ma dernière interview:

Concevoir une fonction f, tels que:

f(f(n)) == -n

Où n est un 32 bits entier signé; vous ne pouvez pas utiliser l'arithmétique des nombres complexes.

Si vous ne pouvez pas concevoir une telle fonction pour l'ensemble de la gamme de nombres, de la conception la plus large possible.

Des idées?

Answer 1

Vous n'avez pas dit quel genre de langage qu'ils devraient... Voici une solution statique (Haskell). En gros, c'est de jouer avec les 2 bits les plus significatifs:

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

Il est beaucoup plus facile dans un langage dynamique (Python). Il suffit de vérifier si l'argument est un nombre X et retourner un lambda qui retourne -X:

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

Answer 2

Comment à ce sujet:

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

En 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 automatiquement favorise des entiers de taille arbitraire longs. Dans d'autres langues le plus grand entier positif débordement, de sorte qu'il fonctionne pour tous les entiers, sauf que l'un.

---

Pour le faire fonctionner pour les nombres réels, vous devez remplacer les n (-1)ⁿ avec { ceiling(n) if n>0; floor(n) if n<0 }.

En C# (fonctionne pour n'importe quel double, sauf dans les cas de dépassement de capacité):

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

Voici une preuve de pourquoi une telle fonction ne peut pas exister, pour tous les nombres, si elle n'utilise pas d'informations supplémentaires(à l'exception de 32bits de type int):

On doit avoir f(0) = 0. (La preuve: Supposons que f(0) = x. Alors f(x) = f(f(0)) = -0 = 0. Maintenant, -x = f(f(x)) = f(0) = x, ce qui signifie que x = 0.)

De plus, pour un x et y, supposons f(x) = y. Nous voulons f(y) = -x ensuite. Et f(f(y)) = -y => f(-x) = -y. Pour résumer: si f(x) = y, alors f(-x) = -y, et f(y) = -x, et f(-y) = x.

Donc, nous avons besoin de diviser tous les nombres entiers à l'exception de 0 en séries de 4, mais nous avons un nombre impair de ces entiers, non seulement que, si on enlève le nombre entier qui n'ont pas de contrepartie positive, nous avons encore 2(mod4).

Si on enlève les 2 le nombre maximal de gauche (abs), nous pouvons obtenir la fonction:

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

Bien sûr, une autre option est de ne pas se conformer pour 0, et d'obtenir les 2 numéros, nous avons retiré comme un bonus. (Mais c'est juste un idiot si.)

Answer 4

Grâce à la surcharge en 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

Ou, vous pourriez abus le préprocesseur:

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

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