Introducción
Todos conocemos y amamos nuestra secuencia de Fibonacci y ya hemos visto innumerables desafíos aquí. Sin embargo, todavía nos falta un caso muy simple que esta respuesta proporcionará: ¡Fibonacci invertida! Así que dado F_n
tu trabajo es encontrar n
.
Especificación
Entrada
Su entrada será un número entero no negativo, que se garantiza que formará parte de la secuencia de Fibonacci.
Salida
La salida también debe ser un número entero no negativo.
¿Qué hacer?
La introducción ya decía: dado un número de Fibonacci, genera su índice. El número de Fiboancci se define como F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
y se le da F(n)
y debe devolver n
.
Casos de esquina potenciales
0 es una entrada y salida válida.
Si se le da "1" como entrada, puede enviar "1" o "2", como prefiera.
Siempre puede suponer que su entrada en realidad es un número de Fibonacci.
Puede suponer que la entrada es representable como un entero con signo de 32 bits.
¿Quién gana?
Este es el código de golf, por lo que gana la respuesta más corta en bytes.
Se aplican reglas estándar, por supuesto.
Casos de prueba
0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46
Respuestas:
En realidad, 1 byte
Sí, hay algo incorporado para esto, desde el 16 de noviembre de 2015 .
Pruébalo en línea
Por diversión, sin el incorporado, son 9 bytes:
Pruébalo en línea!
Explicación:
fuente
Mathematica, 25 bytes
Función. Bastante claro si me preguntas.
fuente
Python,
363432 bytesVersión anterior:
Explicación
La idea central es invertir la fórmula
que nos dice que
Llegar
Las optimizaciones de golf son:
len(str(n))
para calcular la base de registro 10 sin importarlog
(la versión anterior se usaba.bit_length()
para calcular la base de registro 2)n
a una potencia, para que la aproximación del logaritmo pueda distinguir entre números sucesivos de FibonacciLuego, el divisor se truncó con la menor precisión posible y el multiplicador elegido para dar los resultados correctos para todos los números de Fibonacci de 32 bits.
fuente
f=
no se cuenta.lambda n:~-len(`66*n**6`)//1.24
debería funcionar.05AB1E , 3 bytes
Código:
Explicación:
Utiliza la codificación CP-1252 . Pruébalo en línea! .
fuente
Jalea,
1411 bytesPruébalo en línea!
Esta es mi primera respuesta Jelly! Esto usa el algoritmo de la respuesta MATL . ¡Gracias a Dennis por reducir 3 bytes!
Explicación:
Esta es la respuesta correcta, ahora solo tenemos que manejar el caso especial de '0'. Con '0' como argumento, obtenemos
-infinity
, así que volvemosfuente
Julia,
272618 bytesUtiliza el inverso de la fórmula de Binet , con la precisión suficiente para enteros de 32 bits; en realidad funciona hasta F (153) = 42,230,279,526,998,466,217,810,220,532,898> 2 105 .
Pruébalo en línea!
Cómo funciona
La fórmula de Binet establece lo siguiente.
La restricción de F a la serie de Fibonacci, el mapa N → M n tiene un derecho inversa M → N F .
Tenemos eso
y todo lo que queda por hacer es lidiar con el caso límite 0 .
Como la entrada está restringida a enteros de 32 bits, podemos usar literales decimales cortos en lugar de las constantes en la fórmula.
log φ = 0.481211825059603447… ≈ 0.48
Desafortunadamente, 0.5 no es lo suficientemente preciso.
√5 = 2.2360679774997896964… ≈ 3
Eso puede parecer una aproximación horrible a primera vista, pero estamos tomando logaritmos y desde log 3 - log √5 = 0.29389333245105 ... , el resultado antes del redondeo será un factor constante pequeño.
0.5 ≈ 0.7
Debido al exceso de la aproximación anterior, podríamos omitir este término por completo y aún así obtener resultados correctos para F> 0 . Sin embargo, si F = 0 , el logaritmo será indefinido. 0.7 resultó ser el valor más corto que extiende nuestra fórmula a F = 0 .
fuente
JavaScript,
5450695042 bytesSeguramente no va a ganar, solo por diversión :)
Ok, la comprobación de cero consume 19 bytes. WTF?Estúpido yo.¡Manifestación! Para ver el último caso de prueba, debe desplazarse un poco por la consola.
Gracias @edc por acortar en 8 bytes.
fuente
b=>{for(j=1,i=c=0;b-i;c++)i=j+(j=i);return c}
45, golfb=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c
42.Perl 6
33 3027 bytesIntentalo
Explicación:
Prueba:
fuente
first *==$_
con justfirst $_
, porque un número es un emparejador inteligente válido....
operador en lugar defirst
Jalea , 8 bytes
Pruébalo en línea! Tenga en cuenta que este enfoque es demasiado ineficiente para el último caso de prueba.
Cómo funciona
fuente
Pyke, 5 bytes
Pruébalo aquí!
fuente
Python, 29 bytes
Divide recursivamente la entrada por la aproximación de la proporción áurea 1.61 hasta que esté por debajo de 0.7, y genera el número de divisiones.
Para 0, sale el código
False
, que es igual a 0 en Python . Esto se puede evitar para 2 bytesfuente
JavaScript (ES6),
3933 bytesIncluso con ES7, la fórmula inversa de Binet toma 47 bytes:
fuente
log
y precalcule todas las constantes ...f(n,k,j+k)
debe incluir la asignaciónf=
y contarla como +2 bytes . La regla para lambdas sin nombre no debería aplicarse aquí.Sabio, 49 bytes
Gracias a TuukkaX por la sugerencia acerca de cómo guardar
sqrt(5)
comos
para cortar unos pocos bytes.Pruébalo en línea .
Este enfoque que usa un inverso de la fórmula de Binet ofrece varias mejoras con respecto al enfoque anterior: es más rápido (tiempo constante versus tiempo cuadrático), en realidad funciona para entradas más grandes, ¡y es más corto!
Los usuarios de Python pueden preguntarse por qué estoy usando en
sqrt(5)
lugar del más corto5**.5
: es porque5**.5
se calcula con lapow
función de C y pierde precisión debido a problemas de coma flotante. Muchas funciones matemáticas (incluyendosqrt
ylog
) se sobrecargan en Sage para devolver un valor simbólico exacto, que no pierde precisión.fuente
sqrt(5)
una variable y usarla dos veces, en lugar de escribirsqrt(5)
dos veces?MATL , 14 bytes
Pruébalo en línea!
Esto usa un inverso de la fórmula de Binet , por lo que es muy rápido.
Sea F denota el n -ésimo número de Fibonacci, y phi de la proporción áurea . Luego
El código usa esta fórmula con dos modificaciones:
Cómo está hecho
fuente
O1G:"yy+]vGmfq
t?17L&YlXkQ
5X^*
. ( He hecho esto antes ). Y no sé MATL lo suficiente como para seguir mejorando.Python, 38 bytes
Pruébalo en Ideone .
fuente
JavaScript, 22 bytes
fuente
-Infinity|0
está0
en JavaScript. Imagínate.-Infinity = FFF00000 00000000
. Me alegró descubrirlo, ahorra 3 bytes por no tener que anteponer una prueba explícita de cero comon&&
. Aparte de eso, el propósito principal de|0
es un sustituto deMath.trunc()
(como÷
en Julia).C,
6258 bytesDetallado
fuente
Java 7, 70 bytes
https://ideone.com/I4rUC5
fuente
int c(int n){int a=0,b=1,c=0,t;for(;a<n;t=b,b+=a,a=t)c++;return c;}
(no probado)int c(int n){int a=0,b=1,c=0;while(a<n){c++;b+=a;a=b-a;}return c;}
(no probado)int c(int n){int a=0,b=1,c=0;for(;a<n;b+=a,a=b-a)c++;return c;}
(no probado)TSQL, 143 bytes
La entrada entra
@n
como enDECLARE @n INT = 1836311903;
fuente
Haskell, 45 bytes
fuente
Sesos , 28 bytes
Hexdump:
Pruébalo en línea!
(Tiempo exponencial porque en Sesos copiar un número necesita tiempo exponencial).
Ensamblaje utilizado para generar el archivo binario:
fuente
Java 8 61 bytes
Igual que la respuesta de @dainichi solo se acortó usando Java 8 lambdas. La respuesta es una expresión de valor válida.
Sin golf:
fuente
Pyth, 13 bytes
Banco de pruebas.
Aproximación en Python 2:
enfoque alternativo, 18 bytes
Banco de pruebas.
Esto utiliza
.I
para inversa.fuente
Java 7, 89 bytes
Inspirado por la explicación de @Adnan respuesta 05AB1E 's .
Sin golf y casos de prueba:
Pruébalo aquí (Límite de tiempo excedido para el último caso de prueba, pero funciona en aproximadamente 30-45 segundos en mi PC).
Salida:
fuente
Perl 5.10, 48 bytes
Básicamente buscando el derecho
n
para queF(n) = input
.-a
el interruptor agrega un byte.Pruébalo aquí!
fuente
J,
322717 bytesCalcula los primeros n números de Fibonacci y luego encuentra el índice de n en esa lista.
Uso
Se utilizan comandos adicionales para formatear múltiples entradas / salidas. Se omite el último caso de prueba, ya que requerirá mucho más tiempo para calcular.
Explicación
fuente
Mathematica, 30 bytes
Función pura; devuelve 2 si la entrada es 1.
No supera la otra entrada de Mathematica, pero muestra un método inusual: es un hecho (muy bueno) que el enésimo número de Fibonacci es el entero más cercano a [1 / sqrt (5) veces la enésima potencia de la proporción áurea] (" Fórmula de Binet ").
Por lo tanto, la función inversa será el logaritmo base- [proporción áurea] de [sqrt (5) veces el número de Fibonacci en cuestión]. El
.8+
es un truco para asegurarse de que no tomamos el logaritmo de 0, sin atornillar los otros valores.fuente
Japt , 10 bytes
Pruébalo en línea!
Explicación
fuente
Brachylog , 14 bytes
Pruébalo en línea!
Toma la entrada a través de la variable de salida y las salidas a través de la variable de entrada.
No estoy completamente seguro de por qué
≜
es necesario.fuente
Javascript (usando una biblioteca externa) (84 bytes)
Enlace a lib: https://github.com/mvegh1/Enumerable
Explicación del código: la biblioteca tiene un método estático que crea una secuencia hasta que el predicado tenga un valor de retorno indefinido. El predicado tiene una firma de ("i" ndex, actual "a" matriz interna generada). En cada iteración, verificamos si el último elemento de la matriz interna es igual a la entrada, n. Si no, devuelve el siguiente valor en la secuencia fib. De lo contrario, el predicado tiene un resultado indefinido que termina la generación de la secuencia. Luego, devolvemos la longitud de la secuencia (y restamos 1 para cumplir con la base 0 como se ve en el OP
fuente
n=>{a=c=t=0,b=1;while(a<n){c++;t=b;b+=a;a=t}return c}
Pruébelo en línea!