Se dice que una función tiene un ciclo de longitud n si existe una x en su dominio tal que f n (x) = x y f m (x) ≠ x para 0 <m <n , donde el superíndice n denota n - pliegue la aplicación de f . Tenga en cuenta que un ciclo de longitud 1 es un punto fijo f (x) = x .
Su tarea es implementar una función biyectiva de los enteros a sí mismos, que tiene exactamente un ciclo de cada longitud positiva n . Una función biyectiva es una correspondencia uno a uno, es decir, cada entero asignado exactamente a una vez. Tener exactamente un ciclo de longitud n significa que hay exactamente n números distintos x para los cuales f n (x) = x y f m (x) ≠ x para 0 <m <n .
Aquí hay un ejemplo de cómo se vería tal función alrededor de x = 0 :
x ... -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ...
f(x) ... 2 4 6 -3 -1 1 -4 0 -2 5 7 -7 -6 3 -5 ...
Este extracto contiene ciclos de longitud 1 a 5 :
n cycle
1 0
2 -2 1
3 -4 -3 -1
4 -5 6 3 7
5 -7 2 5 -6 4
...
Tenga en cuenta que anteriormente estoy usando "función" solo en el sentido matemático. Puede escribir una función o un programa completo en el idioma que elija, siempre que tome un solo entero (con signo) como entrada y devuelva un solo entero (con signo). Como de costumbre, puede recibir información a través de STDIN, argumento de línea de comando, argumento de función, etc. y salida a través de STDOUT, valor de retorno de función o argumento de función (fuera), etc.
Por supuesto, muchos idiomas no admiten (fácilmente) enteros de precisión arbitraria. Está bien si su implementación solo funciona en el rango del tipo de entero nativo de su idioma, siempre que cubra al menos el rango [-127, 127] y que funcione para enteros arbitrarios si el tipo de entero del idioma se reemplaza por arbitrario- enteros de precisión.
Se aplican reglas estándar de código de golf .
fuente
Respuestas:
Pyth,
2718 bytesExplicación (Pyth se inicializa
Q
al entero de entrada):Esto tiene ciclos
(−1)
(0, −2)
(1, −3, −4)
(2, −5, −7, −6)
(3, −9, −13, −11, −8)
(4, - 17, -25, -21, -15, -10)
(5, -33, -49, -41, -29, -19, -12)
(6, -65, -97, -81, -57, −37, −23, −14)
(7, −129, −193, −161, −113, −73, −45, −27, −16)
(8, −257, −385, −321, −225 , −145, −89, −53, −31, −18)
(9, −513, −769, −641, −449, −289, −177, −105, −61, −35, −20)
⋮
El ciclo de longitud n viene dado por
( n - 2,
−2 ^ ( n - 2) ⋅1 - 1,
−2 ^ ( n - 3) ⋅3 - 1,
−2 ^ ( n - 4) ⋅5 - 1,
…,
−2 ^ 2 ⋅ (2 · n - 7) - 1,
−2 ^ 1⋅ (2 · n - 5) - 1,
−2 ^ 0⋅ (2 · n - 3) - 1).
Cada número entero k ≥ −1 aparece como el primer elemento del ciclo ( k + 2). Para cada entero k <−1, podemos escribir de forma única 1 - k = 2 ^ i ⋅ (2⋅ j + 1) para algunos i , j ≥ 0; entonces k aparece como el elemento ( j + 2) th del ciclo ( i + j + 2).
fuente
MATL , 47 bytes
Pruébalo en línea!
Explicación general
La función 2 a continuación es la misma que la utilizada en la respuesta de @ Sp3000 al desafío relacionado. Gracias a @ Agawa001 por notarlo.
La función es la composición de tres:
Funciones 1 y 3 se utilizan porque es más fácil (creo) para conseguir el comportamiento deseado en N que en Z .
La función 2 es la siguiente: la línea superior es dominio, la línea inferior es codominio. Las comas se usan para mayor claridad:
El primer bloque (de arriba
1
a abajo1
) es un ciclo de longitud 1. El segundo (de2 3
a3 2
) es un ciclo de longitud 2, etc. En cada bloque, la parte inferior (imagen de la función) es la parte superior desplazada circularmente Un paso a la derecha.La función 1 es la siguiente:
La función 3 es la misma que 1 con las dos líneas intercambiadas.
Ejemplos
La imagen de
3
es-5
. Primero3
se asigna a la7
función 1; luego7
se asigna a la10
función 2; luego10
se asigna a -5` por la función 3.El ciclo de longitud-1 es
0
. El ciclo de longitud 2 es-1 1
. El ciclo de longitud 3 es-3 2 -2
, etc.Código explicado
Las funciones 1 y 3 son sencillas.
La función 2 funciona al encontrar el punto final inferior del bloque de entrada correspondiente. Por ejemplo, si la entrada a esta función es
9
encontrar7
(ver bloques más arriba). Luego selecciona el punto final superior, que está10
en el ejemplo. El desplazamiento circular del bloque se logra gracias a la indexación modular basada en 1 de MATL.fuente
Python 2, 55 bytes
59 bytes:
Crea los ciclos.
Modificado de mi solución en el desafío anterior , que se modificó desde la construcción de Sp3000 .
La función
realiza ciclos de números impares de números no negativos
Para encontrar el tamaño de ciclo correcto
k
, desplace la entradan
hacia abajok=1,3,5,7,...
hasta que el resultado esté en el intervalo[0,k)
. Ciclo este intervalo con la operaciónn->(n+1)%k
, luego deshacer todas las sustracciones realizadas en la entrada. Esto se implementa de forma recursiva pork+g(n-k,k+2)
.Ahora, necesitamos lo negativo para hacer los ciclos pares. Tenga en cuenta que si modificamos
g
para empezark=2
eng
, nos gustaría llegar ciclos, incluso de tamañoEstos biject a negativos a través de bits de complemento
~
. Entonces, cuandon
es negativo, simplemente evaluamosg(n)
como~g(~n,2)
.fuente
k
parece ser otra forma de calcularMath.floor(Math.sqrt(n))*2+1
.Python 3, 110 bytes
Todavía no he descubierto cómo poner una lambda allí
si n es un número de triángulo [1,3,6,10,15,21,28, etc ...] entonces f (n) es el orden en la lista multiplicado por uno negativo. Si el número es negativo, dele 1 + el siguiente número de triángulo más pequeño. De lo contrario, incremente.
Ejemplo: 5 no es un número de triángulo, así que suma 1.
Próxima iteración, tenemos 6. 6 es un número de triángulo, y es el tercero en la lista, así que sale -3.
El programa da estas listas
longitud 1: [0]
longitud 2: [1, -1]
longitud 3: [2,3, -2]
longitud 4: [4,5,6, -3]
longitud 5: [7,8,9,10, -4]
Editar: Gracias de nuevo a @TuukkaX por eliminar el exceso de caracteres.
fuente
0.5
a.5
yinput('')
ainput()
.Python 3, 146 bytes
Para cada número mayor que 0, hay bucles pares (len 2,4,6,8 ...), y menos que 0, bucles impares (1,3,5,7). 0 mapas a 0.
(-3, -2, -1), (0), (1,2), (3,4,5,6)
mapas a
(-2, -1, -3), (0), (2,1), (6,3,4,5)
Editar: @TuukkaX despegó 8 bytes de la solución anterior. Y otros 3.
fuente
mi
podría cambiarse a algo más pequeño, comob
.f=lambda x:1+2*int(abs(x)**0.5)if x<1 else 2*int(x**0.5+0.5) x=int(input()) n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
input('')
ainput()
. Las comillas son inútiles ya que no tenemos que imprimir nada en la consola cuando solo queremos obtener la entrada.f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5) x=int(input());n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
Matlab (423)
No competir porque rompe un buen récord de estar en condiciones para la última clasificación, mientras lucho por acortarlo lo más posible.
Algunos errores no sensitivos relacionados con la precisión en matlab que no pude encontrar ninguna salida, excepto hacer mi código sarcásticamente grande, por otro lado, el mapeo que opté fue en términos de factores principales y logaritmo n-ary.
Ejecución
Explicación
Teniendo en cuenta, en primer lugar, que cualquier número puede escribirse como producto de exponentes de primos
N=e1^x1*e2^x2...
de esta base. Elegí mapear imágenes de ciclosC
que se extraen del mayor exponente del factor más pequeño (no necesariamente primo) de que N es una potencia perfecta de .en palabras más simples, sea
N=P^x
donde P es la raíz perfecta más pequeña,x
denota precisamente dos términos esenciales para el ciclo:x=Ʃ(r*P^i)
un términoP
es la base del ciclo y también una raíz perfecta para el número principal N, yk
es el grado del cicloC=p^k
, dondei
varía entre 1 yk, el coeficienter
se incrementa en 1 y se limita por P-1 para cualquier preimagen siguiente hasta que todos los coeficientes se establezcan en r = 1, por lo que nos movemos al inicio de ese ciclo.Para evitar colisiones entre ciclos, la elección de la exponenciación de los primos en lugar de sus productos es precisa, porque como ejemplo de dos ciclos de bases
3
y2
un punto de encuentro entre ellos, puede3*2
evitarse ya que un ciclo se define por su grado más que su base, y para el punto de encuentro hay otro ciclo de base6
y grado 1.Los números negativos colocan una excepción, en cuanto a esto, reservé grados impares para números negativos, y grados pares para el resto. Cómo es eso ?
para cualquier número N incrustado dentro de un ciclo
P^k
, se escribe comoP^(a0*P^i0+a1*P^i1+...)
, la cantidad(a0*P^i0+a1*P^i1+...)
se traduce en base P-aria comoa0,a1,....
, para aclarar este punto si (p = 2) la secuencia debe estar en base binaria. Como se sabe prealably sin establecer la condición de grados positivos / negativos y la excepción (+/- 1), un número N está en los bordes de un ciclo de gradosk
si y solo si la secuenciaA
se escribe como1111..{k+1}..10
o111..{k}..1
para todas las bases, de lo contrario no se necesita rotación, por lo tanto, la asignación de una condición negativa / positiva para los respectivos grados pares / imparesk/k'
para ambos hace una secuencia impar escrita en la forma101..{k}..100
, una secuencia par se escribe en la forma101..{k'}..10
para un borde inicial de un ciclo numérico negativo / positivo respectivamente .Ejemplo:
Tomando un número
N=2^10
,x=10=2^1+2^3
se escribe la secuencia AA=1010
, este tipo de secuencia es sintomática de un borde finito del ciclo numérico positivoC=2^3
, por lo que la siguiente imagen es la del borde inicial,A=011
que es8
, Pero , al estandarizar este resultado a (+ / -) 1 excepción se2^10/2
asigna8/2
y la imagen anterior no debe rotarse.Tomando un número
N=-3^9
,x=9=3^2
se escribe la secuencia AA=100
, este tipo de secuencia sintomatiza un borde finito del ciclo numérico negativoC=3^1
, por lo que la siguiente imagen es la del borde inicial,A=01
que es3
, pero, al adaptar este resultado a negativo / positivo-3^9
mapas de condición a-3
.para la pareja
(-/+)1
, pensé en introducirlo dentro de un número de bases2
cíclicas, con el pretexto de que una secuencia ordinaria de grupos cíclicos{2,4}{8,16,32,64}..
está formada de otra forma{1,2}{4,8,16,32}..
, esto evita cualquier pérdida de elementos anteriores, y la operación realizada solo está cambiando con estallidos un nuevo elemento enResultados:
ejecutando esta pequeña hoja de códigos para verificar los primeros rangos razonables de números cíclicos:
Esto lleva a estos resultados
El último es el error de segmentación, pero se ajusta al rango de entero con signo estándar [-127,127].
fuente
JavaScript (ES6), 73 bytes
Funciona enumerando la secuencia (0, -1, 1, -2, 2, -3, 3, ...) hasta que encuentra
n
, contando los ciclos a medida que avanza.i
contiene la entrada actual;j
contiene el inicio del ciclo actual,k
el índice dentro del ciclo,l
la duración del ciclo actual ym
la siguiente entrada en la secuencia. Una vez que encontramosn
, tomamosj
si estamos al final de un ciclo om
si no.fuente