Números negativos de Fibonacci

28

Probablemente todos conozcan la secuencia de Fibonacci:

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)
fibonacci(0)=0
fibonacci(1)=1

Su tarea es tan simple como podría ser:

  • Dada número entero Nde cómputofibonacci(n)

pero aquí está el giro:

  • También hacer negativo N

Espere. ¿Qué?

fibonacci(1)=fibonacci(0)+fibonacci(-1)

asi que

fibonacci(-1)=1

y

fibonacci(-2)=fibonacci(0)-fibonacci(1)=-1

y así...

  • Este es un por lo que el programa más corto en bytes gana.
  • Puede enviar una función o un programa completo
  • N está en [-100,100]

Testcase (s) en CSV:

-9;-8;-7;-6;-5;-4;-3;-2;-1;0;1;2;3;4;5;6;7;8
34;-21;13;-8;5;-3;2;-1;1;0;1;1;2;3;5;8;13;21

Insinuación:

n <0 y n & 1 == 0:

fibonacci(n)=fibonacci(abs(n))*-1

Roman Gräf
fuente
No. El mío también quiere que apoyes números negativos.
Roman Gräf
77
Creo que esto no es un engaño. De las respuestas en la primera página del desafío existente de Fibonacci, solo 1 puede manejar los negativos, y todo el resto necesitaría ser cambiado significativamente para ir hacia atrás también.
xnor
Se agregaron algunos. Siéntase libre de agregar más. @Flip
Roman Gräf
1
Lea esta meta publicación sobre formatear casos de prueba: trate de evitar tablas elegantes
FlipTack
y por CSV te refieres a SSV (valores separados por punto y coma)?
NH.

Respuestas:

22

Mathematica, 9 bytes

Fibonacci

Sí, esta función integrada admite números negativos.

alephalpha
fuente
2
Esta es casi palabra por palabra la respuesta que venía a publicar: D
Greg Martin
17

Octava, 20 bytes

 @(n)([1,1;1,0]^n)(2)

Pruébalo en línea!

Explicación

Esto hace uso del hecho de que la secuencia de Fibonacci f(n)se puede escribir como (esto debería ser una notación de vector de matriz):

Recursivamente:

[f(n+1)]  = [1  1] * [f(n)  ]
[f(n)  ]    [1  0]   [f(n-1)]

Explícitamente:

[f(n+1)]  = [1  1] ^n * [1]
[f(n)  ]    [1  0]      [0]

Esto significa que la entrada superior derecha de esta matriz a la potencia de nes el valor f(n)que estamos buscando. Obviamente, también podemos invertir esta matriz, ya que tiene rango completo, y la relación todavía describe la misma relación de recurrencia. Eso significa que también funciona para entradas negativas.

falla
fuente
1
(Cómo) ¿Funciona esto también para una entrada negativa?
Roman Gräf
sí, viene la explicación ...
error
está ans(-6)destinado a ser positivo?
FlipTack
@FlipTack Lo sentimos, podría haber sido debido al cambio de índice. Usé 1, mientras que la pregunta usaba 0, lo arreglé ahora.
defecto
13

Máximo, 3 bytes

 fib

admite números positivos y negativos.

Pruébelo (pegue) en CESGA - Maxima en línea

rahnema1
fuente
¿Puedes agregar un enlace al idioma?
Pavel
Por supuesto, agregó un enlace a una calculadora en línea!
rahnema1
También funciona en WolframAlpha
Thunda
11

Python, 43 bytes

g=5**.5/2+.5
lambda n:(g**n-(1-g)**n)/5**.5

Una fórmula directa con la proporción áurea g. Con fla función anterior:

for n in range(-10,11):print f(n) 

-55.0
34.0
-21.0
13.0
-8.0
5.0
-3.0
2.0
-1.0
1.0
0.0
1.0
1.0
2.0
3.0
5.0
8.0
13.0
21.0
34.0
55.0

Misma longitud alt, solo alias la raíz cuadrada de 5:

a=5**.5
lambda n:((a+1)**n-(1-a)**n)/a/2**n

No vi una manera de hacer una función recursiva que pudiera competir con estos. Un intento moderado de 57 bytes:

f=lambda n:n<0and(-1)**n*f(-n)or n>1and f(n-1)+f(n-2)or n

A modo de comparación, un método iterativo (60 bytes en Python 2):

