Definición
La secuencia de Fibonacci F(n)
, en los enteros positivos, se define como tal:
1. F(1) = 1
2. F(2) = 1
3. F(n) = F(n-1) + F(n-2), where n is an integer and n > 2
El Fibonacci-orial de un entero positivo es el producto de [F(1), F(2), ..., F(n)]
.
Tarea
Dado entero positivo n
, encuentre el Fibonacci-orial de n
.
Especificaciones
El fibonacci-orial de 100
debe computar en menos de 5 segundos en una computadora razonable.
Casos de prueba
n Fibonacci-orial of n
1 1
2 1
3 2
4 6
5 30
6 240
7 3120
8 65520
9 2227680
10 122522400
11 10904493600
12 1570247078400
13 365867569267200
14 137932073613734400
15 84138564904377984000
16 83044763560621070208000
17 132622487406311849122176000
18 342696507457909818131702784000
19 1432814097681520949608649339904000
20 9692987370815489224102512784450560000
100 3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
Respuestas:
Mathematica, 10 bytes
Otro Mathematica incorporado es golpeado por un lenguaje de golf sin el incorporado.
fuente
Jalea , 6 bytes
La entrada 100 termina en 500 ms localmente. Pruébalo en línea!
Cómo funciona
fuente
+¡1
un enésimo fibonacci no construido y+С1
son los primeros n números de Fibonacci?En realidad , 4 bytes
Ejecuta la entrada 100 en 0.2 segundos. Código:
Explicación:
Utiliza la codificación CP-437 . Pruébalo en línea! .
fuente
Brainfuck,
11981067817770741657611603Sin comprimir, con comentarios:
Pruébalo en línea!
El tiempo de ejecución para n = 100 es menos de 1 segundo con el intérprete en línea (aproximadamente 0.2 s localmente con mi propio intérprete). La entrada máxima es 255, pero requeriría que el intérprete admita ~ 54000 celdas (el intérprete en línea parece ajustarse a 64k).
Cambiar registro
Se ahorraron alrededor de 130 bytes con una mejor extracción del dígito actual para multiplicar por y combinando agregar y transportar en una sola pasada. También parece ser un poco más rápido.
Guardado otros 250 bytes. Logré reducir mi bloc de notas de multiplicación en dos celdas, lo que ahorra bytes en casi todas partes al no tener que cambiar tanto entre dígitos. También dejé caer el acarreo después de multiplicarlo por un dígito, y en su lugar realicé un acarreo completo mientras agregué el total acumulado.
Cortó otros 50, nuevamente con una mejor extracción del dígito actual para multiplicarlo, simplemente no moviéndolo hacia adelante la primera iteración y trabajando desde donde está. Algunas micro optimizaciones más abajo representan alrededor de ~ 10 bytes.
30 más desaparecidos. Marcar los dígitos que ya se han tomado con un 0 en lugar de un 1 hace que sean más fáciles de localizar. También hace que la verificación de si el ciclo de multiplicación ha terminado sea algo más simple.
Reduje el bloc de notas por otra celda, por 80 bytes más. Hice esto fusionando el marcador para el producto anterior y el total actual, lo que reduce los cambios entre las brechas y facilita un poco la contabilidad.
Salvó otros 50, al eliminar otra celda, reutilizando el marcador para los dígitos de Fibonacci para marcar el último dígito tomado también. También pude fusionar el ciclo para cambiar los totales anteriores con el ciclo de multiplicación de dígitos.
Guardado 8 bytes en el análisis de entrada. Ups
fuente
Python, 45 bytes
La entrada se toma de stdin. La salida para n = 100 termina demasiado rápido como para medir el tiempo con precisión. n = 1000 toma aproximadamente 1s.
Uso de muestra
fuente
Haskell
4129 Bytes1 + 11 bytes guardados por los comentarios de @ Laikoni.
1
,f
y!!
son tokens separados. La primera línea define la secuencia de Fibonacci, la segunda es una función que calcula la secuencia de fibonacci-oriales y devuelve el enésimo para un n dado. Comienza a imprimir dígitos casi de inmediato incluso para n = 1000.fuente
(scanl(*)1f!!)
.f=1:scanl(+)1f
42+
como una función que agrega 42? No deberías, porque es solo una expresión inacabada. Pero en Haskell podemos agregar paréntesis y obtener el sección(42+)
, una forma de escribir la función\n->42+n
. Aquí es lo mismo, solo con!!
(el operador infijo binario para la indexación) en lugar de+
un primer operando más complicado.Python 2, 39 bytes
Pruébalo en Ideone .
fuente
True
en algunos casos.True
para la entrada 0 , que no es positiva.J,
1716 bytes1 byte se juega con una solución aún mejor por millas.
La idea es la misma que la original, pero en lugar de formar la matriz para operar en diagonales menores, formamos las diagonales sobre la marcha.
Original
Para obtener el primero n fibonomiales:
Lectura de derecha a izquierda ...
Cree la matriz de enteros consecutivos (
i.
) hasta uno especificado, a partir de esa matriz cree la tabla (/~
) de coeficientes binomiales (!
) calculados a partir de cada par en la matriz, esta tabla es la parte superior triangular de Pascal en al final de la primera fila y todos los elementos debajo de la diagonal principal son 0, afortunadamente para la implementación de!
. Si sumas (+/
) todas las diagonales menores (/.
), obtienes números de Fibonacci, pero necesitas tomar ({.
) tanto de los primeros elementos de la matriz resultante como la longitud (#
) de la tabla misma. Luego, el producto (*/
) aplicado a prefijos consecutivos (\
) de la matriz da como resultado la secuencia deseada de fibonoriales.Si lo desea, puede tomar solo el último usando 2 bytes más ({:
) pero pensé que mostrarlos no es pecado:)
.NB. the previous code block is not a J function
.Para los números grandes en J que usa
x
al final:El programa se ejecuta en Avarage 0.11s .
fuente
[:*/+/@(!|.)\@i.
usar 16 bytes. Forma los mismos coeficientes binomiales a lo largo de la tabla que genera utilizando,!/~
excepto que lo forma tomando prefijos dei.
.Pyth, 13 bytes
Demostración
Esto emplea un ingenioso truco no seguro para los tipos. Cinco de los personajes (
u*G ... Q1
) dicen que la salida es el producto de la entrada de muchos números. El resto del código genera los números.=[sZhZ)
actualiza la variableZ
a la lista[s(Z), h(Z)]
. Luegos
suma esa lista, para ser multiplicada.Z
es inicialmente 0.s
, en ints, es la función de identidad.h
, en su, es la+ 1
función. Entonces, en la primera iteración,Z
convierte en[0, 1]
.s
en las listas está la función de suma, como se mencionó anteriormente.h
Es la función de la cabeza. Entonces la segunda iteración es[1, 0]
.Aquí hay una lista:
Estas sumas se multiplican para dar el resultado.
fuente
Mathematica
2524 bytesGracias a Martin Ender.
Tiempo: 63 microsegundos.
fuente
1##&@@Fibonacci~Array~#&
Jalea, 8 bytes
Mi primera sumisión en Jelly. No es tan corto como la respuesta de @Dennis , pero solo tiene 2 bytes más con un método diferente.
A nivel local, requiere unos 400 ms en comparación con 380 ms con la versión de @Dennis para n = 100.
Pruébalo en línea!
Explicación
fuente
PARI / GP, 29 bytes
O alternativamente:
fuente
R,
9996787666 bytesEsta respuesta es utiliza la fórmula de Binet , así como la
prod(x)
función. Como R no tiene unPhi
valor incorporado, lo definí yo mismo:Funciona en menos de 5 segundos, pero R tiende a dar
Inf
una respuesta para esos números grandes ...Sin golf:
-2 bytes gracias a @Cyoce!
¡Oh, me encanta este sitio! -10 bytes gracias a @ user5957401
fuente
sqrt(5)
en una variableN
una vez, puede llamar a scan dentro del1:N
bit. es decirfor(n in 1:scan())
. También puede guardar algunos caracteres simplemente usando en*
lugar de laprod()
función en su bucle for. Su bucle for es solo una línea, por lo que tampoco necesita las llaves.function(n,N=1:n,p=5^.5)prod(((1+p)^N-(1-p)^N)/2^N/p)
R,
82,53, 49 bytes (48 bytes con un estilo de entrada diferente)Si solo podemos preceder el código con el número de entrada, obtenemos el byte de 48
EDITAR: Nuevo código. El original está debajo:
No devolverá nada más que Inf para
a(100)
embargo, . Y no funcionará para nada más que enteros no negativos.Sin golf:
fuente
Java, 165 bytes
Golfizado:
Este es otro caso en el que
BigInteger
se requiere debido a los grandes números. Sin embargo, pude guardar el textoBigInteger
al mínimo, manteniendo el tamaño bajo. También lo comparé con las importaciones estáticas, e hizo que la longitud total fuera más larga.Este programa funciona rastreando tres números en una matriz. Los dos primeros son los dos números anteriores de Fibonacci. El tercero es el valor acumulado. El ciclo comienza calculando el siguiente valor y almacenándolo en índices de matriz alternos (0, 1, 0, 1, ...). Esto evita la necesidad de cambiar valores con operaciones de asignación costosas (en términos de tamaño de fuente). Luego toma ese nuevo valor y multiplícalo en el acumulador.
Al evitar objetos temporales y limitar el bucle a dos operadores de asignación, pude extraer bastantes bytes.
Sin golf:
Salida del programa:
fuente
Brachylog , 31 bytes
Pruébalo en línea!
fuente
Ruby, 39 bytes
fuente
Javascript (ES6),
5139 bytesImplementación recursiva (39 bytes)
Implementación original (51 bytes)
Nota: Inicia errores de redondeo para el Fibonacci-orial de 16, 100 es solo Infinity, se ejecuta en lo que parece ser <1 segundo.
fuente
n=>[...Array(n)].reduce(p=>(c=a,a=b,p*=b+=c),a=1,b=0)
solo para descubrir que había contado lof=
que no es necesario para ahorrarle 2 bytes.DC (sabor GNU o OpenBSD) , 36 bytes
Archivo
A003266-v2.dc
:(sin línea nueva)
... ahora el resultado se mantiene en la pila en lugar de usar un registro con nombre (está
Y
en la versión 1). losr
comando no está disponible en el originaldc
(vea la página de Dc de RosettaCode ).Correr:
Tratando de explicar:
tos
es el contenido de la parte superior de la pila sin quitarlo.nos
es el elemento a continuacióntos
.corriente continua , 41 bytes
... sencillo, sin trucos:
Archivo
A003266-v1.dc
:(sin línea nueva)
Correr:
fuente
dc
código definitivamente es más fácil que explicarlo ...n
elementos superiores a otra pila a la vez. Por ahora, sin embargo, todavía no sé cómo compilardc
desde la fuente. : /C #
11010910710310194 BytesExplicación
Algoritmo Iterativo de Fib
fuente
Brain-Flak , 54 bytes
Pruébalo en línea!
La multiplicación en Brain-Flak lleva mucho tiempo para grandes entradas. Simplemente multiplicar F 100 por F 99 con un algoritmo de multiplicación genérico llevaría miles de millones de años.
Afortunadamente, hay una forma más rápida. Una secuencia de Fibonacci generalizada que comience
(k, 0)
generará los mismos términos que la secuencia habitual, multiplicada pork
. Usando esta observación, Brain-Flak puede multiplicarse por un número de Fibonacci tan fácilmente como puede generar números de Fibonacci.Si la pila consta de
-n
dos números seguidos,{({}()<([({})]({}{}))>)}{}{}
calculará lasn
iteraciones de la secuencia generalizada de Fibonacci y las descartará por la última. El resto del programa simplemente configura el 1 inicial y recorre esto para todos los números en el rangon...1
.Aquí está el mismo algoritmo en los otros idiomas proporcionados por este intérprete:
Brain-Flak Classic, 52 bytes
Pruébalo en línea!
Flujo cerebral, 58 bytes
Pruébalo en línea!
Mini-Flak, 62 bytes
Pruébalo en línea!
fuente
Mathematica -
3226 bytes¡@MartinEnder cortó 6 bytes!
fuente
BRECHA 28 Bytes
No sabía antes de hoy que GAP tiene un
Fibonacci
incorporado.fuente
Rubí, 85 bytes
Resultó bien, pero probablemente haya una solución más corta.
Cálculo rápido de Fibonnaci tomado de aquí: enlace
Pruébalo aquí
fuente
Julia, 36 bytes
fuente
Cerebro-Flak ,
110104100 bytesPruébalo en línea!
Explicación
Primero ejecutamos una versión mejorada del generador de secuencia de Fibonacci, cortesía del Dr. Green Eggs y Iron Man
Luego, mientras la pila tiene más de un elemento
multiplica los dos primeros elementos
y saca el cero extra
fuente
Clojure, 70 bytes
Clojure no es realmente un buen lenguaje para el golf de código. Oh bien.
Pruébalo en http://tryclj.com .
fuente
Adelante, 55 bytes
Utiliza un enfoque iterativo, basado en mi respuesta de Fibonacci en Forth. Los resultados se desbordan aritméticamente para
n > 10
. La respuesta no distingue entre mayúsculas y minúsculas.Pruébalo en línea
fuente
Rápido, 68 bytes
fuente
JavaScript (ES6), 46 bytes
Utiliza recursividad y variables de acumulación. Los errores de redondeo comienzan en
f(16)
.fuente