Definición
a(0) = 0
a(n) = n-a(a(a(n-1)))
para enteron > 0
Tarea
Dado entero no negativo n
, salida a(n)
.
Casos de prueba
n a(n)
0 0
1 1
2 1
3 2
4 3
5 4
6 4
7 5
8 5
9 6
10 7
11 7
12 8
13 9
14 10
15 10
16 11
17 12
18 13
19 13
20 14
10000 6823
Referencias
code-golf
sequence
number-theory
recursion
Monja permeable
fuente
fuente
Respuestas:
Haskell
2322 bytesSimplemente usa la definición de la secuencia.
f(f$f$n-1)
es equivalente af (f (f (n-1)))
.Prueba:
¡Gracias a Anders Kaseorg por un byte!
fuente
(f$f$f$n-1)
=f(f$f$n-1)
guarda un byte.Jalea , 8 bytes
Pruébalo en línea! o verificar los casos de prueba más pequeños .
Cómo funciona
fuente
Mathematica, 20 bytes
El recuento de bytes asume la codificación ISO 8859-1 (o compatible) y se
$CharacterEncoding
establece en un valor coincidente, como el valor predeterminado de WindowsWindowsANSI
.Esto define un operador unario
±
.fuente
PlusMinus
. Ver esta publicación para más detalles.@
o[ ]
también.J,
1412 bytesGuardado 2 bytes gracias a @ Leaky Nun .
Calcula el resultado llamándose recursivamente cuando n > 0 tres veces en n -1 y restando ese resultado de n . Hay una situación diferente para el caso base cuando n = 0. Allí se calcula n - n que es igual a 0.
Pruébalo aquí.
Explicación
fuente
Julia, 16 bytes
Pruébalo en línea!
Cómo funciona
Redefinimos el operador unario
!
para nuestros fines.Si n = 0 , la comparación
n>0
devuelve falso y también lo hace!
.De lo contrario, el código después
&&
se ejecuta.~-n
es equivalente al(n-1)
complemento de dos,!!!
recursivamente llama!
tres veces en n - 1 , y el valor resultante se resta de n .fuente
-!!~-
._.!
es simplemente el nombre de la función.Python, 31 bytes
El límite de recursión y las limitaciones de tiempo hacen que la función anterior no sea práctica, pero en teoría debería funcionar (y funciona para n pequeña).
fuente
JavaScript (ES6), 52 bytes
Podría haber sido aburrido y haber escrito la versión recursiva, pero esta versión es mucho más rápida (maneja fácilmente el último caso de prueba) y también usa
reduce
eso es una ventaja!fuente
Retina ,
4943 bytesPruébalo en línea!
fuente
CJam,
1312 bytesGracias a Dennis por guardar 1 byte.
Pruébalo aquí.
fuente
a
.R,
4241 bytesUso:
Sin embargo, este enfoque recursivo no escala bien para valores mayores de
n
.fuente
n<1
. Como es una secuencia, de todos modos solo se define realmente para enteros no negativos.a=function(n)"if"(n,n-a(a(a(n-1))),0)
funcionará para varios bytes de descuento.Oasis , 6 bytes
Código:
Versión ampliada:
Código:
Pruébalo en línea!
fuente
Sesos ,
5855 bytesManeja entradas de hasta 400 razonablemente bien, pero el tiempo de ejecución aumenta dramáticamente después de ese punto.
Pruébalo en línea! Verifique la depuración para ver el código SBIN generado.
Asamblea Sesos
El archivo binario anterior se generó al ensamblar el siguiente código SASM.
fuente
LISP, 61 bytes
Probablemente no sea la solución óptima, pero funciona.
fuente
Java 7, 42 bytes
Sin golf y casos de prueba:
Pruébalo aquí.
Salida:
fuente
Rubí, 27 bytes
La implementación obvia.
Esta es una respuesta más larga y rápida que almacena en caché las entradas anteriores de la secuencia. Ambas respuestas solo funcionan para versiones posteriores a 1.9, ya que fue cuando
->
, la lambda stabby, fue presentada a Ruby.fuente
C #, 35 bytes
fuente
Golfscript,
2625 bytesPruébalo en línea!
Localmente
10000
toma menos de medio segundo.fuente
C,
3532 bytes¡Guardado 3 bytes gracias a @PeterTaylor!
Pruébalo en Ideone!
fuente
a(n){return n?n-a(a(a(n-1))):0;}
:
código erróneo . Deberías sacar el que está después?
.Javascript ES6, 22 bytes
Seré aburrido y haré la versión recursiva: P
fuente
VBA, 69 bytes
Funciona en un abrir y cerrar de ojos en el conjunto de prueba, se ralentiza un poco por encima de n = 1000000, se encuentra con un muro de memoria un poco por encima de n = 25 millones.
fuente
Pyth, 10 bytes
Define una función
y
. Pruébelo en línea: demostraciónEsto usa una característica relativamente nueva de Pyth. Puede aplicar una función varias veces utilizando la sintaxis de plegado. En realidad no guarda ningún byte, lo usé solo con fines de demostración.
Explicación:
fuente
Arce,
2826 bytesUso:
fuente
cc, 34 bytes
La entrada se toma desde la parte superior de la pila. Este debe ser el único elemento en la pila, porque la profundidad de la pila se usa como contador. Ejemplo de uso:
Esta es una implementación bastante sencilla de la definición de secuencia:
De todos modos, comenzó de forma directa ... luego ocurrió el golf.
fuente
Lisp común , 44 bytes
Pruébalo en línea!
fuente
C ++ (MSVC, principalmente)
Versión normal: 40 bytes.
Versión de meta programación de plantilla: 130 bytes
Uso:
La versión de la plantilla es el código más rápido, ya que no hay nada más rápido que mover un valor a un registro => con optimización,
H<20>::a()
compilar como:Para 10000, la versión recursiva se bloquea debido a un error de desbordamiento de pila, y la versión de la plantilla se bloquea en tiempo de compilación debido a la profundidad de creación de instancias de la plantilla. GCC va a 900 (614)
fuente
C
y{
en la versión de meta programación de la plantillaD , 36 bytes
Pruébalo en línea!
fuente
APL (Dyalog Unicode) ,
1817 bytesPruébalo en línea!
Sorprendentemente, no hay una respuesta APL a este desafío. Esta es una implementación literal de la función en el OP.
TIO agota el tiempo de esperan > 90 .
Guardado un byte gracias a @ Zacharý.
fuente
{⍵=0:0⋄⍵-∇⍣3⊢⍵-1}
Python 3, 72 bytes
Ideone it!
fuente
PowerShell v2 +, 56 bytes
El equivalente de PowerShell de una lambda para formar la definición recursiva. Ejecútelo a través del
&
operador de llamada, por ejemplo&$a(5)
. Toma mucho tiempo tiempo en ejecutarse, incluso50
en mi máquina (un i5 reciente con 8GB de RAM) toma alrededor de 90 segundos.Solución iterativa más rápida, 59 bytes.
Más tiempo solo porque necesitamos tener en cuenta la entrada
0
(eso es*!!$n
al final). De lo contrario, simplemente construimos la matriz de forma iterativa$n
, agregando un nuevo elemento cada vez, y enviamos el último al final$o[-1]
. Súper rápido: el cálculo10000
en mi máquina demora aproximadamente 5 segundos.fuente
> <> , 55 + 2 = 57 bytes
Se espera que la entrada esté presente en la pila al inicio del programa, por lo que +2 bytes para el
-v
indicador. Pruébalo en línea!Esto es muy lento, ya que utiliza la recursividad para calcular el resultado. Usando TIO,
h(50)
toma más de un minuto. Devuelve los resultados correctos <= 30, así que estoy seguro de que funcionaráh(10000)
, ¡simplemente no lo he ejecutado para averiguarlo!fuente