f (g (x)) diminue tandis que g (f (x)) augmente

42

Pour ce défi, vous devez implémenter deux fonctions, f et g , sur les entiers, telles que f ∘ g est une fonction strictement décroissante tandis que g ∘ f est une fonction strictement croissante. En d'autres termes, si vous prenez deux entiers quelconques a <b , alors f (g (a))> f (g (b)) et g (f (a)) <g (f (b)) . Il n'y a pas de restrictions sur f et g individuellement, sauf qu'ils doivent mapper un entier à un autre.

Veuillez inclure une courte description de f et g et un argument pour expliquer pourquoi ils possèdent la propriété requise.

Crédit: Ce défi a été inspiré par un problème rencontré lors du concours de maîtrise en mathématiques roumain de 2011 (qui demande la même chose, mais sur des nombres réels au lieu d'entiers). Si vous voulez vraiment des spoilers, vous savez maintenant quoi chercher.

Règles

  • Le mot "fonction" dans ce défi doit être pris dans le sens mathématique du mappage d'un entier à un autre: vous pouvez écrire deux programmes ou deux fonctions et utiliser l'une des méthodes standard de réception et de sortie, comme d'habitude. Vous pouvez utiliser des représentations sous forme de chaînes d'entiers au lieu de variables entières réelles, mais les types d'entrée et de sortie doivent être identiques, de sorte que les fonctions puissent être composées sans conversion manuelle des types entre les deux. Rappelez-vous que, f et g doivent toujours être des fonctions sur, vous ne pouvez donc pas tricher en utilisant deux représentations de chaîne différentes du même nombre ou quelque chose du genre.

  • Rappelez-vous que les fonctions peuvent ne pas être nommées , tant que leur nom n'est pas utilisé par lui-même ou par une autre fonction que vous définissez. Si vous nommez une ou les deux fonctions, vous pouvez supposer qu’elles existent dans le même programme, afin qu’elles puissent se référer les unes aux autres dans leur implémentation (par exemple, def f(x): return -g(x)en Python).

  • Les règles habituelles de dépassement d'entier s'appliquent: votre solution doit pouvoir fonctionner avec des entiers arbitrairement grands dans une version hypothétique (ou peut-être réelle) de votre langage dans laquelle tous les entiers sont non liés par défaut, mais si votre programme échoue dans la pratique en raison de la mise en œuvre ne supportant pas des entiers de cette taille, cela n'invalide pas la solution.

  • Vous pouvez utiliser n'importe quel langage de programmation , mais notez que ces failles sont interdites par défaut.

  • Il s'agit d'un . Votre score est donc la somme du nombre d'octets des deux fonctions et la réponse la plus courte valide l'emporte.

Martin Ender
la source
Les fonctions peuvent-elles renvoyer une chaîne?
Matthew Roh
@SIGSEGV Je dirais que oui, mais seulement s'ils acceptent également une chaîne en entrée, afin qu'ils puissent être composés sans avoir à insérer de conversion de type.
Martin Ender
Aww darnit, j'ai essayé la conversion en chaîne pour que l'autre fonction ne puisse plus éditer les résultats.
Matthew Roh
1
@ Fatalize Correct. Chacun doit être une fonction de type ℤ →.
Martin Ender
1
@Bijan à la fois positif et négatif.
Martin Ender

Réponses:

18

Python, 68 caractères

f=lambda x:(1-x%2*2)*(2*x*x+(x<0))
g=lambda x:(1-x%2*2)*(2*x*x+(x>0))

f mappe les nombres négatifs sur les nombres impairs et les nombres positifs sur les nombres pairs, et les nombres pairs sur les nombres positifs et les nombres impairs sur les nombres négatifs, l'amplitude de sortie augmentant strictement avec l'amplitude d'entrée.

g fait la même chose, sauf qu'il mappe les nombres négatifs aux nombres pairs et les nombres positifs aux nombres impairs.

f maps g cartes négatives → même → positives et positives → impaires → négatives.
g ∘ f correspond négativement → impair → négatif et positif → même → positif.

Par conséquent, f et g ont les propriétés souhaitées.

utilisateur1502040
la source
2
fet gpeuvent être des fonctions non nommées, vous pouvez donc supprimer quatre octets.
Martin Ender
Vous pouvez définir (1-x%2*2)une variable pour économiser quelques octets.
OldBunny2800
Voici un code complet pour jouer avec import numpy as np; import matplotlib.pyplot as plt; xrange=np.arange(-3,4); f=lambda x:(1-x%2*2)*(2*x*x+(x<0)); g=lambda x:(1-x%2*2)*(2*x*x+(x>0)); plt.plot(xrange, map(f, xrange), 'ro'); plt.plot(xrange, map(g, xrange), 'go'); plt.plot(xrange, map(f, map(g, xrange)), 'b--'); plt.plot(xrange, map(g, map(f, xrange)), 'y--'); plt.show(); Vous pouvez remplacer ;par des sauts de ligne pour la lisibilité.
Stéphane Gourichon
16

Python , 40 octets

f=lambda x:x*(-1)**x
g=lambda x:3*f(x)+1

Essayez-le en ligne! Certaines sorties sont des flottants égaux à des entiers car ils (-1)**(-3)donnent un flottant par exemple.

Basé sur des idées de Peter Taylor . La fonction fannule les nombres impairs et laisse les mêmes inchangés. La fonction gfait la même chose, puis applique la carte monotone à commutation de parité x -> 3*x + 1.

Depuis f(f(x)) = x, nous avons de g(f(x)) = 3*f(f(x))+1 = 3*x+1plus en plus.

Car f(g(x)) = f(3*f(x)+1), l’idée est que l’un des fsignes de retournement intérieur et extérieur est exactement ce qui le rend décroissant.

  • Pour même x, f(x) = xmais f(3*x+1) = -3*x-1parce que 3*x+1c'est étrange.
  • Pour impair x, f(x) = -xet f(-3*x+1) = -3*x+1parce que -3*x+1est pair.

Nous avons maintenant besoin que les entrées paires et impaires s'entrelacent de manière décroissante, ce qui est -3*x±1vrai car décroît quelle que soit la manière dont les signes sont choisis. C'est pourquoi le 3*nécessaire.

Un port Haskell est 25 octets:

f x=x*(-1)**x
g x=1+3*f x

Essayez-le en ligne!

Xnor
la source
En Haskell, (^)correspond à une exponentiation entière.
user1502040
1
@ user1502040 Il ne peut pas gérer les exposants négatifs.
xnor
1
Puisque vous ne gvous appelez pas vous-même, vous pouvez économiser deux octets en le rendant non nommé.
Martin Ender
14

CJam (17 octets)

Fonction f (nommée Fparce que CJam n'autorise que les noms en majuscule):

{W1$2b,#*}:F

Fonction g (anonyme):

{F2*}

Démo en ligne

Cela économise un octet en s’appuyant sur un détail d’implémentation de CJam, qui est sans doute un bogue: lors de conversions de base, il utilise une valeur absolue. 2b,donne donc le nombre de bits dans la valeur absolue de son argument, donc f inverse précisément les nombres dont la valeur absolue a un nombre impair de bits. g applique f puis double (modification de la parité du nombre de bits).

Donc, appliquer f puis g laisse le signe inchangé et double, en mappant xsur 2x. Appliquer g, puis f change le signe exactement une fois et double, en mappant xsur -2x.

Peter Taylor
la source
Nice, c’est exactement la solution de référence proposée dans le cadre de la compétition. (Je suppose que vous l'avez inventé de manière indépendante?)
Martin Ender
@MartinEnder, j'ai déjà vu ce problème quelque part. Peut-être sur math.SE.
Peter Taylor
2

Pyth, 34 octets

Ceci est juste une traduction directe de ma réponse en Python.

*-1*2%Q2+*2*QQ<Q0
*-1*2%Q2+*2*QQ>Q0
utilisateur1502040
la source