Question Fonction de conception f (f (n)) == -n [fermé]


Une question que j'ai eue lors de ma dernière interview:

Concevoir une fonction f, tel que:

f(f(n)) == -n

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 toute la gamme de nombres, concevez-la pour la plus grande plage possible.

Des idées?


836


origine


Réponses:


Que diriez-vous:

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 promeut automatiquement les entiers à des longueurs arbitraires. Dans d'autres langages, le plus grand entier positif débordera, donc il fonctionnera pour tous les entiers sauf celui-là.


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

En C # (fonctionne pour tout double, sauf en cas de débordement):

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



Vous n'avez pas dit quel genre de langage ils attendaient ... Voici une solution statique (Haskell). Il s'agit essentiellement 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

C'est beaucoup plus facile dans un langage dynamique (Python). Vérifiez simplement si l'argument est un nombre X et renvoyez un lambda qui renvoie -X:

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

439



Voici une preuve de la raison pour laquelle une telle fonction ne peut pas exister, pour tous les nombres, si elle n'utilise pas d'informations supplémentaires (sauf 32 bits de int):

Nous devons avoir f (0) = 0. (Preuve: Supposons 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.)

En outre, pour tout x et y, supposons f(x) = y. Nous voulons f(y) = -x puis. Et f(f(y)) = -y => f(-x) = -y. Pour résumer: si f(x) = y, puis f(-x) = -y, et f(y) = -x, et f(-y) = x.

Donc, nous devons diviser tous les entiers sauf 0 en ensembles de 4, mais nous avons un nombre impair de tels entiers; non seulement cela, si nous supprimons l'entier qui n'a pas de contrepartie positive, nous avons toujours 2 (mod4) nombres.

