Função ou sequência de Fibonacci

115

A sequência de Fibonacci é uma sequência de números, onde cada número na sequência é a soma dos dois números que a precedem. Os dois primeiros números da sequência são 1.

Aqui estão os primeiros termos

1 1 2 3 5 8 13 21 34 55 89 ...

Escreva o código mais curto que:

  • Gera a sequência de Fibonacci sem fim.

  • Dado ncalcula o ntermo th da sequência. (1 ou zero indexado)

Você pode usar formas padrão de entrada e saída.

(Dei as duas opções, caso uma seja mais fácil de fazer no idioma escolhido do que a outra.)


Para a função que recebe um n, um valor de retorno razoavelmente grande (o maior número de Fibonacci que se encaixa no tamanho normal de palavra do seu computador, no mínimo) deve ser suportado.


Entre os melhores

Chris Jester-Young
fonte

Respostas:

48

Perl 6, 10 caracteres:

Lista de sequências infinitas de fibonacci anônimas:

^2,*+*...*

Igual a:

0, 1, -> $x, $y { $x + $y } ... Inf;

Portanto, você pode atribuí-lo a uma matriz:

my @short-fibs = ^2, * + * ... *;

ou

my @fibs = 0, 1, -> $x, $y { $x + $y } ... Inf;

E obtenha os primeiros onze valores (de 0 a 10) com:

say @short-fibs[^11];

ou com:

say @fibs[^11];

Espere, você também pode obter os 50 primeiros números da própria lista anônima:

say (^2,*+*...*)[^50]

Isso retorna:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169
63245986 102334155 165580141 267914296 433494437 701408733 1134903170 
1836311903 2971215073 4807526976 7778742049

E uma referência simples:

real    0m0.966s
user    0m0.842s
sys     0m0.080s

Com:

$ time perl6 -e 'say (^2, *+* ... *)[^50]'

EOF

Marco Aurélio da Silva
fonte
Eu nem pensaria ^2nisso como substituto 0,1. +1
Konrad Borowski
2
Isso não é mais válido, você precisará escrevê-lo como |^2,*+*...*, que é o mesmo número de bytes que 0,1,*+*...*.
Brad Gilbert b2gills
5
Perl é tão estranho.
Cyoce 29/01
1
Em qual versão do Perl 6 essa resposta foi escrita?
CalculatorFeline
3
@CalculatorFeline Houve uma grande mudança conhecida como GLR (Great List Refactor), que aconteceu pouco antes do primeiro lançamento oficial, que foi em 25/12/2015. Este código teria funcionado até aquele momento.
Brad Gilbert b2gills
73

Brainfuck, 22 cursos

+>++[-<<[->+>+<<]>>>+]

Gera a sequência de Fibonacci movendo-se gradualmente pela fita de memória.

R. Martinho Fernandes
fonte
5
Bela! Litterally lindo! Ou talvez não ... de qualquer maneira +1 para este :)
Por Hornshøj-Schierbeck
2
Isso é 3.344 ou 4 bytes em fuso cerebral comprimido. (6 ln (22)) / ln (256)
Will Sherwood
24
16 bytes:+[[<+>->+>+<<]>]
primo
3
14 bytes:+[.[>+>+<<-]>]
Charlim
2
@ Stefnotch, é claro, o menor é destrutivo. A solução acima termina com a sequência de fibonacci na fita, que é o que a solução de 16 bytes também faz.
primo
51

Haskell, 17 15 14 caracteres

f=1:scanl(+)1f

Experimente online!

Anon.
fonte
4
Por que não cortar dois espaços para f=0:scanl(+)1 f?
R. Martinho Fernandes
@ Martinho: Editado, obrigado.
Anon.
Uau, isso é ainda mais curto do que o habitual f@(_:x)=0:1:zipWith(+)f x! Tem que lembrar disso.
FUZxxl
4
Você pode até mesmo tirar um outro espaço: f=0:scanl(+)1f.
FUZxxl
37

C # 4, 58 bytes

Stream (69; 65 se digitado de maneira fraca IEnumerable)

