Definição
A sequência de Fibonacci F(n)
, nos números inteiros positivos, é definida como:
1. F(1) = 1
2. F(2) = 1
3. F(n) = F(n-1) + F(n-2), where n is an integer and n > 2
O Fibonacci-orial de um número inteiro positivo é o produto de [F(1), F(2), ..., F(n)]
.
Tarefa
Dado inteiro positivo n
, encontre o Fibonacci-orial de n
.
Especificações
O fibonacci-orial de 100
deve calcular em menos de 5 segundos em um computador razoável.
Casos de teste
n Fibonacci-orial of n
1 1
2 1
3 2
4 6
5 30
6 240
7 3120
8 65520
9 2227680
10 122522400
11 10904493600
12 1570247078400
13 365867569267200
14 137932073613734400
15 84138564904377984000
16 83044763560621070208000
17 132622487406311849122176000
18 342696507457909818131702784000
19 1432814097681520949608649339904000
20 9692987370815489224102512784450560000
100 3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
Respostas:
Mathematica, 10 bytes
Outro Mathematica embutido profundamente derrotado por uma linguagem de golfe sem o embutido.
fonte
Gelatina , 6 bytes
Insira 100 acabamentos em 500 ms localmente. Experimente online!
Como funciona
fonte
+¡1
um n-ésimo número de fibonacci e+С1
é o primeiro número de n-Fibonacci?Na verdade , 4 bytes
Executa a entrada 100 dentro de 0,2 segundos. Código:
Explicação:
Usa a codificação CP-437 . Experimente online! .
fonte
Brainfuck,
11981067817770741657611603Não compactado, com comentários:
Experimente online!
O tempo de execução para n = 100 é inferior a 1 segundo com o intérprete online (cerca de 0,2s localmente usando meu próprio intérprete). A entrada máxima é 255, mas exigiria que o intérprete suporte ~ 54000 células (o intérprete online parece quebrar em 64k).
Change Log
Economizou cerca de 130 bytes com melhor extração do dígito atual para multiplicar por, e mesclando adicionar e transportar em uma única passagem. Também parece ser um pouco mais rápido.
Salvo outros 250 bytes. Consegui reduzir meu bloco de rascunho de multiplicação em duas células, o que economiza bytes em quase todos os lugares por não ter que mudar tão longe entre os dígitos. Também larguei o transporte após multiplicar por um dígito e, em vez disso, executei um transporte completo enquanto adicionava ao total em execução.
Cortou outros 50, novamente com uma melhor extração do dígito atual para multiplicar, simplesmente não avançando a primeira iteração e trabalhando de onde está. Algumas micro-otimizações representam mais ou menos 10 bytes.
Mais 30 desaparecidos. A marcação de dígitos que já foram tirados com 0 e não com 1 torna mais fácil sua localização. Também verifica se o loop de multiplicação terminou um pouco mais simples.
Reduzi o bloco de rascunho por outra célula, por mais 80 bytes. Fiz isso mesclando o marcador do produto anterior e o total atual em execução, o que reduz os desvios entre as lacunas e facilita a contabilidade.
Economizou outros 50, eliminando mais uma célula, reutilizando o marcador para dígitos de fibonacci para marcar também o último dígito. Eu também pude mesclar o loop para mudar os totais anteriores com o loop de multiplicação digitado.
8 bytes salvos na análise de entrada. Opa
fonte
Python, 45 bytes
A entrada é retirada do stdin. A saída para n = 100 termina muito rapidamente para cronometrar com precisão. n = 1000 leva aproximadamente 1s.
Uso da amostra
fonte
Haskell
4129 Bytes1 + 11 bytes salvos pelas observações de @ Laikoni.
1
,f
E!!
são sinais separados. As primeiras linhas definem a sequência de fibonacci, a segunda é uma função que calcula a sequência de fibonacci-oriais e retorna a n-ésima para um dado n. Ele começa a imprimir dígitos quase imediatamente, mesmo para n = 1000.fonte
(scanl(*)1f!!)
.f=1:scanl(+)1f
42+
como uma função que adiciona 42? Você não deveria, porque é apenas uma expressão inacabada. Mas em Haskell podemos adicionar parênteses e obter a seção(42+)
, uma maneira de escrever a função\n->42+n
. Aqui está o mesmo, apenas com!!
(o operador de infixo binário para indexação) em vez de+
e um primeiro operando mais complicado.Python 2, 39 bytes
Teste em Ideone .
fonte
True
em alguns casos.True
para a entrada 0 , o que não é positivo.J,
1716 bytes1 byte é jogado com uma solução ainda melhor por milhas.
A idéia é a mesma que a original, mas em vez de formar a matriz para operar em diagonais menores, formamos as diagonais em tempo real.
Original
Para obter os primeiros n fibonomiais:
Lendo da direita para a esquerda ...
Crie a matriz de números inteiros consecutivos (
i.
) até a especificada. A partir dessa matriz, crie a tabela (/~
) de coeficientes binomiais (!
) calculada a partir de cada par na matriz. Essa tabela é o triângulo de Pascal no topo da posição em o final da primeira linha e todos os elementos na diagonal principal são 0, graças à implementação de!
. Se você soma (+/
) todas as diagonais menores (/.
), obtém os números de Fibonacci, mas precisa pegar ({.
) o máximo de elementos da matriz resultante como o comprimento (#
) da tabela em si. Em seguida, o produto (*/
) se aplicou a prefixos consecutivos (\
) da matriz resulta na sequência desejada de fibonorials.Se você quiser, pode pegar apenas o último usando mais 2 bytes ({:
), mas achei que exibir todos eles não é pecado:)
.NB. the previous code block is not a J function
.Para grandes números em J você usa
x
no final:O programa é executado na média 0.11s .
fonte
[:*/+/@(!|.)\@i.
usando 16 bytes. Ele forma os mesmos coeficientes binomiais ao longo da tabela que você gera usando,!/~
exceto que ele forma isso usando prefixos dei.
.Pitão, 13 bytes
Demonstração
Isso emprega um truque inteligente e não tipicamente seguro. Cinco dos caracteres (
u*G ... Q1
) dizem que a saída é o produto da entrada de muitos números. O restante do código gera os números.=[sZhZ)
atualiza a variávelZ
para a lista[s(Z), h(Z)]
. Em seguida,s
soma essa lista, a ser multiplicada.Z
é inicialmente 0.s
, em ints, é a função de identidade.h
, por si só, é a+ 1
função. Então, na primeira iteração,Z
torna-se[0, 1]
.s
nas listas é a função soma, como mencionado acima.h
é a função da cabeça. Portanto, a segunda iteração é[1, 0]
.Aqui está uma lista:
Essas somas são multiplicadas para dar o resultado.
fonte
Mathematica
2524 bytesCom agradecimentos a Martin Ender.
Tempo: 63 microssegundos.
fonte
1##&@@Fibonacci~Array~#&
Gelatina, 8 bytes
Minha primeira apresentação em Jelly. Não é tão curto quanto a resposta de @Dennis , mas possui apenas 2 bytes de comprimento com um método diferente.
Localmente, requer cerca de 400ms em comparação com 380ms na versão @Dennis 'para n = 100.
Experimente online!
Explicação
fonte
PARI / GP, 29 bytes
Ou alternativamente:
fonte
R,
9996787666 bytesEsta resposta é usa a fórmula de Binet , bem como a
prod(x)
função. Como R não tem umPhi
valor embutido, eu mesmo o defini:Funciona em menos de 5 segundos, mas R tende a dar
Inf
uma resposta para esses grandes números ...Ungolfed:
-2 bytes graças a @Cyoce!
Oh, eu amo este site! -10 bytes graças a @ user5957401
fonte
sqrt(5)
a uma variávelN
uma vez, basta ligar para a varredura dentro do1:N
bit. iefor(n in 1:scan())
. Você também pode salvar alguns caracteres usando apenas*
aprod()
função no loop for. Seu loop for é apenas uma linha, portanto você também não precisa de chaves.function(n,N=1:n,p=5^.5)prod(((1+p)^N-(1-p)^N)/2^N/p)
R,
82,53, 49 bytes (48 bytes com estilo de entrada diferente)Se pudermos preceder o código com o número de entrada, obteremos os 48 bytes
EDIT: novo código. O original está abaixo:
Não retornará nada além de Inf, no
a(100)
entanto. E não funcionará para nada além de números inteiros não negativos.Ungolfed:
fonte
Java, 165 bytes
Golfe:
Este é outro caso em que
BigInteger
é necessário devido a grandes números. No entanto, consegui manter o textoBigInteger
no mínimo, mantendo o tamanho baixo. Também comparei com importações estáticas e isso aumentou o comprimento total.Este programa funciona rastreando três números em uma matriz. Os dois primeiros são os dois números anteriores de Fibonacci. O terceiro é o valor acumulado. O loop inicia calculando o próximo valor e armazenando-o em índices de matriz alternados (0, 1, 0, 1, ...). Isso evita a necessidade de alterar valores com operações de atribuição caras (em termos de tamanho da fonte). Então pegue esse novo valor e multiplique-o no acumulador.
Evitando objetos temporários e limitando o loop a dois operadores de atribuição, consegui extrair alguns bytes.
Ungolfed:
Saída do programa:
fonte
Braquilog , 31 bytes
Experimente online!
fonte
Ruby, 39 bytes
fonte
Javascript (ES6),
5139 bytesImplementação recursiva (39 bytes)
Implementação original (51 bytes)
Nota: Inicia erros de arredondamento para o Fibonacci-orial de 16, 100 é apenas Infinito, é executado no que parece ser <1 segundo.
fonte
n=>[...Array(n)].reduce(p=>(c=a,a=b,p*=b+=c),a=1,b=0)
apenas para descobrir que você contou of=
que não é necessário, economizando 2 bytes.DC (versão GNU ou OpenBSD) , 36 bytes
Arquivo
A003266-v2.dc
:(sem nova linha à direita)
... agora o resultado é mantido na pilha em vez de usar um registrador nomeado (está
Y
na versão 1). Or
comando não está disponível no originaldc
(consulte a página Dc do RosettaCode ).Corre:
Tentando explicar:
tos
é o conteúdo do topo da pilha sem removê-lo.nos
é o elemento abaixotos
.DC , 41 bytes
... direto, sem truques:
Arquivo
A003266-v1.dc
:(sem nova linha à direita)
Corre:
fonte
dc
código definitivamente é mais fácil do que explicar isso ...n
itens principais para outra pilha de uma só vez. Por enquanto, ainda não sei como compilar adc
partir do código-fonte. : /C #
11010910710310194 BytesExplicação
Algoritmo Iterativo de Fib
fonte
Brain-Flak , 54 bytes
Experimente online!
A multiplicação no Brain-Flak leva muito tempo para grandes entradas. Apenas multiplicar F 100 por F 99 com um algoritmo de multiplicação genérico levaria bilhões de anos.
Felizmente, há uma maneira mais rápida. Uma sequência generalizada de Fibonacci começando com
(k, 0)
gerará os mesmos termos que a sequência usual, multiplicada pork
. Usando esta observação, o Brain-Flak pode se multiplicar por um número de Fibonacci tão facilmente quanto pode gerar números de Fibonacci.Se a pilha consistir em
-n
seguida por dois números,{({}()<([({})]({}{}))>)}{}{}
calculará asn
iterações da sequência generalizada de Fibonacci e descartará tudo pelo último. O restante do programa apenas configura o 1 inicial e o percorre para todos os números no intervalon...1
.Aqui está o mesmo algoritmo nos outros idiomas fornecidos por este intérprete:
Clássico Brain-Flak, 52 bytes
Experimente online!
Conduta cerebral, 58 bytes
Experimente online!
Mini-Flak, 62 bytes
Experimente online!
fonte
Mathematica -
3226 bytes@MartinEnder cortou 6 bytes!
fonte
GAP 28 bytes
Não sabia até hoje que o GAP tem um
Fibonacci
builtin.fonte
Ruby, 85 bytes
Acabou bem, mas provavelmente há uma solução mais curta.
Cálculo rápido de Fibonnaci retirado daqui: link
Teste aqui
fonte
Julia, 36 bytes
fonte
Flak cerebral ,
110104100 bytesExperimente online!
Explicação
Primeiro, rodamos uma versão aprimorada do gerador de sequência de Fibonacci, cortesia do Dr. Green Eggs e Iron Man
Enquanto a pilha possui mais de um item
multiplique os dois principais itens
e coloque o zero extra
fonte
Clojure, 70 bytes
Clojure não é realmente uma boa linguagem para o código de golfe. Ah bem.
Experimente em http://tryclj.com .
fonte
Quarto, 55 bytes
Utiliza uma abordagem iterativa, baseada na minha resposta de Fibonacci em Forth. Os resultados estouram aritmeticamente para
n > 10
. A resposta não diferencia maiúsculas de minúsculas.Experimente online
fonte
Swift, 68 bytes
fonte
JavaScript (ES6), 46 bytes
Usa variáveis de recursão e acumulador. Os erros de arredondamento começam em
f(16)
.fonte