Une question que j'ai posée lors de ma dernière interview:
Concevez une fonction
f
, telle que:f(f(n)) == -n
Où
n
est un entier signé 32 bits ; 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 large gamme possible.
Des idées?
Réponses:
Que diriez-vous:
En Python:
Python promeut automatiquement les entiers en longueurs arbitraires. Dans d'autres langues, le plus grand entier positif débordera, donc cela fonctionnera pour tous les entiers sauf celui-ci.
Pour le faire fonctionner pour des nombres réels, vous devez remplacer le n dans (-1) n par
{ ceiling(n) if n>0; floor(n) if n<0 }
.En C # (fonctionne pour tout double, sauf en cas de débordement):
la source
Vous n'avez pas dit à quel type de langage ils s'attendaient ... Voici une solution statique (Haskell). Il s'agit essentiellement de jouer avec les 2 bits les plus significatifs:
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:
la source
class C a b | a->b where { f :: a->b }
;instance C Int (()->Int) where { f=const.negate }
;instance C (()->Int) Int where { f=($()) }
.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 d'int):
Nous devons avoir f (0) = 0. (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 tout
x
ety
, supposonsf(x) = y
. Nous voulonsf(y) = -x
alors. Etf(f(y)) = -y => f(-x) = -y
. Pour résumer: sif(x) = y
, alorsf(-x) = -y
, etf(y) = -x
, etf(-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 nombres (mod4).
Si nous supprimons les 2 nombres maximaux restants (par valeur abs), nous pouvons obtenir la fonction:
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.)
la source
n = -2147483648
(valeur minimale); vous ne pouvez pasabs(n)
dans ce cas, et le résultat ne sera pas défini (ou une exception).Merci à la surcharge en C ++:
la source
Ou, vous pourriez abuser du préprocesseur:
la source
Cela est vrai pour tous les nombres négatifs.
Parce qu'il y a un nombre négatif de plus qu'il y a de nombres positifs pour deux entiers complémentaires,
f(n) = abs(n)
est valable pour un cas de plus que laf(n) = n > 0 ? -n : n
solution qui est la même quef(n) = -abs(n)
. Je vous ai par un ...: DMISE À JOUR
Non, ce n'est pas valable pour un cas de plus comme je viens de le reconnaître par le commentaire de litb ...
abs(Int.Min)
va juste déborder ...J'ai aussi pensé à utiliser les informations du mod 2, mais j'ai conclu que cela ne fonctionne pas ... trop tôt. Si cela est fait correctement, cela fonctionnera pour tous les numéros, sauf
Int.Min
parce que cela débordera.MISE À JOUR
J'ai joué avec pendant un certain temps, à la recherche d'un bon truc de manipulation, mais je n'ai pas pu trouver un joli one-liner, tandis que la solution mod 2 tient dans un.
En C #, cela devient le suivant:
Pour le faire fonctionner pour toutes les valeurs, vous devez remplacer
Math.Abs()
par(n > 0) ? +n : -n
et inclure le calcul dans ununchecked
bloc. Ensuite, vous êtes mêmeInt.Min
mappé sur lui-même comme le fait la négation non contrôlée.MISE À JOUR
Inspiré par une autre réponse, je vais expliquer comment fonctionne la fonction et comment construire une telle fonction.
Commençons au tout début. La fonction
f
est appliquée à plusieurs reprises à une valeur donnée,n
ce qui donne une séquence de valeurs.La question demande
f(f(n)) = -n
, soit deux applications successives def
nier l'argument. Deux autres applications def
- quatre au total - annulent à nouveau l'argumentn
.Maintenant, il y a un cycle évident de longueur quatre. En substituant
x = f(n)
et en notant que l'équation obtenuef(f(f(n))) = f(f(x)) = -x
est vraie, on obtient ce qui suit.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 négatives sont situées aux coins opposés.
Une des nombreuses solutions pour construire un tel cycle est la suivante à partir de n.
Un exemple concret est d'un tel cycle est
+1 => -2 => -1 => +2 => +1
. On a presque fini. En notant que le cycle construit contient un nombre positif impair, son successeur pair et que les deux nombres sont négatifs, nous pouvons facilement partitionner les nombres entiers en plusieurs de ces cycles (2^32
est un multiple de quatre) et avons 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 zéro est annulé à lui-même. Et parce que le cycle indique déjà0 => x
qu'il suit0 => x => 0 => x
. Ce n'est qu'un cycle de longueur deux etx
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. SiX
est égal à zéro, nous obtenons un cycle de longueur un contenant uniquement zéro et nous avons résolu ce problème en concluant que zéro est un point fixe def
.Terminé? Presque. Nous avons des
2^32
nombres, zéro est un point fixe laissant des2^32 - 1
nombres, et nous devons partitionner ce nombre en cycles de quatre nombres. Mauvais qui2^32 - 1
n'est pas un multiple de quatre - il restera trois nombres qui ne seront 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 sur 3 bits allant de
-4
à+3
. Nous en avons fini avec zéro. Nous avons un cycle complet+1 => -2 => -1 => +2 => +1
. Construisons maintenant le cycle à partir de+3
.Le problème qui se pose est qu'il
+4
n'est pas représentable comme un entier de 3 bits. Nous obtiendrions+4
en niant-3
à+3
- ce qui est toujours un entier valide de 3 bits - mais en ajoutant ensuite un à+3
(binaire011
), on obtient100
binaire. Interprété comme un entier non signé, il l'est,+4
mais nous devons l'interpréter comme un entier signé-4
. Donc, en fait,-4
pour cet exemple ouInt.MinValue
dans le cas général, il y a un deuxième point fixe de négation arithmétique entière -0
etInt.MinValue
sont mappés à eux-mêmes. Le cycle est donc en fait le suivant.C'est un cycle de longueur deux et
+3
entre en plus 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é sur-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 pouvons couvrir toute la plage entière jusqu'à quatre valeurs. Les valeurs restantes sont les deux points fixes
0
etInt.MinValue
qui doivent être mappés sur eux-mêmes et deux entiers arbitrairesx
et-x
qui doivent être mappés l'un sur l'autre par deux applications de fonction.Pour correspondre
x
à-x
et vice versa, ils doivent former un cycle à quatre et ils doivent être situés aux coins opposés de ce cycle. En conséquence0
etInt.MinValue
doivent également être dans des coins opposés. Cela va correctement mapperx
et-x
mais échanger les deux points fixes0
etInt.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 mieux que nous puissions obtenir.la source
À l'aide de nombres complexes, vous pouvez efficacement diviser la tâche de négation d'un nombre en deux étapes:
La grande chose est que vous n'avez pas besoin de code de traitement spécial. La simple multiplication par i fait le travail.
Mais vous n'êtes pas autorisé à utiliser des nombres complexes. Vous devez donc en quelque sorte créer votre propre axe imaginaire, en utilisant une partie de votre plage de données. Étant donné que vous avez besoin d'autant de valeurs imaginaires (intermédiaires) que de valeurs initiales, il ne vous reste que la moitié de la plage de données.
J'ai essayé de visualiser cela sur la figure suivante, en supposant que les données signées 8 bits. Vous devez mettre cela à l'échelle pour les entiers 32 bits. La plage autorisée pour n initial est de -64 à +63. Voici ce que fait la fonction pour n positif:
Pour n négatif, la fonction utilise la plage intermédiaire -65 ..- 128.
la source
float
vsint
). L '«anneau à 4 éléments» que de nombreuses réponses décrivent nécessite 4 états, qui peuvent être représentés comme 2 dimensions avec chacun 2 états. Le problème avec cette réponse est qu'elle nécessite un espace de traitement supplémentaire (ne fonctionne que pour -64..63, mais a besoin de -128..127) et ne précise pas explicitement la formule écrite!Fonctionne sauf int.MaxValue et int.MinValue
la source
0
à0
et-2147483648
à-2147483648
étant donné que ces deux nombres sont des points fixes pour l'opérateur de négation,x => -x
. Pour le reste des nombres, suivez les flèches dans l'image ci-dessus. Comme il ressort clairement de la réponse de SurDin et de ses commentaires, il y aura deux nombres, dans ce cas2147483647
et-2147483647
sans autre paire à échanger.La question ne dit rien sur ce que le type d'entrée et de la valeur de retour de la fonction
f
doivent être (au moins pas la façon dont vous l'avez présenté) ...... juste que lorsque n est un entier 32 bits,
f(f(n)) = -n
Alors, que diriez-vous de quelque chose comme
Si n est un entier 32 bits, alors l'instruction
f(f(n)) == -n
sera vraie.De toute évidence, cette approche pourrait être étendue pour fonctionner avec une gamme de nombres encore plus large ...
la source
pour le javascript (ou d'autres langages typés dynamiquement), vous pouvez demander à la fonction d'accepter un int ou un objet et de renvoyer l'autre. c'est à dire
donnant
vous pouvez également utiliser la surcharge dans un langage fortement typé bien que cela puisse enfreindre les règles, c.-à-d.
la source
Selon votre plateforme, certaines langues vous permettent de conserver l'état dans la fonction. VB.Net, par exemple:
L'IIRC, C ++ l'a également autorisé. Je soupçonne cependant qu'ils recherchent une solution différente.
Une autre idée est que, puisqu'ils n'ont pas défini le résultat du premier appel à la fonction, vous pouvez utiliser impair / égalité pour contrôler s'il faut inverser le signe:
Ajoutez un à la magnitude de tous les nombres pairs, soustrayez un de la magnitude de tous les nombres impairs. Le résultat de deux appels a la même ampleur, mais le seul appel où il est même nous échangeons le signe. Il y a des cas où cela ne fonctionnera pas (-1, max ou min int), mais cela fonctionne beaucoup mieux que tout ce qui a été suggéré jusqu'à présent.
la source
Exploiter les exceptions JavaScript.
la source
Pour toutes les valeurs 32 bits (avec la mise en garde de -0 à -2147483648)
Vous devez essentiellement associer chaque boucle -x => x => -x à la boucle ay => -y => y. J'ai donc jumelé les côtés opposés du
split
.par exemple pour les entiers 4 bits:
la source
Une version C ++, probablement pliant quelque peu les règles mais fonctionne pour tous les types numériques (flottants, entiers, doubles) et même les types de classe qui surchargent le moins unaire:
la source
x86 asm (style AT&T):
Code vérifié, tous les entiers 32 bits possibles passés, erreur avec -2147483647 (sous-dépassement).
la source
Utilise les globaux ... mais alors?
la source
Cette solution Perl fonctionne pour les entiers, les flottants et les chaînes .
Essayez quelques données de test.
Production:
la source
n
c'était une chaîne que je pourrais faire, 548 devient "First_Time_548", puis la prochaine fois qu'il passe par la fonction ... if (prefix == First_Time_ ") remplace" First_Time_ "par" - "Personne n'a jamais dit que f (x) devait être du même type.
la source
Je n'essaie pas réellement de donner une solution au problème lui-même, mais j'ai quelques commentaires, car la question indique que ce problème a été posé faisait partie d'un entretien (d'emploi?):
int.MinValue
àint.MaxValue
, et pour chacunn
dans cet appel de plagef(f(n))
et vérifier le résultat est-n
), en disant que j'utiliserais ensuite Test Driven Development pour arriver à une telle fonction.Oh, cette réponse suppose que l'entrevue était pour un poste lié à la programmation C #. Ce serait bien sûr une réponse idiote si l'entretien était pour un poste lié aux mathématiques. ;-)
la source
Je voudrais que vous changiez les 2 bits les plus significatifs.
Comme vous pouvez le voir, ce n'est qu'un ajout, en laissant de côté le peu porté.
Comment ai-je obtenu la réponse? Ma première pensée était juste un besoin de symétrie. 4 tours pour revenir là où j'ai commencé. Au début, je pensais que c'était du code Gray à 2 bits. Ensuite, j'ai pensé que le binaire standard était suffisant.
la source
Voici une solution qui s'inspire de l'exigence ou de la revendication selon laquelle les nombres complexes ne peuvent pas être utilisés pour résoudre ce problème.
La multiplication par la racine carrée de -1 est une idée qui semble échouer car -1 n'a pas de racine carrée sur les entiers. Mais jouer avec un programme comme mathématique donne par exemple l'équation
et c'est presque aussi bon que d'avoir une racine carrée de -1. Le résultat de la fonction doit être un entier signé. Je vais donc utiliser une opération modulo modifiée mods (x, n) qui retourne l'entier y congruent à x modulo n qui est le plus proche de 0. Seuls très peu de langages de programmation ont réussi une opération modulo, mais elle peut facilement être définie . Par exemple en python c'est:
En utilisant l'équation ci-dessus, le problème peut maintenant être résolu comme
Cela satisfait
f(f(x)) = -x
pour tous les entiers de la plage[-2
31
-2, 2
31
-2]
. Les résultats def(x)
sont également dans cette plage, mais bien sûr, le calcul aurait besoin d'entiers 64 bits.la source
C # pour une plage de 2 ^ 32 - 1 nombres, tous les nombres int32 sauf (Int32.MinValue)
impressions:
la source
La fonction doit essentiellement diviser la plage disponible en cycles de taille 4, avec -n à l'extrémité opposée du cycle de n. Cependant, 0 doit faire partie d'un cycle de taille 1, car sinon
0->x->0->x != -x
. Parce que 0 est seul, il doit y avoir 3 autres valeurs dans notre plage (dont la taille est un multiple de 4) pas dans un cycle correct avec 4 éléments.J'ai choisi ces valeurs étranges supplémentaires pour être
MIN_INT
,MAX_INT
etMIN_INT+1
. En outre,MIN_INT+1
sera mappéMAX_INT
correctement, mais restez bloqué et ne mappez pas en arrière. Je pense que c'est le meilleur compromis, car il a la belle propriété de ne fonctionner que correctement les valeurs extrêmes. Cela signifie également que cela fonctionnerait pour tous les BigInts.la source
Personne n'a dit qu'il devait être apatride.
Tricher, mais pas autant que beaucoup d'exemples. Encore plus de mal serait de jeter un œil à la pile pour voir si l'adresse de votre appelant est & f, mais cela sera plus portable (bien que pas sûr pour les threads ... la version thread-safe utiliserait TLS). Encore plus de mal:
Bien sûr, ni l'un ni l'autre ne fonctionne trop bien dans le cas de MIN_INT32, mais vous ne pouvez pas faire grand-chose à ce sujet, sauf si vous êtes autorisé à renvoyer un type plus large.
la source
Je pourrais imaginer utiliser le 31e bit comme un bit imaginaire ( i ) serait une approche qui prendrait en charge la moitié de la plage totale.
la source
fonctionne pour n = [0 .. 2 ^ 31-1]
la source
Le problème indique "des entiers signés 32 bits" mais ne spécifie pas s'ils sont à deux ou à un complément .
Si vous utilisez le complément à un, toutes les valeurs de 2 ^ 32 se produisent par cycles de longueur quatre - vous n'avez pas besoin d'un cas spécial pour zéro, et vous n'avez pas non plus besoin de conditions.
En C:
Cela fonctionne par
Après deux passes, nous avons l'inverse au niveau du bit de la valeur d'origine. Ce qui dans la représentation du complément à un équivaut à la négation.
Exemples:
la source
:RÉ
la source
la source
J'aimerais partager mon point de vue sur ce problème intéressant en tant que mathématicien. Je pense que j'ai la solution la plus efficace.
Si je me souviens bien, vous annulez un entier 32 bits signé en retournant simplement le premier bit. Par exemple, si n = 1001 1101 1110 1011 1110 0000 1110 1010, alors -n = 0001 1101 1110 1011 1110 0000 1110 1010.
Alors, comment définissons-nous une fonction f qui prend un entier signé 32 bits et renvoie un autre entier signé 32 bits avec la propriété que prendre deux fois f équivaut à retourner le premier bit?
Permettez-moi de reformuler la question sans mentionner les concepts arithmétiques comme les nombres entiers.
Comment définir une fonction f qui prend une séquence de zéros et de longueur 32 et renvoie une séquence de zéros et de même longueur, avec la propriété que prendre f deux fois équivaut à retourner le premier bit?
Observation: Si vous pouvez répondre à la question ci-dessus pour le cas 32 bits, vous pouvez également répondre pour le cas 64 bits, le cas 100 bits, etc. Vous appliquez simplement f au premier 32 bits.
Maintenant, si vous pouvez répondre à la question du cas 2 bits, Voila!
Et oui, il s'avère que changer les 2 premiers bits est suffisant.
Voici le pseudo-code
Remarque: L'étape 2 et l'étape 3 ensemble peuvent être résumées comme (a, b) -> (-b, a). Ça vous semble familier? Cela devrait vous rappeler la rotation de 90 degrés de l'avion et la multiplication par la racine carrée de -1.
Si je venais de présenter le pseudo-code seul sans le long prélude, cela ressemblerait à un lapin sorti du chapeau, je voulais expliquer comment j'ai obtenu la solution.
la source