(Supondo uma usingdiretiva para System.Collections.Generic.)

IEnumerable<int>F(){int c=0,n=1;for(;;){yield return c;n+=c;c=n-c;}}

Valor único (58)

int F(uint n,int x=0,int y=1){return n<1?x:F(n-1,y,x+y);}
Jon Skeet
fonte
6
Dado que né um uint, n==0pode ser reduzido para n<1. E o fluxo pode salvar alguns caracteres abandonando o espaço após o tipo genérico e declarando xem um escopo mais amplo do que o necessário. Na verdade, abandonar xinteiramente:n+=c;c=n-c;
Peter Taylor
1
@ Peter: Obrigado, irá editar quando eu tiver algum tempo.
Jon Skeet
Sua versão de valor único é contanto que minha expressão lambda recursiva responda ... legal!
Andrew Gray
1
@ wizzwizz4 se não me engano, se !nfuncionar, o mesmo deveria acontecer nse você mudar de condicional.
Cyoce
3
@JonSkeet Aw. E aqui eu estava pensando que eu tinha batido Jon Skeet em C # ... :-)
wizzwizz4
32

GolfScript, 12

Agora, apenas 12 caracteres!

1.{[email protected]+.}do
jtjacques
fonte
+1 bom trabalho. Se você reduzir para 13 caracteres, aceitarei sua resposta instantaneamente (a menos que alguém faça uma resposta ainda mais curta, é claro). :-P
Chris Jester-Young
1
Eu amo um desafio. Feito! ;-)
jtjacques
Bom, você venceu. Pelo menos, até que alguém faça algo ainda mais curto (se é que isso é possível). :-P
Chris Jester-Young
5
essa definição é quase tão curta quanto o próprio nome 'Fibonacci'! +1
agent-j
23

> <> - 15 caracteres

0:nao1v LF a+@:n:<o
Kevin Brown
fonte
Embora você possa reduzi-lo, 0:nao1v LF a+@:n:<ose quiser. Dá 15 :) Na verdade, isso também faz com que a saída de um pouco mais legível ...
tomsmeding
5
13 caracteres:01r:nao$:@+$r
randomra
21

J, 10 caracteres

Usando o cálculo interno dos coeficientes da série Taylor, talvez seja um pouco mais barato. Aprendi aqui .

   (%-.-*:)t.

   (%-.-*:)t. 0 1 2 3 4 5 10 100
0 1 1 2 3 5 55 354224848179261915075
randomra
fonte
2
@aditsu (q:^-^:p) 6é 64 729onde p é par. J é provavelmente bom para o que faz enigmas. :)
randomra
2
Melhor ainda: (<:^-^:>) 4é 81e <:^-^:> 4é 53.5982.
randomra
2
O emoji demonstrado aqui é o que todo o código J deve buscar. Em uma nota lateral, outra alternativa está +/@:!&i.-usando 9 bytes.
milhas
1
@miles Muito bom! Você deve publicá-lo, pois é totalmente diferente do meu.
Random # 31/07/16
21

Hexagony ,18 14 12

Obrigado Martin por 6 bytes!

1="/}.!+/M8;

Expandido:

  1 = "
 / } . !
+ / M 8 ;
 . . . .
  . . .

Experimente online


Velho, responda. Isso está sendo deixado de lado porque as imagens e a explicação podem ser úteis para os novos usuários do Hexagony.