n=input()
a,b=0,1;exec"a,b=b,a+b;"*n+"a,b=b-a,a;"*-n
print a

O, para 58 bytes:

n=input()
a,b=0,1;exec"a,b=b,a+cmp(n,0)*b;"*abs(n)
print a
xnor
fuente
10

JavaScript (ES6), 42 bytes

f=n=>n<2?n<0?f(n+2)-f(n+1):n:f(n-2)+f(n-1)

Prueba

Arnauld
fuente
Realmente me gusta tu función. Tenía una sugerencia aquí, pero pasé por alto un -, así que no funcionaría ...
Luke
5

MATL , 11 9 bytes

Estoy contento con el [3,2], que seguramente se podría jugar al golf, si alguien conoce una forma, hágamelo saber =) (También funcionaría con [1,3]). Gracias @LuisMendo por -2 bytes =)

IHhBiY^2)

Esto está utilizando el mismo enfoque que la respuesta de Octave . Pero para generar la matriz

[1,1]
[1,0]

simplemente convertimos el número 3y 2de decimal a binario (es decir, 11y 10).

Pruébalo en línea!

falla
fuente
5

JavaScript (ES7) 37 bytes

Utiliza la fórmula de Binet .

n=>((1+(a=5**.5))**n-(1-a)**n)/a/2**n

Esto genera el nth número de Fibonacci + - 0.0000000000000005.

Luke
fuente
**requiere ES7.
Neil
Oh, pensé que era parte de ES6, pero tienes razón. Lo cambié También usé otra versión de la fórmula de Binet para ahorrar 1B.
Lucas
Ahora que lo pienso, solo usar en 1-plugar de -1/pdebería haber funcionado para el mismo ahorro.
Neil
3

Jolf, 2 bytes

mL

Pruébalo aquí!

El fibonacci incorporado, implementado utilizando la phifórmula.

Conor O'Brien
fuente
SyntaxError no capturado: token inesperado | en la nueva Función (<anónimo>) en p (math.min.js: 27) en Objeto (math.min.js: 27) en tipeado (eval en p (math.min.js: 27), <anónimo>: 36:14) en Object.n [como fábrica] (math.min.js: 45) en t (math.min.js: 27) en f (math.min.js: 27) en Object.get [como mediana ] (math.min.js: 27) en clone (rawgit.com/ConorOBrien-Foxx/Jolf/master/src/jolf.js:902) en rawgit.com/ConorOBrien-Foxx/Jolf/master/src/jolf. js: 2128 (Último Google Chrome, versión 55.0.2883.87m)
Ismael Miguel
@IsmaelMiguel Esto solo debería funcionar en firefox
Conor O'Brien
No tenía idea, no está en ninguna parte
Ismael Miguel
2

Haskell, 51 bytes

s=0:scanl(+)1s;f z|even z,z<0= -f(-z);f z=s!!abs z
Roman Czyborra
fuente
1
Pruebas múltiples dentro de un guardia se pueden combinar con ,en lugar de &&: even z,z<0.
nimi
1

Potencia Shell , 112 bytes

function f($n){$o=('-','+')[$n-lt0];&(({$a,$b=(2,1|%{f("$n$o$_"|iex)});"$a- $o$b"|iex},{$n*$n})[$n-in(-1..1)])}

Llamada de demostración:

-9..9 | %{"{0,2}`t=> {1,3}" -f $_,(f($_))} 

Salida de demostración:

-9  =>  34
-8  => -21
-7  =>  13
-6  =>  -8
-5  =>   5
-4  =>  -3
-3  =>   2
-2  =>  -1
-1  =>   1
 0  =>   0
 1  =>   1
 2  =>   1
 3  =>   2
 4  =>   3
 5  =>   5
 6  =>   8
 7  =>  13
 8  =>  21
 9  =>  34
JohnLBevan
fuente
1

Lithp , 88 bytes

#N::((if(< N 2)((if(< N 0)((-(f(+ N 2))(f(+ N 1))))((+ N))))((+(f(- N 2))(f(- N 1))))))

Mi mirada a todos esos paréntesis .

Pruébalo en línea!

No muy pequeño en realidad. Actualmente hay un error de análisis que requiere uno para usar (get N)o en (+ N)lugar de simplemente N. Elegí el más pequeño. Sin embargo, no creo que se pueda hacer nada más para jugar golf.

Andrakis
fuente