Si on enlève les 2 nombres maximaux restants (par abs), on peut 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 consiste à ne pas se conformer à 0, et à obtenir les 2 numéros que nous avons supprimés en bonus. (Mais c'est juste un idiot si.)


280



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

146



Ou, vous pourriez abuser du préprocesseur:

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

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

135



Ceci est vrai pour tous les nombres négatifs.

    f (n) = abs (n)

Parce qu'il y a un nombre plus négatif que de nombres positifs pour les entiers complémentaires de deux, f(n) = abs(n) est valable pour un cas de plus f(n) = n > 0 ? -n : n solution qui est la même chose que f(n) = -abs(n). Je vous ai eu par un ...: D

METTRE À JOUR

Non, ce n'est pas valable pour un cas de plus que je viens de le reconnaître par le commentaire de litb ... abs(Int.Min) va juste déborder ...

J'ai aussi pensé à utiliser l'information du mod 2, mais j'ai conclu, ça ne marche pas ... au début. Si c'est bien fait, cela fonctionnera pour tous les nombres sauf Int.Min parce que cela va déborder.

METTRE À JOUR

J'ai joué avec lui pendant un certain temps, à la recherche d'un bon truc de manipulation, mais je ne pouvais pas trouver un bon doublure, alors que la solution mod 2 tient dans un.

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

En C #, ceci devient le suivant:

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

Pour le faire fonctionner pour toutes les valeurs, vous devez remplacer Math.Abs() avec (n > 0) ? +n : -net incluez le calcul dans un unchecked bloc. Ensuite, vous obtenez même Int.Min mappé à lui-même comme négation non contrôlée.

METTRE À JOUR

Inspiré par une autre réponse, je vais expliquer comment la fonction fonctionne et comment construire une telle fonction.

Commençons au tout début. La fonction f est appliqué à plusieurs reprises à une valeur donnée n donnant une séquence de valeurs.

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

La question exige f(f(n)) = -n, c'est deux applications successives de f nier l'argument. Deux autres applications de f - quatre au total - annuler l'argument à nouveau en cédant n encore.

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

Maintenant, il y a un cycle évident de longueur quatre. Substitution x = f(n) et notant que l'équation obtenue f(f(f(n))) = f(f(x)) = -x tient, donne ce qui suit.

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

Nous obtenons donc un cycle de longueur quatre avec deux nombres et les deux nombres niés. Si vous imaginez le cycle comme un rectangle, les valeurs inversées sont situées dans les coins opposés.

Une des nombreuses solutions pour construire un tel cycle est la suivante à partir de n.

 n => annuler et soustraire un
-n - 1 = - (n + 1) => ajouter un
-n => annuler et ajouter un
 n + 1 => soustraire un
 n

Un exemple concret est d'un tel cycle est +1 => -2 => -1 => +2 => +1. Nous avons presque fini. Notant que le cycle construit contient un nombre impair impair, son successeur pair, et les deux nombres nient, nous pouvons facilement diviser les nombres entiers en beaucoup de tels cycles (2^32 est un multiple de quatre) et ont trouvé une fonction qui satisfait les conditions.

Mais nous avons un problème avec zéro. Le cycle doit contenir 0 => x => 0 parce que le zéro est nié à lui-même. Et parce que le cycle indique déjà 0 => x ça suit 0 => x => 0 => x. Ceci est seulement un cycle de longueur deux et x est transformé en lui-même après deux applications, pas en -x. Heureusement, il y a un cas qui résout le problème. Si X est égal à zéro, nous obtenons un cycle de longueur un contenant seulement zéro et nous avons résolu ce problème en concluant que zéro est un point fixe de f.

Terminé? Presque. Nous avons 2^32 chiffres, zéro est un point fixe laissant 2^32 - 1 nombres, et nous devons partitionner ce nombre en cycles de quatre nombres. Mauvais 2^32 - 1 n'est pas un multiple de quatre - il restera trois nombres dans aucun cycle de longueur quatre.

Je vais expliquer la partie restante de la solution en utilisant le plus petit ensemble de itegers signés 3 bits allant de -4 à +3. Nous avons terminé avec zéro. Nous avons un cycle complet +1 => -2 => -1 => +2 => +1. Maintenant, construisons le cycle à partir de +3.

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

Le problème qui se pose est que +4 n'est pas représentable en entier de 3 bits. Nous obtiendrions +4 en niant -3 à +3 - ce qui est encore un entier valide de 3 bits - mais en ajoutant un à +3 (binaire 011) rendements 100binaire. Interprété comme un entier non signé, il est +4 mais nous devons l'interpréter comme un entier signé -4. Donc en fait -4 pour cet exemple ou Int.MinValue dans le cas général est un deuxième point fixe de la négation arithmétique entière - 0  et Int.MinValue sont mappés à eux-mêmes. Donc, le cycle est réellement comme suit.

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

C'est un cycle de longueur deux et en plus +3 entre dans le cycle via -4. En conséquence -4 est correctement mappé sur lui-même après deux applications de fonction, +3 est correctement mappé à -3 après deux applications de fonction, mais -3 est mappé par erreur sur lui-même après deux applications de fonction.

Nous avons donc construit une fonction qui fonctionne pour tous les entiers sauf un. Pouvons-nous faire mieux? Non, nous ne pouvons pas. Pourquoi? Nous devons construire des cycles de longueur quatre et sont capables de couvrir toute la gamme entière jusqu'à quatre valeurs. Les valeurs restantes sont les deux points fixes 0 et Int.MinValue qui doit être mappé à eux-mêmes et deux entiers arbitraires x et -x qui doivent être mappés les uns aux autres par deux applications de fonction.

Pour cartographier x à -x et vice versa, ils doivent former un cycle de quatre et ils doivent être situés aux coins opposés de ce cycle. En conséquence 0 et Int.MinValue doivent être aux coins opposés, aussi. Cela permettra de cartographier correctement x et -x mais échangez les deux points fixes 0 et Int.MinValue après deux applications de fonction et nous laisser avec deux entrées défaillantes. Il n'est donc pas possible de construire une fonction qui fonctionne pour toutes les valeurs, mais nous en avons une qui fonctionne pour toutes les valeurs sauf une et c'est le meilleur que nous pouvons réaliser.


103



En utilisant des nombres complexes, vous pouvez diviser efficacement la tâche de négation d'un nombre en deux étapes:

  • multipliez n par i, et vous obtenez n * i, qui est tourné de 90 ° dans le sens inverse des aiguilles d'une montre
  • multiplier encore par i, et vous obtenez -n

Ce qui est génial, c'est que vous n'avez pas besoin de code de manipulation spécial. Juste en multipliant par i fait le travail.

Mais vous n'êtes pas autorisé à utiliser des nombres complexes. Vous devez donc créer votre propre axe imaginaire en utilisant une partie de votre plage de données. Puisque vous avez besoin d'autant de valeurs imaginaires (intermédiaires) que de valeurs initiales, il vous reste seulement la moitié de la plage de données.

J'ai essayé de visualiser ceci sur la figure suivante, en supposant des données 8 bits signées. Vous auriez à l'échelle pour les entiers 32 bits. La plage autorisée pour l'initiale n est comprise entre -64 et +63. Voici ce que la fonction fait pour n positif:

  • Si n est dans 0,63 (plage initiale), l'appel de fonction ajoute 64, mappant n à la plage 64. 127 (plage intermédiaire)
  • Si n est dans 64..127 (intervalle intermédiaire), la fonction soustrait n de 64, n correspondant à la plage 0 ..- 63

Pour n négatif, la fonction utilise la plage intermédiaire -65 ..- 128.

alt text


96



Fonctionne sauf int.MaxValue et 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



La question ne dit rien sur ce que le type d'entrée et la valeur de retour de la fonction f doit être (au moins pas la façon dont vous l'avez présenté) ...

... juste que lorsque n est un entier de 32 bits alors f(f(n)) = -n

Alors, que diriez-vous de quelque chose comme

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

Si n est un entier de 32 bits, alors l'instruction f(f(n)) == -n sera vrai.

Évidemment, cette approche pourrait être étendue pour travailler pour une gamme de nombres encore plus large ...


48



pour javascript (ou d'autres langages typés dynamiquement), vous pouvez faire en sorte que la fonction accepte un int ou un objet et renvoie l'autre. c'est à dire.

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

donnant

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

alternativement, vous pourriez utiliser la surcharge dans une langue fortement typée bien que cela puisse enfreindre les règles

int f(long n) {
    return n;
}

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

47