Pregunta Diseño de la función f (f (n)) == -n [cerrado]


Una pregunta que obtuve en mi última entrevista:

Diseña una función f, tal que:

f(f(n)) == -n

Dónde n es un 32 bit entero firmado; no puedes usar aritmética de números complejos.

Si no puede diseñar dicha función para todo el rango de números, diseñe para el rango más amplio posible.

¿Algunas ideas?


836


origen


Respuestas:


Qué tal si:

f (n) = signo (n) - (-1)norte * 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 promueve automáticamente enteros a longitudes de longitud arbitrarias. En otros idiomas, el número entero positivo más grande se desbordará, por lo que funcionará para todos los enteros excepto ese.


Para que funcione con números reales, debe reemplazar el norte En 1)norte con { ceiling(n) if n>0; floor(n) if n<0 }.

En C # (funciona para cualquier doble, excepto en situaciones de desbordamiento):

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



No dijiste qué tipo de lenguaje esperaban ... Aquí hay una solución estática (Haskell). Básicamente está jugando con los 2 bits más significativos:

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

Es mucho más fácil en un lenguaje dinámico (Python). Solo verifica si el argumento es un número X y devuelve un lambda que arroja -X:

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

439



Aquí hay una prueba de por qué dicha función no puede existir, para todos los números, si no utiliza información adicional (excepto 32 bits de int):

Debemos tener f (0) = 0. (Prueba: supongamos que f (0) = x. Entonces f (x) = f (f (0)) = -0 = 0. Ahora, -x = f (f (x) )) = f (0) = x, lo que significa que x = 0.)

Además, para cualquier x y y, supongo f(x) = y. Queremos f(y) = -x entonces. Y f(f(y)) = -y => f(-x) = -y. Para resumir: si f(x) = y, entonces f(-x) = -yy f(y) = -xy f(-y) = x.

Entonces, necesitamos dividir todos los enteros excepto 0 en conjuntos de 4, pero tenemos un número impar de tales enteros; no solo eso, si eliminamos el entero que no tiene una contrapartida positiva, todavía tenemos 2 (mod4) números.

Si eliminamos los 2 números máximos restantes (por valor de abs), podemos obtener la función:

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

Por supuesto, otra opción es no cumplir con 0 y obtener los 2 números que eliminamos como bonificación. (Pero eso es solo una tontería si)


280



Gracias a la sobrecarga 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



O bien, podría abusar del preprocesador:

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

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

135



Esto es cierto para todos los números negativos.

    f (n) = abs (n)

Debido a que hay un número negativo más que números positivos para dos números enteros, f(n) = abs(n) es válido para un caso más que f(n) = n > 0 ? -n : n solución que es la misma que f(n) = -abs(n). Te tengo por uno ...: D

ACTUALIZAR

No, no es válido para un caso más ya que acabo de reconocer por el comentario de litb ... abs(Int.Min) se desbordará ...

Pensé en usar también la información de mod 2, pero concluí, no funciona ... hasta temprano. Si se hace bien, funcionará para todos los números excepto Int.Min porque esto se desbordará

ACTUALIZAR

Jugué con él por un tiempo, buscando un buen truco de manipulación, pero no pude encontrar un buen trazador de líneas, mientras que la solución de mod 2 cabe en uno.

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

En C #, esto se convierte en lo siguiente:

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

Para que funcione para todos los valores, debe reemplazar Math.Abs() con (n > 0) ? +n : -ne incluir el cálculo en una unchecked bloquear. Entonces, consigues incluso Int.Min mapeado a sí mismo como la negación no verificada sí lo hace.

ACTUALIZAR

Inspirado por otra respuesta, voy a explicar cómo funciona la función y cómo construir dicha función.

Comencemos desde el principio La función f se aplica repetidamente a un valor dado n produciendo una secuencia de valores.

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

La pregunta exige f(f(n)) = -n, eso es dos aplicaciones sucesivas de f negar el argumento Dos aplicaciones adicionales de f - cuatro en total - niega el argumento de nuevo cediendo n de nuevo.

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

Ahora hay un ciclo obvio de longitud cuatro. Sustituyendo x = f(n) y observando que la ecuación obtenida f(f(f(n))) = f(f(x)) = -x contiene, cede lo siguiente.

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

Entonces obtenemos un ciclo de longitud cuatro con dos números y los dos números negados. Si imagina el ciclo como un rectángulo, los valores negados se ubican en esquinas opuestas.

Una de las muchas soluciones para construir dicho ciclo es la siguiente a partir de n.

 n => negar y restar uno
-n - 1 = - (n + 1) => agregar uno
-n => negar y agregar uno
 n + 1 => restar uno
 norte

Un ejemplo concreto de tal ciclo es +1 => -2 => -1 => +2 => +1. Casi terminamos. Observando que el ciclo construido contiene un número positivo impar, su sucesor par y ambos números niegan, podemos dividir fácilmente los números enteros en muchos de esos ciclos (2^32 es un múltiplo de cuatro) y ha encontrado una función que satisface las condiciones.