!).={!/"*10;$.[+{]

Expandido:

  ! ) .
 = { ! /
" * 1 0 ;
 $ . [ +
  { ] .

Isso imprime a sequência de Fibonacci separada por novas linhas.

Experimente online! Tenha cuidado, porém, o intérprete on-line realmente não gosta de saída infinita.

Explicação

Existem duas "sub-rotinas" para este programa, cada uma delas é executada por um dos dois IPs utilizados. A primeira rotina imprime novas linhas e a segunda faz o cálculo e a saída de Fibonacci.

A primeira sub-rotina começa na primeira linha e se move da esquerda para a direita o tempo todo. Primeiro, imprime o valor no ponteiro da memória (inicializado em zero) e depois incrementa o valor no ponteiro da memória 1. Após o no-op, o IP salta para a terceira linha que primeiro muda para outra célula de memória e depois imprime uma nova linha. Como uma nova linha tem um valor positivo (seu valor é 10), o código sempre passará para a quinta linha, a seguir. A quinta linha retorna o ponteiro da memória para o nosso número de Fibonacci e depois muda para a outra sub-rotina. Quando voltarmos desta sub-rotina, o IP voltará para a terceira linha, depois de executar um no-op.

A segunda sub-rotina começa no canto superior direito e começa a se mover para sudeste. Depois de um no-op, somos levados a viajar para o oeste ao longo da segunda linha. Esta linha imprime o número atual de Fibonacci, antes de mover o ponteiro de memória para o próximo local. Em seguida, o IP salta para a quarta linha, onde calcula o próximo número de Fibonacci usando os dois anteriores. Em seguida, ele devolve o controle à primeira sub-rotina, mas quando recupera o controle do programa, continua até encontrar um salto, onde salta sobre o espelho que foi originalmente usado para apontá-lo para o oeste, quando retorna à segunda linha.


Fotos bonitas preliminares!

O lado esquerdo da imagem é o programa, o lado direito representa a memória. A caixa azul é o primeiro IP e os dois estão apontando para a próxima instrução a ser executada.

insira a descrição da imagem aqui

Nota: As imagens podem parecer bonitas apenas para pessoas com habilidades igualmente limitadas nos programas de edição de imagens: o PI adicionará pelo menos mais duas iterações para que o uso do *operador fique mais claro.

Nota 2: Eu só vi a resposta de alefhalpha depois de escrever a maior parte disso, achei que ainda era valiosa por causa da separação, mas as partes reais de Fibonacci de nossos programas são muito semelhantes. Além disso, este é o menor programa Hexagony que eu já vi usando mais de um IP, então achei que seria bom manter assim: P

FryAmTheEggman
fonte
Você deve criar um link para o que você usou para fazer as fotos bonitas e depois colocar o link em esolangs.org/wiki/Hexagony .
mbomb007
1
@ mbomb007 Eu usei o gimp para criar manualmente cada quadro, depois enviei as imagens para algum site de criação de gif. Embora, várias vezes durante esse processo, considerei fazer uma ferramenta para fazê-lo, considerando o quão tedioso era.
FryAmTheEggman
@FryAmTheEggman Impressive! Faça disso um desafio. Tenho certeza que alguém postará uma resposta. : D Melhor ainda se você pudesse criar um site semelhante ao intérprete on-line do fish.
mbomb007
@ mbomb007 Isso pode ser um pouco ambicioso para um desafio neste site, sem mencionar que provavelmente sofreria muito por ser realmente amplo. Acho que não vou postar isso, mas fique à vontade para fazer isso sozinho, se você achar que tem uma boa maneira de apresentá-lo. Além disso, acredito que Timwi criou um C # ide para hexagonia, embora nunca o tenha usado porque não me incomodei com mono.
FryAmTheEggman
1
@ mbomb007 O ide mora aqui , aliás, esqueceu de ligá-lo da última vez.
FryAmTheEggman
18

COW , 108

 MoO moO MoO mOo MOO OOM MMM moO moO
 MMM mOo mOo moO MMM mOo MMM moO moO
 MOO MOo mOo MoO moO moo mOo mOo moo
Timtech
fonte
17

Python 2, 34 bytes

Python, usando recursão ... aqui vem um StackOverflow!

def f(i,j):print i;f(j,i+j)
f(1,1)
jtjacques
fonte
15

Gelatina , 3 bytes

+¡1

Experimente online!

Como funciona

+¡1    Niladic link. No implicit input.
       Since the link doesn't start with a nilad, the argument 0 is used.

  1    Yield 1.
+      Add the left and right argument.
 ¡     For reasons‡, read a number n from STDIN.
       Repeatedly call the dyadic link +, updating the right argument with
       the value of the left one, and the left one with the return value.

¡ espreita os dois links à esquerda. Como existe apenas um, ele deve ser o corpo do loop. Portanto, um número é lido da entrada. Como não há argumentos de linha de comando, esse número é lido em STDIN.

Dennis
fonte
12

Golfscript - número único - 12/11/10

12 caracteres para obter informações do stdin:

~0 1@{.@+}*;

11 caracteres para entrada já na pilha:

0 1@{.@+}*;

10 caracteres para definir mais 1 como o número 0 de Fibonacci:

1.@{.@+}*;
aaaaaaaaaaaa
fonte
1
A opção é "Calcula, dado o n-ésimo número de Fibonacci". Então abandone o ~e você tem 11 caracteres que assumem na pilha e deixam F_nna pilha.
Peter Taylor
12

Rubi

29 27 25 24 Chars

p a=b=1;loop{b=a+a=p(b)}

Edit: transformou em um loop infinito. ;)

st0le
fonte
13
alguém notou que b=a+a=bé um palíndromo? :)
st0le
2
sim st0le fez :)
gnibbler
Sei que estou atrasado para a festa, mas alguém pode explicar como a b=a+a=bpeça funciona? Não consigo envolver minha cabeça em torno disso.
Mr. Llama
3
@GigaWatt, Pense nisso desta maneira, as instruções são executadas esquerda para a direita ... entãonewb=olda+(a=oldb)
st0le
você pode salvar 2 caracteres usando loop:p 1,a=b=1;loop{p b=a+a=b}
Patrick Oscity
11

