f (g (x)) disminuye mientras que g (f (x)) aumenta

42

Para este desafío, debe implementar dos funciones, f y g , en los enteros, de modo que f ∘ g sea ​​una función estrictamente decreciente, mientras que g ∘ f sea ​​una función estrictamente creciente. En otras palabras, si toma dos enteros a <b , entonces f (g (a))> f (g (b)) y g (f (a)) <g (f (b)) . No existen restricciones para f y g individualmente, excepto que cada uno debe mapear un entero a otro entero.

Incluya una breve descripción de f y gy un argumento de por qué tienen la propiedad requerida.

Crédito: Este desafío fue inspirado por un problema en la competencia rumana de Maestría en Matemáticas de 2011 (que pregunta lo mismo pero sobre los números reales, en lugar de los enteros). Si realmente quieres spoilers, ahora sabes qué buscar.

Reglas

  • La palabra "función" en este desafío debe tomarse en el sentido matemático de mapear un número entero a otro: puede escribir dos programas o dos funciones y usar cualquiera de los métodos estándar para recibir entradas y proporcionar salidas, como de costumbre. Puede usar representaciones de cadenas de enteros en lugar de variables enteras reales, pero los tipos de entrada y salida deben ser idénticos, de modo que las funciones se puedan componer sin convertir manualmente los tipos intermedios. Recuerde que conceptualmente, f y g todavía deben ser funciones en ℤ, por lo que no puede hacer trampa usando dos representaciones de cadena diferentes del mismo número o algo así.

  • Recuerde que las funciones pueden no tener nombre , siempre que su nombre no sea necesario por sí mismo o por otra función que defina. Si nombra una o ambas funciones, puede suponer que existen en el mismo programa, para que puedan referirse entre sí en su implementación (por ejemplo, def f(x): return -g(x)en Python).

  • Se aplican las reglas habituales de desbordamiento de enteros: su solución debe poder funcionar para enteros arbitrariamente grandes en una versión hipotética (o tal vez real) de su idioma en la que todos los enteros están ilimitados de forma predeterminada, pero si su programa falla en la práctica debido a la implementación no admite enteros tan grandes, eso no invalida la solución.

  • Puede usar cualquier lenguaje de programación , pero tenga en cuenta que estas lagunas están prohibidas de forma predeterminada.

  • Este es el , por lo que su puntaje es la suma del número de bytes de ambas funciones y gana la respuesta válida más corta.

Martin Ender
fuente
¿Pueden las funciones devolver una cadena?
Matthew Roh el
@SIGSEGV Yo diría que sí, pero solo si también toman una cadena como entrada, para que puedan componerse sin tener que insertar ningún tipo de conversión.
Martin Ender
Aww darnit, intenté la conversión a cadena para que la otra función no pueda editar más los resultados.
Matthew Roh el
1
@Fatalize Correcto. Cada uno debe ser una función de tipo ℤ → ℤ.
Martin Ender
1
@Bijan tanto positivo como negativo.
Martin Ender

Respuestas:

18

Python, 68 caracteres

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 asigna números negativos a números impares y números positivos a números pares, y números pares a números positivos y números impares a números negativos, con la magnitud de salida aumentando estrictamente con la magnitud de entrada.

g hace lo mismo, excepto que asigna números negativos a números pares y números positivos a números impares.

f ∘ g asigna negativo → par → positivo y positivo → impar → negativo.
g ∘ f asigna negativo → impar → negativo y positivo → par → positivo.

Por lo tanto, fyg tienen las propiedades deseadas.

user1502040
fuente
2
fy gpueden ser funciones sin nombre, por lo que puede eliminar cuatro bytes.
Martin Ender
Puede definir (1-x%2*2)como una variable para guardar unos pocos bytes.
OldBunny2800
Aquí hay un código completo para jugar 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(); . Puede reemplazarlo ;con saltos de línea para facilitar la lectura.
Stéphane Gourichon
16

Python , 40 bytes

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

Pruébalo en línea! Algunas salidas son flotantes que equivalen a enteros porque (-1)**(-3)da una flotante, por ejemplo.

Basado en ideas de Peter Taylor . La función fniega los números impares y deja los pares sin cambios. La función ghace lo mismo, luego aplica el mapa monotónico de cambio de paridad x -> 3*x + 1.

Desde entonces f(f(x)) = x, tenemos g(f(x)) = 3*f(f(x))+1 = 3*x+1cada vez más.

Para f(g(x)) = f(3*f(x)+1), la idea es que exactamente uno de los fflips signo interno y externo , disminuyendo.

  • Por par x, f(x) = xpero f(3*x+1) = -3*x-1porque 3*x+1es extraño.
  • Por extraño x, f(x) = -xy f(-3*x+1) = -3*x+1porque -3*x+1es par.

Ahora solo necesitamos que las entradas pares e impares se intercalen de manera decreciente, lo que se cumple porque -3*x±1está disminuyendo independientemente de cómo se elijan los signos. Es por eso que 3*se necesita.

Un puerto Haskell tiene 25 bytes:

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

Pruébalo en línea!

xnor
fuente
En Haskell, (^)es la exponenciación de enteros.
user1502040
1
@ user1502040 No puede manejar exponentes negativos.
xnor
1
Como no se llama a gsí mismo, puede guardar dos bytes al dejarlo sin nombre.
Martin Ender
14

CJam (17 bytes)

Función f (nombrada Fporque CJam solo permite nombres en mayúsculas):

{W1$2b,#*}:F

Función g (anónimo):

{F2*}

Demostración en línea

Esto ahorra un byte al confiar en un detalle de implementación de CJam que posiblemente sea un error: cuando realiza conversiones de base, utiliza un valor absoluto. 2b,por lo tanto, da el número de bits en el valor absoluto de su argumento, por lo que f niega precisamente aquellos números cuyo valor absoluto tiene un número impar de bits. g aplica f y luego se duplica (cambiando la paridad del número de bits).

Entonces, aplicar fy luego g deja el signo sin cambios y se duplica, asignando xa 2x. Aplicando gy luego f cambia el signo exactamente una vez y se duplica, asignando xa -2x.

Peter Taylor
fuente
Bien, esta es exactamente la solución de referencia proporcionada en la competencia de la que proviene. (¿Asumo que se te ocurrió de forma independiente?)
Martin Ender
@ MartinEnder, he visto este problema en alguna parte antes. Posiblemente en matemáticas.
Peter Taylor
2

Pyth, 34 bytes

Esta es solo una traducción directa de mi respuesta de Python.

*-1*2%Q2+*2*QQ<Q0
*-1*2%Q2+*2*QQ>Q0
user1502040
fuente