Todos estamos familiarizados con la famosa secuencia de Fibonacci , que comienza con 0
y 1
, y cada elemento es la suma de los dos anteriores. Estos son los primeros términos (OEIS A000045 ):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
Dado un número entero positivo , devuelve el número más cercano de la secuencia de Fibonacci, según estas reglas:
El número de Fibonacci más cercano se define como el número de Fibonacci con la menor diferencia absoluta con el entero dado. Por ejemplo,
34
es el número de Fibonacci más cercano a30
, porque|34 - 30| = 4
, que es más pequeño que el segundo más cercano21
, para el cual|21 - 30| = 9
.Si el entero dado pertenece a la secuencia de Fibonacci, el número de Fibonacci más cercano es exactamente el mismo. Por ejemplo, el número de Fibonacci más cercano a
13
es exactamente13
.En caso de empate, puede optar por emitir cualquiera de los números de Fibonacci que estén más cerca de la entrada o simplemente emitirlos a ambos. Por ejemplo, si la entrada es
17
, todos los siguientes son válidos:21
,13
o21, 13
. En caso de que los devuelva a ambos, mencione el formato.
Se aplican las lagunas predeterminadas . Puede tomar entrada y proporcionar salida a través de cualquier método estándar . Su programa / función solo debe manejar valores de hasta 10 8 .
Casos de prueba
Entrada -> Salida 1 -> 1 3 -> 3 4 -> 3 o 5 o 3, 5 6 -> 5 7 -> 8 11 -> 13 17 -> 13 o 21 o 13, 21 63 -> 55 101 -> 89 377 -> 377 467 -> 377 500 -> 610 1399 -> 1597
Tanteo
Este es el código de golf , por lo que gana el código más corto en bytes en cada idioma .
n
implican ≥ 1
.Respuestas:
Python 2 , 43 bytes
Pruébalo en línea!
Itera a través de pares de números consecutivos de Fibonacci
(a,b)
hasta que alcanza uno donde la entradan
es menor que su punto medio(a+b)/2
, luego regresaa
.Escrito como un programa (47 bytes):
Misma longitud :
fuente
Neim , 5 bytes
Explicación:
En la versión más nueva de Neim, esto se puede jugar a 3 bytes:
Como las listas infinitas se han rediseñado para subir solo a su valor máximo.
Pruébalo en línea!
fuente
Python ,
5552 bytesPruébalo en línea!
fuente
R ,
7067646260 bytes-2 bytes gracias a djhurio!
-2 bytes más gracias a djhurio (¡chico puede jugar al golf!)
Como solo tenemos que manejar valores hasta
10^8
, esto funciona.Pruébalo en línea!
Lee
n
de stdin. elwhile
bucle genera los números de fibonacci enF
(orden decreciente); en caso de empate, se devuelve el más grande. Esto activará una serie de advertencias porquewhile(F<1e8)
solo evalúa la declaración para el primer elemento deF
con una advertenciaOriginalmente utilicé
F[which.min(abs(F-n))]
el enfoque ingenuo, pero @djhurio sugirió(F-n)^2
ya que el pedido será equivalente, y enorder
lugar dewhich.min
.order
sin embargo, devuelve una permutación de índices para poner su entrada en orden creciente, por lo que[1]
al final necesitamos obtener solo el primer valor.versión más rápida:
solo almacena los dos últimos números de Fibonacci
fuente
F=1:0;n=scan();while(n>F)F=c(F[1]+F[2],F);F[order((F-n)^2)][1]
F=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][1]
F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]
numbers::fibonacci(x<-scan(),T)
JavaScript (ES6), 41 bytes
Se redondea por preferencia.
fuente
f=(n,x=0,y=1)=>x*(2*n<x+y)||f(n,y,x+y)
Como no tiene que trabajar con 0, puede jugar un poco más al golf.Jalea ,
97 bytes-2 bytes gracias a @EriktheOutgolfer
Pruébalo en línea!
Consejos de golf bienvenidos :). Toma un int como entrada y devuelve una lista int.
fuente
µḢ
.Mathematica, 30 bytes
Pruébalo en línea!
fuente
Código de máquina x86-64, 24 bytes
Los bytes de código anterior definen una función en código máquina x86 de 64 bits que se encuentra el número de Fibonacci más cercano al valor de entrada especificado,
n
.La función sigue la convención de llamada System V AMD64 (estándar en los sistemas Gnu / Unix), de modo que el único parámetro (
n
) se pasa en elEDI
registro y el resultado se devuelve en elEAX
registro.Mnemotécnicos de montaje sin golf:
Pruébalo en línea!
El código básicamente se divide en tres partes:
EAX
se establece en 0 yEDX
se establece en 1.La siguiente parte es un bucle que iterativamente calcula los números de Fibonacci a cada lado del valor de entrada,
n
. Este código se basa en mi implementación anterior de Fibonacci con sustracción , pero ... um ... no es con sustracción. :-) En particular, utiliza el mismo truco de calcular el número de Fibonacci usando dos variables: aquí, estos son los registrosEAX
yEDX
. Este enfoque es extremadamente conveniente aquí, porque nos da números adyacentes de Fibonacci. El candidato potencialmente menor de lo quen
se retieneEAX
, mientras que el candidato potencialmente mayor de lo quen
se retieneEDX
. Estoy bastante orgulloso de lo apretado que pude hacer el código dentro de este bucle (y más cosquillas que lo volví a descubrir de forma independiente, y solo más tarde me di cuenta de cuán similar era a la respuesta de resta vinculada anteriormente).Una vez que tengamos disponibles los valores de Fibonacci candidatos
EAX
yEDX
, es una cuestión conceptual simple de averiguar cuál está más cerca (en términos de valor absoluto)n
. En realidad, teniendo un valor absoluto costaría manera demasiados bytes, por lo que acabamos de hacer una serie de sustracciones. El comentario a la derecha de la penúltima instrucción de movimiento condicional explica acertadamente la lógica aquí. Esto se mueveEDX
hacia adentroEAX
o se vaEAX
solo, de modo que cuando la función seRET
activa, se devuelve el número de Fibonacci más cercanoEAX
.En el caso de un empate, se devuelve el menor de los dos valores candidatos, ya que hemos utilizado en
CMOVG
lugar deCMOVGE
hacer la selección. Es un cambio trivial, si prefiere el otro comportamiento. Sin embargo, devolver ambos valores no es un iniciador; solo un resultado entero, por favor!fuente
nasm foo.asm -l /dev/stdout | cut -b -28,$((28+12))-
recortar algunas columnas entre el código de la máquina y la fuente en una respuesta reciente.xor eax,eax
/cdq
/inc edx
. Por lo tanto, podría crear una versión de convención de llamada personalizada de 32 bits que guardó un byte.cdq
mucho en las respuestas de código de golf. No se requiere una convención de llamadas personalizada. Usualmente uso la__fastcall
convención de llamadas de Microsoft para código de 32 bits. Lo bueno de esto es que es compatible con GCC con una anotación, por lo que aún puede usar el servicio TIO que todos quieren ver.edi
/esi
paralodsb
/stosb
, y solo x86-64 SysV hace eso (hecho divertido: a propósito por esa razón, porque algunas funciones pasan sus argumentos a memset / memcpy, y supongo que a gcc en ese momento le gustó en línea de operaciones de cadena).PowerShell ,
8074 bytes(¡Pruébelo en línea! Temporalmente no responde)
Solución iterativa. Toma entrada
$n
, establece$a,$b
ser1,0
, y luego realiza un bucle con Fibonacci hasta$a
sea más grande que la entrada. En ese punto, indexamos en($b,$a)
base a Boolean si la diferencia entre el primer elemento y$n
es mayor que entre$n
y el segundo elemento. Eso queda en la tubería, la salida es implícita.fuente
JavaScript (ES6), 67 bytes
Casos de prueba
Mostrar fragmento de código
fuente
JavaScript (nodo de Babel) , 41 bytes
Residencia en la impresionante respuesta de Python de ovs
Pruébalo en línea!
Sin golf
fuente
0
(no es que sea necesario; solo quiero que lo haga ):f=(n,i=1,j=1)=>n+n<i+j?i:f(n,j,j+i)
Python, 74 bytes
Pruébalo en línea!
Cómo funciona
Para todos los k ≥ 0, ya que | φ - k / √5 | <1/2, F k = φ k / √5 + φ - k / √5 = redondo (φ k / √5). Por lo tanto, el valor de retorno cambia de F k - 1 a F k exactamente donde k = log φ ( n ⋅2√5) - 1, o n = φ k + 1 / (2√5), que está dentro de 1/4 de F k + 1/2 = ( F k - 1 + F k ) / 2.
fuente
05AB1E , 6 bytes
Pruébalo en línea!
fuente
C (gcc) ,
86858376 bytesPruébalo en línea!
fuente
Java (OpenJDK 8) ,
605756 bytesPruébalo en línea!
-1 byte gracias a @Neil
fuente
Python 3 , 103 bytes
Pruébalo en línea!
Lamentablemente, tuve que usar un def en lugar de lambda ... Probablemente hay mucho margen de mejora aquí.
Respuesta original (incorrecta):
Python 3 , 72 bytesPruébalo en línea!
Mi primera presentación de PPCG. En lugar de calcular los números de Fibonacci de forma recursiva o tenerlos predefinidos, este código usa cómo el número n-ésimo de Fibonacci es el entero más cercano a la potencia n-ésima de la proporción áurea dividida por la raíz de 5.
fuente
nearest_fib_PM2R
función que vinculé en mi comentario sobre la pregunta.Taxi, 2321 bytes
Pruébalo en línea!
Pruébalo en línea con comentarios!
Sin golf con comentarios:
fuente
Python 3 , 84 bytes
Pruébalo en línea!
Puede funcionar, pero ciertamente no es rápido ...
Salidas en
True
lugar de1
, pero en Python son equivalentes.fuente
cc, 52 bytes
Pruébalo en línea!
Toma entrada en la carrera usando?
Editado para asumir la parte superior de la pila como valor de entrada, -1 byte.
La entrada se almacena en el registro
i
. Luego ponemos 1 y 1 en la pila para comenzar la secuencia de Fibonacci, y generamos la secuencia hasta que alcancemos un valor mayor quei
. En este punto tenemos dos números en la secuencia de Fibonacci en la pila: uno que es menor o igual quei
, y uno que es mayor quei
. Los convertimos en sus respectivas diferenciasi
y luego comparamos las diferencias. Finalmente, reconstruimos el número de Fibonacci sumando o restando la diferencia ai
.Vaya, estaba cargando dos registros en el orden incorrecto y luego los intercambiaba, desperdiciando un byte.
fuente
C # (.NET Core) ,
6356 bytes-1 byte gracias a @Neil
-6 bytes gracias a @Nevay
Pruébalo en línea!
fuente
for(;b<n;a=b,b+=c)c=a;
Guardar un byte?c
mediante el usob+=a,a=b-a
(debe guardar 6 bytes).Q / KDB +, 51 bytes
fuente
Hexagonía , 37 bytes.
Pruébalo en línea!
sin golf:
Desglosado:
Al igual que algunos otros carteles, me di cuenta de que cuando el punto medio de last y curr es mayor que el objetivo, el más pequeño de los dos es el más cercano o el más cercano.
El punto medio está en (last + curr) / 2. Podemos acortar eso porque next ya es last + curr, y si en cambio multiplicamos nuestro entero objetivo por 2, solo necesitamos verificar que (next - 2 * target)> 0, luego regrese último.
fuente
Brachylog , 22 bytes
Pruébalo en línea!
Realmente, todo lo que he hecho aquí es pegar el clásico de Fatalize. Devolver la solución del número primo más cercano y la mía. ¿Soy un número de Fibonacci? solución. Afortunadamente, este último ya opera en la variable de salida; desafortunadamente, también incluye un corte necesario que debe aislarse para +2 bytes, por lo que el único punto de elección que descarta es
ⁱ
dejarlo≜
intacto.fuente
Japt
-g
, 8 bytesIntentalo
fuente
Java 7,
244234 bytesfuente
static
si desea seguir con Java 7.r>c&&s<c
debería serr>=c&&s<=c
,s-c
debería serc-s
), podría eliminar espacios en blanco no necesarios, usarint f(int i){return i<2?i:f(--i)+f(--i);}
, usar una sola declaración de retorno con operador ternario en c y eliminar el manejo especialc-s==r-c
ya que se permite devolver cualquier valor.Pyke , 6 bytes
Pruébalo en línea!
fuente
Lisp común, 69 bytes
Pruébalo en línea!
fuente
Perl 6 , 38 bytes
Pruébalo
Para una posible aceleración agregue
.tail(2)
antes.sort(…)
.En el caso de un empate, siempre devolverá el menor de los dos valores, porque
sort
es un tipo estable. (dos valores que ordenarían lo mismo mantienen su orden)fuente
Pyth, 19 bytes
Pruébalo aquí
Explicación
fuente
Haskell, 48 bytes
Pruébalo en línea!
fuente