Mathematica, 9 caracteres

Fibonacci

Se funções internas não forem permitidas, aqui está uma solução explícita:

Mathematica, 33 32 31 caracteres

#&@@Nest[{+##,#}&@@#&,{0,1},#]&
celtschk
fonte
#&@@Nest[{#+#2,#}&@@#&,{0,1},#]&32 caracteres.
chyanog
1
@chyanog 31:#&@@Nest[{+##,#}&@@#&,{0,1},#]&
Mr.Wizard
1
@ Mr.Wizard 24 caracteres (26 bytes):Round[GoldenRatio^#/√5]&
JungHwan Min
1
ou 23 caracteres (27 bytes):Round[((1+√5)/2)^#/√5]&
JungHwan Min
10

DC (20 bytes)

Como um bônus, é até ofuscado;)

zzr[dsb+lbrplax]dsax

EDIT: Posso salientar que ele imprime todos os números na sequência de fibonacci, se você esperar o suficiente.

Hiato
fonte
13
Eu não chamaria isso de ofuscado - o código ofuscado deve ser difícil de entender e, no que diz respeito à CC, o código aqui é completamente direto.
Nabb 6/02/11
10

Prelúdio , 12 bytes

Um dos poucos desafios em que o Prelude é realmente bastante competitivo:

1(v!v)
  ^+^

Isso requer o interpretador Python, que imprime valores como números decimais em vez de caracteres.

Explicação

No Prelude, todas as linhas são executadas em paralelo, com o ponteiro da instrução percorrendo as colunas do programa. Cada linha tem sua própria pilha, que é inicializada em zero.

1(v!v)
  ^+^
| Push a 1 onto the first stack.
 | Start a loop from here to the closing ).
  | Copy the top value from the first stack to the second and vice-versa.
   | Print the value on the first stack, add the top two numbers on the second stack.
    | Copy the top value from the first stack to the second and vice-versa.

O loop se repete para sempre, porque a primeira pilha nunca terá um 0no topo.

Observe que isso inicia a sequência de Fibonacci 0.

Martin Ender
fonte
10

Hexagonia , 6 bytes

Não competir porque o idioma é mais recente que a questão.

1.}=+!

Ungolfed:

  1 .
 } = +
  ! .

Imprime a sequência de Fibonacci sem nenhum separador.

alefalpha
fonte
2
Isso tem o pequeno problema de não imprimir nenhum separador entre os números. Isso não está totalmente bem especificado no desafio. (E eu estou realmente feliz que alguém está usando Hexagony :).)
Martin Ender
9

TI-BASIC, 11