Pero tenemos un problema con cero. El ciclo debe contener 0 => x => 0 porque cero se niega a sí mismo. Y porque el ciclo ya indica 0 => x sigue 0 => x => 0 => x. Este es solo un ciclo de longitud dos y x se convierte en sí mismo después de dos aplicaciones, no en -x. Afortunadamente hay un caso que resuelve el problema. Si X es igual a cero obtenemos un ciclo de longitud uno que contiene solo cero y resolvimos ese problema concluyendo que cero es un punto fijo de f.

¿Hecho? Casi. Tenemos 2^32 números, cero es un punto fijo que se va 2^32 - 1 números, y debemos dividir ese número en ciclos de cuatro números. Mal que 2^32 - 1 no es un múltiplo de cuatro; permanecerán tres números, no en ningún ciclo de cuatro.

Explicaré la parte restante de la solución usando el conjunto más pequeño de iteradores con signo de 3 bits que van desde -4 a +3. Hemos terminado con cero. Tenemos un ciclo completo +1 => -2 => -1 => +2 => +1. Ahora construyamos el ciclo comenzando en +3.

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

El problema que surge es que +4 no es representable como un entero de 3 bits. Obtendríamos +4 negando -3 a +3 - lo que aún es un número entero de 3 bits válido - pero luego agregar uno a +3 (binario 011) rendimientos 100binario. Interpretado como entero sin signo es +4 pero tenemos que interpretarlo como un entero con signo -4. Entonces en realidad -4 para este ejemplo o Int.MinValue en el caso general es un segundo punto fijo de negación aritmética entera - 0  y Int.MinValue están mapeados a themselve. Entonces el ciclo es en realidad el siguiente.

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

Es un ciclo de longitud dos y adicionalmente +3 ingresa al ciclo a través de -4. En consecuencia -4 se asigna correctamente a sí mismo después de dos aplicaciones de función, +3 está correctamente asignado a -3 después de dos aplicaciones de función, pero -3 se asigna erróneamente a sí mismo después de dos aplicaciones de función.

Entonces, construimos una función que funciona para todos los enteros menos uno. ¿Podemos hacerlo mejor? No podemos. ¿Por qué? Tenemos que construir ciclos de longitud cuatro y podemos cubrir todo el rango entero hasta cuatro valores. Los valores restantes son los dos puntos fijos 0 y Int.MinValue que debe asignarse a sí mismos y dos enteros arbitrarios x y -x que deben ser mapeados entre sí por dos aplicaciones de funciones.

Para asignar x a -x y viceversa, deben formar un ciclo de cuatro y deben estar ubicados en las esquinas opuestas de ese ciclo. En consecuencia 0 y Int.MinValue tiene que estar en las esquinas opuestas, también. Esto mapeará correctamente x y -x pero intercambia los dos puntos fijos 0 y Int.MinValue después de dos aplicaciones de función y nos deja con dos entradas que fallan. Por lo tanto, no es posible construir una función que funcione para todos los valores, pero tenemos uno que funciona para todos los valores, excepto uno, y esto es lo mejor que podemos lograr.


103



Usando números complejos, puedes dividir efectivamente la tarea de negar un número en dos pasos:

  • multiplica n por i, y obtienes n * i, que se gira n 90 ° en sentido antihorario
  • multiplicar nuevamente por i, y obtienes -n

Lo mejor es que no necesita ningún código de manejo especial. Solo multiplicar por i hace el trabajo.

Pero no puedes usar números complejos. De modo que debe crear de algún modo su propio eje imaginario, usando parte de su rango de datos. Como necesita exactamente tantos valores imaginarios (intermedios) como valores iniciales, solo queda la mitad del rango de datos.

Traté de visualizar esto en la siguiente figura, asumiendo datos de 8 bits firmados. Tendría que escalar esto para enteros de 32 bits. El rango permitido para n inicial es -64 a +63. Esto es lo que hace la función para n positivo:

  • Si n está en 0..63 (rango inicial), la llamada de función agrega 64, mapeando n al rango 64..127 (rango intermedio)
  • Si n está en 64..127 (rango intermedio), la función resta n de 64, mapeando n al rango 0 ..- 63

Para n negativo, la función usa el rango intermedio -65 ..- 128.

alt text


96



Funciona excepto int.MaxValue e 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 pregunta no dice nada sobre el tipo de entrada y el valor de retorno de la función f tiene que ser (al menos no de la manera que lo has presentado) ...

... solo que cuando n es un entero de 32 bits, entonces f(f(n)) = -n

Entonces, ¿qué tal algo así como

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

Si n es un entero de 32 bits, entonces la declaración f(f(n)) == -n será cierto

Obviamente, este enfoque podría extenderse para funcionar para un rango aún más amplio de números ...


48



para javascript (u otros lenguajes tipados dinámicamente) puede hacer que la función acepte un int o un objeto y devuelva el otro. es decir

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

dando

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

alternativamente, puede usar la sobrecarga en un lenguaje fuertemente tipado, aunque eso puede romper las reglas, es decir,

int f(long n) {
    return n;
}

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

47