Números negativos de Fibonacci

28

Você provavelmente todos conhecem a sequência de fibonacci:

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

Sua tarefa é a mais simples possível:

  • Dada Ncomputação inteirafibonacci(n)

mas aqui está a reviravolta:

  • Também negativo N

Esperar. O que?

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

então

fibonacci(-1)=1

e

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

e assim por diante...

  • Este é um pelo que o programa mais curto em bytes ganha.
  • Você pode enviar uma função ou um programa completo
  • N está em [-100,100]

Caso (s) de teste em 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

Dica:

n <0 e n & 1 == 0:

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

Roman Gräf
fonte
Não. O meu também quer que você suporte números negativos.
Roman Gräf
7
Eu acho que isso não é uma bobagem. Das respostas na primeira página do desafio existente de Fibonacci, apenas 1 pode lidar com negativos, e todo o resto precisaria ser significativamente alterado para retroceder também.
xnor
Adicionado alguns. Sinta-se livre para adicionar mais. @Flip
Roman Gräf
1
Leia este meta post sobre como formatar casos de teste: tente evitar tabelas sofisticadas
FlipTack 31/12/16
e por CSV você quer dizer SSV (valores separados por ponto e vírgula)?
NH.

Respostas:

22

Mathematica, 9 bytes

Fibonacci

Sim, esta função interna suporta números negativos.

alefalpha
fonte
2
Essa é quase a palavra por palavra a resposta que eu estava postando: D
Greg Martin
17

Oitava, 20 bytes

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

Experimente online!

Explicação

Isso faz uso do fato de que a sequência de fibonacci f(n)pode ser escrita como (essa deve ser uma notação de vetor de matriz):

Recursivamente:

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

Explicitamente:

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

Isso significa que a entrada superior direita dessa matriz à potência de né o valorf(n) que estamos procurando. Obviamente, também podemos inverter essa matriz, pois ela possui uma classificação completa, e o relacionamento ainda descreve a mesma relação de recorrência. Isso significa que também funciona para entradas negativas.

flawr
fonte
1
(Como) Isso também funciona para dados negativos?
Roman Gräf
Sim, a explicação está chegando ...
flawr 31/12/16
está ans(-6)destinado a ser positivo?
FlipTack 31/12/16
@ FlipTack Desculpe, pode ter sido por causa da mudança de índice. Eu usei 1, enquanto a pergunta usava 0, eu o corrigi agora.
flawr
13

Máximos, 3 bytes

 fib

suporta números positivos e negativos.

Experimente (cole) no CESGA - Maxima on line

rahnema1
fonte
Você pode adicionar um link para o idioma?
Pavel
É claro que adicionou um link para uma calculadora online!
precisa saber é o seguinte
Também funciona em WolframAlpha
Thunda
11

Python, 43 bytes

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

Uma fórmula direta com a proporção áurea g. Com fa função acima:

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

Mesmo comprimento alt, apenas com o alias da raiz quadrada de 5:

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

Não vi uma maneira de criar uma função recursiva que pudesse competir com elas. Uma tentativa moderada de 57 bytes:

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

Para comparação, um método iterativo (60 bytes em Python 2):

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

Ou, para 58 bytes:

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

JavaScript (ES6), 42 bytes

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

Teste

Arnauld
fonte
Eu realmente gosto da sua função. Eu tive uma sugestão aqui, mas negligenciei um -, para que não funcionasse ... #
314 Luke #
5

MATL , 11 9 bytes

Estou feliz com o [3,2], que certamente poderia ser jogado, se alguém souber uma maneira, por favor me avise =) (Também funcionaria [1,3].) Obrigado @LuisMendo por -2 bytes =)

IHhBiY^2)

Isso está usando a mesma abordagem que a resposta do Octave . Mas para gerar a matriz

[1,1]
[1,0]

nós apenas convertemos o número 3e 2de decimal para binário (ie 11e 10).

Experimente online!

flawr
fonte
5

JavaScript (ES7) 37 bytes

Usa a fórmula de Binet .

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

Isso gera o número nth de Fibonacci + - 0.0000000000000005.

Luke
fonte
**requer ES7.
31516 Neil
Oh, pensei que fazia parte do ES6, mas você está certo. Mudou isso. Também usei outra versão da fórmula de Binet para salvar 1B.
Luke
Agora que penso nisso, apenas usar em 1-pvez de -1/pdeveria ter funcionado para a mesma economia.
Neil
3

Jolf, 2 bytes

mL

Experimente aqui!

O fibonacci embutido, implementado usando a phifórmula.

Conor O'Brien
fonte
SyntaxError não capturado: token inesperado | em new Function (<anonymous>) em p (math.min.js: 27) em Object (math.min.js: 27) em digitado (eval em p (math.min.js: 27), <anonymous>: 36:14) em Object.n [como fábrica] (math.min.js: 45) em t (math.min.js: 27) em f (math.min.js: 27) em Object.get [como mediana ] (math.min.js: 27) no clone (rawgit.com/ConorOBrien-Foxx/Jolf/master/src/jolf.js:902) em rawgit.com/ConorOBrien-Foxx/Jolf/master/src/jolf. js: 2128 (mais recente do Google Chrome, versão 55.0.2883.87m)
Ismael Miguel
@IsmaelMiguel Isso só deve trabalhar no firefox
Conor O'Brien
Eu não tinha idéia, não é em qualquer lugar
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
fonte
1
Vários testes dentro de um guarda pode ser combinado com ,em vez de &&: even z,z<0.
N
1

PowerShell , 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)])}

Chamada de demonstração:

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

Saída da demonstração:

-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
fonte
1

Lit , 88 bytes

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

Meu olhar para todos esses parênteses .

Experimente online!

Na verdade, não é muito pequeno. Atualmente, existe um erro de análise que requer um uso (get N)ou em (+ N)vez de simplesmente N. Eu escolhi o menor. No entanto, acho que não há nada que possa ser feito ainda mais para jogar golfe.

Andrakis
fonte