Pelo lendário jogador de golfe TI-BASIC Kenneth Hammond ("Weregoose"), deste site . É executado no tempo O (1) e considera 0 como o 0º termo da sequência de Fibonacci.

int(round(√(.8)cosh(Anssinh‾¹(.5

Usar:

2:int(round(√(.8)cosh(Anssinh‾¹(.5
                                     1

12:int(round(√(.8)cosh(Anssinh‾¹(.5
                                     144

Como é que isso funciona? Se você fizer as contas, sinh‾¹(.5)é igual a ln φ, então é uma versão modificada da fórmula de Binet que arredonda para baixo em vez de usar o (1/φ)^ntermo de correção. A round((arredondar para 9 casas decimais) é necessária para evitar erros de arredondamento.

Thomas Kwa
fonte
8

K - 12

Calcula o número ne n-1Fibonacci.

{x(|+\)/0 1}

Apenas o nthnúmero de Fibonacci.

{*x(|+\)/0 1}
isawdrones
fonte
+1 Nada mal! Se você puder reduzir apenas um caractere (e me fornecer uma maneira de testá-lo), aceitarei sua resposta. :-)
Chris Jester-Young
A única maneira de diminuir isso seria substituir a função por uma chamada para um número conhecido: n (| + \) / 0 1 Teste-a usando este intérprete .
Isawdrones
7

Julia, 18 bytes

n->([1 1;1 0]^n)[]
Rɪᴋᴇʀ
fonte
7

Java, 55

Não posso competir com a concisão da maioria dos idiomas aqui, mas posso oferecer uma maneira substancialmente diferente e possivelmente muito mais rápida (tempo constante) para calcular o n-ésimo número:

Math.floor(Math.pow((Math.sqrt(5)+1)/2,n)/Math.sqrt(5))

né a entrada (int ou longa), iniciando com n = 1. Ele usa a fórmula e os arredondamentos de Binet em vez da subtração.

Hans-Peter Störr
fonte
Eu amo esta solução
Andreas
Isso não parece funcionar para mim, mas é cedo e posso estar perdendo alguma coisa! Assumindo 0para ser o primeiro número na sequência, isto dá 0, 0, 1, 1, 3, 4, 8, 12, 21, 33para os primeiros 10 números
Salsicha
@Shaggy Oops! Desculpe, eu apresentei um bug - corrigido agora.
Hans-Peter Störr
6

Ruby, 25 caracteres

a resposta de st0le foi reduzida.

p 1,a=b=1;loop{p b=a+a=b}
Matma Rex
fonte
6
Na verdade, você pode reduzi-lo ainda mais usandoa=b=1;loop{p a;b=a+a=b}
Ventero
6
Então você continua a resposta dele? : P
mbomb007 20/01
6

FAC: APL funcional, 4 caracteres (!!)

Não é meu, portanto, publicado como wiki da comunidade. FAC é um dialeto da APL que Hai-Chen Tu aparentemente sugeriu como sua dissertação de doutorado em 1985. Mais tarde, ele escreveu um artigo em conjunto com Alan J. Perlis chamado " FAC: uma linguagem funcional da APL ". Esse dialeto do APL usa "matrizes preguiçosas" e permite matrizes de tamanho infinito. Ele define um operador "iter" ( ) para permitir a definição compacta de algumas seqüências recursivas.

O caso monádico ("unário") é basicamente de Haskell iteratee é definido como (F⌼) A ≡ A, (F A), (F (F A)), …. A ( "binário") caso dyadic é definido um pouco analogamente para duas variáveis: A (F⌼) B ≡ A, B, (A F B), (B F (A F B)), …. Por que isso é útil? Bem, como se vê, esse é precisamente o tipo de recorrência da sequência de Fibonacci. De fato, um dos exemplos dados é

1+⌼1

produzindo a sequência familiar 1 1 2 3 5 8 ….

Então, lá está, possivelmente a menor implementação possível de Fibonacci em uma linguagem de programação que não é novidade. : D

FireFly
fonte
Ah, acidentalmente desclassifiquei sua postagem como parte da minha desaprovação em massa (manual). Ah bem. ;-)
Chris Jester-Young
6

R, 40 bytes

Não vi uma solução R, então:

f=function(n)ifelse(n<3,1,f(n-1)+f(n-2))
plannapus
fonte
1
Eu sei que esta é uma resposta antiga, mas você pode encurtar para 38 bytes
Robert S.
6

05AB1E, 7 bytes

Código:

1$<FDr+

Experimente online!

Vimlesh
fonte
3
Olá, e bem-vindo ao PPCG! Bom primeiro post!
Rɪᴋᴇʀ
6

Dodos , 26 bytes

	dot F
F
	F dip
	F dip dip

Experimente online!

Como funciona

A função F faz todo o trabalho pesado; é definido recursivamente da seguinte maneira.

F(n) = ( F(|n - 1|), F(||n - 1| - 1|) )

Sempre que n> 1 , temos | n - 1 | = N - 1 <n e || n - 1 | 1 | = | n - 1 - 1 | = n - 2 <n , então a função retorna (F (n - 1), F (n - 2)) .

Se n = 0 , então | n - 1 | = 1> 0 ; se n = 1 , então || n - 1 | 1 | = | 0 - 1 | = 1 = 1 . Nos dois casos, as tentativas de chamadas recursivas F (1) geram uma exceção Surrender , então F (0) retorna 0 e F (1) retorna 1 .

Por exemplo, F (3) = (F (1), F (2)) = (1, F (0), F (1)) = (1, 0, 1) .

Finalmente, a função principal é definida como

main(n) = sum(F(n))

por isso acrescenta-se todas as coordenadas do vetor retornado por F .

Por exemplo, main (3) = soma (F (3)) = soma (1, 0, 1) = 2 .

Dennis
fonte
5

Desmos , 61 bytes

Golfe

Clique no add sliderbotão para n.

p=.5+.5\sqrt{5}
n=0
f=5^{-.5}\left(p^n-\left(-p\right)^{-n}\right)

A última linha é a saída.

Ungolfed

É uma função.

\phi =\frac{1+\sqrt{5}}{2}
f_{ibonacci}\left(n\right)=\frac{\phi ^n-\left(-\phi \right)^{-n}}{\sqrt{5}}
Conor O'Brien
fonte
5

Cubix , 10 bytes

Resposta não concorrente porque o idioma é mais recente que a pergunta.

Cubix é uma nova linguagem bidimensional da @ETHproductions onde o código é envolvido em um cubo dimensionado para caber.

;.o.ON/+!)

Experimente online

Isso envolve um cubo 2 x 2 da seguinte maneira

    ; .
    o .
O N / + ! ) . .
. . . . . . . .
    . .
    . .
  • O emitir o valor dos TOS
  • N empurrar nova linha para a pilha
  • / refletir norte
  • o gera o caractere do TOS
  • ; pop TOS
  • / refletir leste depois de dar a volta no cubo
  • + adicione os 2 principais valores da pilha
  • ! pule o próximo comando se o TOS for 0
  • ) aumente os TOS em 1. Isso inicia a sequência essencialmente.

Esse é um loop sem fim que imprime a sequência com um separador de nova linha. Aproveita o fato de a maioria dos comandos não exibir os valores da pilha.
Se o separador for ignorado, isso poderá ser feito com 5 bytes.O+!)

MickyT
fonte
5

Brainfuck, 16,15, 14/13 caracteres

+[[->+>+<<]>]  

Gera a sequência de Fibonacci e não imprime nada. Além disso, é mais curto que o acima.

+[.[->+>+<<]>]   

Este possui 14 caracteres, mas imprime caracteres ASCII com os valores da sequência de Fibonacci.

Stefnotch
fonte
1
Isso é bom, mas eu estaria incorreto ao dizer que a versão de 14 bytes sai somente do 2º 1 em diante? Como em "1 2 3 5 8" em vez de "1 1 2 3 5 8"?
Charlim
1
@Charlim Oh, você está certo. Não faço ideia do que pensava eu ​​em 2014. Enfim, eu apenas consertei movendo a instrução de impressão para a frente do loop.
Stefnotch 12/02