Fibonacci-orial

36

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 100deve 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

Referências

Freira Furada
fonte
Relacionado .
Freira vazada
1
@LuisMendo A soma de fibonacci é ... você adivinhou, fibonacci. Bem, menos um.
Freira vazando
2
@LeakyNun Atualmente, a resposta JavaScript conclui apenas os casos de teste até 15, porque o JavaScript não pode comparar (ou manipular) números corretamente além de 2 ^ 53 - 1. É provavelmente semelhante a muitos envios aqui, porque a maioria dos idiomas não números de suporte que grande #
MayorMonty 30/07/16
1
O que você quer dizer com "computador razoável"?
Erik the Outgolfer
2
-1 porque parece que vários desafios foram enfrentados juntos (intervalo, fibonacci de cada fatorial), sem atalhos particularmente interessantes.
Esolanging Fruit

Respostas:

63

Mathematica, 10 bytes

Fibonorial

Outro Mathematica embutido profundamente derrotado por uma linguagem de golfe sem o embutido.

Martin Ender
fonte
49
Eu ... o que ... por que, Mathematica ?!
30416 Lynn
3
Esqueceu que a função ainda existia!
precisa
3
@ Regra 35 de Lynn : Se existir, existe uma função do Mathematica;)
Decay Beta
9
@BetaDecay Eu pensei que tínhamos estabelecido que é a Regra 110 .
Martin Ender
1
Não, a regra 110 é algo muito diferente. Embora eu tenha certeza que o Mathematica também tem um recurso para isso.
AdmBorkBork
27

Gelatina , 6 bytes

+С1ḊP

Insira 100 acabamentos em 500 ms localmente. Experimente online!

Como funciona

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

   1    Yield 1.
+       Add the left and right argument.
 С     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.
        Collect all values of the left argument into an array.
    Ḋ   Dequeue; discard the first Fibonacci number (0).
     P  Product; multiply the remaining ones.
Dennis
fonte
Então, é +¡1um n-ésimo número de fibonacci e +С1é o primeiro número de n-Fibonacci?
caird coinheringaahing
@cairdcoinheringaahing Pretty much.
Dennis
Eu pensei que havia uma função de fibonacci embutida?
MilkyWay90 17/03
21

Na verdade , 4 bytes

Executa a entrada 100 dentro de 0,2 segundos. Código:

R♂Fπ

Explicação:

R     # Get the range [1, ..., input].
 ♂F   # Map over the array with the fibonacci command.
   π  # Take the product.

Usa a codificação CP-437 . Experimente online! .

Adnan
fonte
1
Esta é a ferramenta certa para o trabalho :) Graças a algumas melhorias na função Fibonacci que a Leaky Nun recuperou há algum tempo, o caso de teste 100 é executado em 0,1 segundos no TIO .
Mego
16

Brainfuck, 1198 1067 817 770 741 657 611 603

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

Não compactado, com comentários:

# parse input (max 255)
,[>++++++[-<-------->]<<[->++++++++++<]>>,]
>+>+>>+>+<<<<<<
[->>>
  # compute next fibonacci number
  [[-]<
    [->+<]>>
    [-<+<+>>]<
    # perform carries
    [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<
      [->[-]>>>>>>+>+<<<<<<<<[->+<]]
    ]]]]]]]]]+>>>>>>>>
  ]<<<<<<<<
  # multiplication
  [->
    # extract next digit of F_n (most significant first)
    [-<+<<+>>>]<
    [->+<]>>>
    # move back to the end
    [<<<<<
      [->>>>>>>>+<<<<<<<<]>>>>>>>>>>>>>
    ]<<<<<<<<
    # digit wise multiplication (shifting current digit)
    [->>>
      [-<<<<<<<<+>>>>
        [->+>>+<<<]>
        [-<+>]>>>
      ]<<
      # shift previous total over one gap (in effect multiplying by 10)
      [->>>>>>>+>+<<<<<<<<]<+<<<<<<<<
    ]>>>[-]>>>>>
    # add product to total
    [[-]>
      [->+<]>
      # perform carries
      [-<+>
        [-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>
          [->>>>>>+>+<<<<<<<<[-]]
        ]]]]]]]]>
      ]<<[<]+>>>>>>>>
    ]<<<<<<<<
    [<<<<<<<<]>>>>>
    [>>>>>>>>]+<<<<<<<<
  ]>>>>>>>>>>>
  # overwrite previous product
  [<[-]>>
    [-<<+>>]>>>>>>>
  ]<<<<<<<<
  [<<<<<<<<]>>
]>>>>>>
# output product
[>>>>>>>>]<<<<<<<<
[+++++
  [-<++++++++>]<.<<<<<<<
]

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

primo
fonte
14

Python, 45 bytes

a=b=o=1
exec"o*=a;a,b=b,a+b;"*input()
print o

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

$ echo 10 | python fib-orial.py
122522400

$ echo 100 | python fib-orial.py
3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
primo
fonte
13

Haskell 41 29 Bytes

1 + 11 bytes salvos pelas observações de @ Laikoni.

f=1:scanl(+)1f
(scanl(*)1f!!)

1, fE !!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.

Peneiradores cristãos
fonte
1
Você pode se livrar do espaço (scanl(*)1f!!).
Laikoni 30/07
2
E há um gerador de Fibonacci mais curto aqui :f=1:scanl(+)1f
Laikoni
@Laikoni Isso é incrível, obrigado!
Christian Sievers
2
@WillNess Acho que não apenas sou justificado pelo que os outros usuários fazem, mas também por meta.codegolf.stackexchange.com/questions/2419/… e meta.codegolf.stackexchange.com/questions/9031/… (mas existe um muito mais e eu não li tudo)
Christian Sievers
1
@flawr Você aceitaria 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.
Christian Sievers
11

Python 2, 39 bytes

f=lambda n,a=1,b=1:n<1or a*f(n-1,b,a+b)

Teste em Ideone .

Dennis
fonte
Você pode especificar que ele retorna Trueem alguns casos.
Leaky Nun
5
Isso retornaria apenas Truepara a entrada 0 , o que não é positivo.
Dennis
6

J, 17 16 bytes

1 byte é jogado com uma solução ainda melhor por milhas.

[:*/+/@(!|.)\@i.

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:

*/\(#{.+//.)!/~i.

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.

   {:*/\(#{.+//.)!/~i. 10
122522400

Para grandes números em J você usa xno final:

   {:*/\(#{.+//.)!/~i. 100x
3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225...

O programa é executado na média 0.11s .

   100 timex '{:*/\(#{.+//.)!/~i.100x'
0.112124
Dan Oak
fonte
1
Uma alternativa que é uma função está [:*/+/@(!|.)\@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 de i..
milhas
4

Pitão, 13 bytes

u*Gs=[sZhZ)Q1

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ável Zpara a lista [s(Z), h(Z)]. Em seguida, ssoma essa lista, a ser multiplicada.

Zé inicialmente 0. s, em ints, é a função de identidade.h, por si só, é a + 1função. Então, na primeira iteração, Ztorna-se [0, 1]. snas 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:

Iter  Z          Sum
0     0          Not used
1     [0, 1]     1
2     [1, 0]     1
3     [1, 1]     2
4     [2, 1]     3
5     [3, 2]     5

Essas somas são multiplicadas para dar o resultado.

isaacg
fonte
4

Mathematica 25 24 bytes

Com agradecimentos a Martin Ender.

1##&@@Fibonacci@Range@#&

1##&@@Fibonacci@Range@#&@100

Tempo: 63 microssegundos.

{0.000063, 
3371601853146468125386964065447576689828006172937411310662486977801540
6711385898686165008341900290675836651822917015531720110825745874313823
1009903039430687777564739516714333248356092511296002464445971530050748
1235056111434293619038347456390454209587101225261757371666449068625033
9995735521655245297254676280601708866020010771376138030271586483293355
0772869860576999281875676563330531852996518618404399969665040724619325
7877568825245646129366994079739720698147440310773871269639752334356493
6789134243905645353892122400388956268116279491329780860702550826683922
9003714114129148483959669418215206272639036409444764264391237153249138
8089634845995941928089653751672688740718152064107169357399466473375804
9722605947689699525073466941890502338235963164675705844341280523988912
2373033501909297493561702963891935828612435071136036127915741683742890
4150054292406756317837582840596331363581207781793070936765786629772999
8328572573496960944166162599743042087569978353607028409125185326833249
36435856348020736000000000000000000000000}
DavidC
fonte
Como alternativa, com a mesma contagem de bytes:1##&@@Fibonacci~Array~#&
Greg Martin
4

Gelatina, 8 bytes

RḶUc$S€P

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

RḶUc$S€P  Input: n
R         Generate the range [1, 2, ..., n]
          For each value x in that range
 Ḷ          Create another range [0, 1, ..., x-1]
  U         Reverse that list
   c        Compute the binomial coefficients between each pair of values
    $       Bind the last two links (Uc) as a monad
     S€   Sum each list of binomial coefficients
          This will give the first n Fibonacci numbers
       P  Take the product of those to compute the nth Fibonacci-orial
milhas
fonte
3

PARI / GP, 29 bytes

f=n->prod(i=1,n,fibonacci(i))

Ou alternativamente:

f=n->prod(i=a=!b=0,n,b=a+a=b)
primo
fonte
3

R, 99 96 78 76 66 bytes

Esta resposta é usa a fórmula de Binet , bem como a prod(x)função. Como R não tem um Phivalor embutido, eu mesmo o defini:

p=(1+sqrt(5))/2;x=1;for(n in 1:scan())x=x*(p^n-(-1/p)^n)/sqrt(5);x

Funciona em menos de 5 segundos, mas R tende a dar Infuma resposta para esses grandes números ...

Ungolfed:

r=sqrt(5)
p=(1+r)/2 
x=1
for(n in 1:scan())        
    x=x*(p^n-(-1/p)^n)/r    
x

-2 bytes graças a @Cyoce!
Oh, eu amo este site! -10 bytes graças a @ user5957401

Frédéric
fonte
Pode ser capaz de guardar um pouco, armazenando sqrt(5)a uma variável
Cyoce
Como você usa apenas Numa vez, basta ligar para a varredura dentro do 1:Nbit. ie for(n in 1:scan()). Você também pode salvar alguns caracteres usando apenas *a prod()função no loop for. Seu loop for é apenas uma linha, portanto você também não precisa de chaves.
usuário5957401
Boa ideia usar a fórmula de Binet. Em seu espírito, mas apenas 53 bytes é #function(n,N=1:n,p=5^.5)prod(((1+p)^N-(1-p)^N)/2^N/p)
Michael M #:
3

R, 82 , 53 , 49 bytes (48 bytes com estilo de entrada diferente)

b=d=1;a=0;for(i in 1:scan()){d=d*b;b=a+b;a=b-a};d

Se pudermos preceder o código com o número de entrada, obteremos os 48 bytes

->n;b=d=1;a=0;for(i in 1:n){d=d*b;b=a+b;a=b-a};d

EDIT: novo código. O original está abaixo:

a=function(n)ifelse(n<3,1,{v=c(1,1,3:n);for(i in 3:n)v[i]=v[i-1]+v[i-2];prod(v)})

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:

a=function(n){
   if(n<3) return(1)
   v=c(1,1,3:n)
   for(i in 3:n)
       v[i]=v[i-1]+v[i-2]
   prod(v)
}
user5957401
fonte
3

Java, 165 bytes

Golfe:

BigInteger f(int n){BigInteger[]a={BigInteger.ZERO,BigInteger.ONE,BigInteger.ONE};for(int i=0;i<n;){a[++i%2]=a[0].add(a[1]);a[2]=a[2].multiply(a[i%2]);}return a[2];}

Este é outro caso em que BigIntegeré necessário devido a grandes números. No entanto, consegui manter o texto BigIntegerno 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:

import java.math.BigInteger;

public class Fibonacci_orial {

  public static void main(String[] args) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "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" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println("Input: " + data[0]);
      System.out.println("Expected: " + data[1]);
      System.out.print("Actual:   ");
      System.out.println(new Fibonacci_orial().f(Integer.parseInt(data[0])));
      System.out.println();
    }
  }

  // Begin golf
  BigInteger f(int n) {
    BigInteger[] a = { BigInteger.ZERO, BigInteger.ONE, BigInteger.ONE };
    for (int i = 0; i < n;) {
      a[++i % 2] = a[0].add(a[1]);
      a[2] = a[2].multiply(a[i % 2]);
    }
    return a[2];
  }
  // End golf

}

Saída do programa:

Input: 1
Expected: 1
Actual:   1

Input: 2
Expected: 1
Actual:   1

Input: 3
Expected: 2
Actual:   2

Input: 4
Expected: 6
Actual:   6

Input: 5
Expected: 30
Actual:   30

Input: 6
Expected: 240
Actual:   240

Input: 7
Expected: 3120
Actual:   3120

Input: 8
Expected: 65520
Actual:   65520

Input: 9
Expected: 2227680
Actual:   2227680

Input: 10
Expected: 122522400
Actual:   122522400

Input: 11
Expected: 10904493600
Actual:   10904493600

Input: 12
Expected: 1570247078400
Actual:   1570247078400

Input: 13
Expected: 365867569267200
Actual:   365867569267200

Input: 14
Expected: 137932073613734400
Actual:   137932073613734400

Input: 15
Expected: 84138564904377984000
Actual:   84138564904377984000

Input: 16
Expected: 83044763560621070208000
Actual:   83044763560621070208000

Input: 17
Expected: 132622487406311849122176000
Actual:   132622487406311849122176000

Input: 18
Expected: 342696507457909818131702784000
Actual:   342696507457909818131702784000

Input: 19
Expected: 1432814097681520949608649339904000
Actual:   1432814097681520949608649339904000

Input: 20
Expected: 9692987370815489224102512784450560000
Actual:   9692987370815489224102512784450560000

Input: 100
Expected: 3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
Actual:   3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000

fonte
2

Ruby, 39 bytes

->n{f=i=b=1;n.times{f,i,b=i,f+i,b*f};b}
Lynn
fonte
36: -> n {f = i = b = 1; n vezes {b * = f; i = f + f = i}; b}
GB
2

Javascript (ES6), 51 39 bytes

Implementação recursiva (39 bytes)

f=(n,a=p=i=b=1)=>++i<n?f(n,b,p*=b+=a):p

Implementação original (51 bytes)

n=>{for(i=a=b=p=1;++i<n;){c=a;a=b;p*=b+=c}return p}

Nota: Inicia erros de arredondamento para o Fibonacci-orial de 16, 100 é apenas Infinito, é executado no que parece ser <1 segundo.

Pandacoder
fonte
Fiz uma versão alternativa de 53 bytes n=>[...Array(n)].reduce(p=>(c=a,a=b,p*=b+=c),a=1,b=0)apenas para descobrir que você contou o f=que não é necessário, economizando 2 bytes.
Neil
Ponto justo. Minha lógica era que era aceitável e reutilizável, e não apenas aceitável.
Pandacoder
Claro, mas se alguém quiser reutilizá-lo, ainda terá a opção de nomeá-lo.
Neil
@ Neil Bem, agora eu fui re-implementado e agora o f = é obrigatório ou então ele não pode realmente ser executado. : D
Pandacoder
Bem, pelo menos você corrigiu a contagem de bytes para a implementação original.
Neil
2

DC (versão GNU ou OpenBSD) , 36 bytes

Arquivo A003266-v2.dc:

0sA1sB1?[1-d0<LrlBdlA+sBdsA*r]dsLxrp

(sem nova linha à direita)

... agora o resultado é mantido na pilha em vez de usar um registrador nomeado (está Yna versão 1). O rcomando não está disponível no original dc(consulte a página Dc do RosettaCode ).

Corre:

$ time dc -f A003266-v2.dc <<< 100
337160185314646812538696406544757668982800617293741131066248697780154\
067113858986861650083419002906758366518229170155317201108257458743138\
231009903039430687777564739516714333248356092511296002464445971530050\
748123505611143429361903834745639045420958710122526175737166644906862\
503399957355216552452972546762806017088660200107713761380302715864832\
933550772869860576999281875676563330531852996518618404399969665040724\
619325787756882524564612936699407973972069814744031077387126963975233\
435649367891342439056453538921224003889562681162794913297808607025508\
266839229003714114129148483959669418215206272639036409444764264391237\
153249138808963484599594192808965375167268874071815206410716935739946\
647337580497226059476896995250734669418905023382359631646757058443412\
805239889122373033501909297493561702963891935828612435071136036127915\
741683742890415005429240675631783758284059633136358120778179307093676\
578662977299983285725734969609441661625997430420875699783536070284091\
2518532683324936435856348020736000000000000000000000000

real    0m0.005s
user    0m0.004s
sys     0m0.000s

Tentando explicar:

tosé o conteúdo do topo da pilha sem removê-lo.
nosé o elemento abaixo tos.

0 sA # push(0) ; A=pop()
1 sB # push(1) ; B=pop()
1    # push(1)
     # this stack position will incrementally hold the product
?    # push( get user input and evaluate it )
[    # start string
 1-  # push(pop()-1)
 d   # push(tos)
 0   # push(0)
 <L  # if pop() < pop() then evaluate contents of register L
 r   # exchange tos and nos
     # now nos is the loop counter
     # and tos is the bucket for the product of the fibonacci numbers
 lB  # push(B)
 d   # push(tos)
 lA  # push(A)
 +   # push(pop()+pop())
     # now tos is A+B, nos still is B 
 sB  # B=pop()
     # completes B=A+B
 d   # push(tos)
 sA  # A=pop()
     # completes B=A
     # tos (duplicated new A from above) is the next fibonacci number
 *   # push(nos*tos)
     # tos now is the product of all fibonacci numbers calculated so far
 r   # exchange tos and nos
     # now tos is the loop counter, nos is the product bucket
]    # end string and push it
d    # push(tos)
sL   # L=pop()
x    # evaluate(pop())
r    # exchange tos and nos
     # nos now is the former loop counter
     # tos now is the complete product. \o/
p    # print(tos)
     # this does not pop() but who cares? :-P

DC , 41 bytes

... direto, sem truques:

Arquivo A003266-v1.dc:

0sA1sB1sY?[1-d0<LlBdlA+sBdsAlY*sY]dsLxlYp

(sem nova linha à direita)

Corre:

$ for i in $(seq 4) ; do dc -f A003266-v1.dc <<< $i ; done
1
1
2
6
$ time dc -f A003266-v1.dc <<< 100
337160185314646812538696406544757668982800617293741131066248697780154\
067113858986861650083419002906758366518229170155317201108257458743138\
231009903039430687777564739516714333248356092511296002464445971530050\
748123505611143429361903834745639045420958710122526175737166644906862\
503399957355216552452972546762806017088660200107713761380302715864832\
933550772869860576999281875676563330531852996518618404399969665040724\
619325787756882524564612936699407973972069814744031077387126963975233\
435649367891342439056453538921224003889562681162794913297808607025508\
266839229003714114129148483959669418215206272639036409444764264391237\
153249138808963484599594192808965375167268874071815206410716935739946\
647337580497226059476896995250734669418905023382359631646757058443412\
805239889122373033501909297493561702963891935828612435071136036127915\
741683742890415005429240675631783758284059633136358120778179307093676\
578662977299983285725734969609441661625997430420875699783536070284091\
2518532683324936435856348020736000000000000000000000000

real    0m0.006s
user    0m0.004s
sys     0m0.004s

fonte
1
* suspiro * ... escrever dccódigo definitivamente é mais fácil do que explicar isso ...
1
Sim, nós realmente precisamos de um IDE com algum tipo de dispositivo de visualização de múltiplas pilhas ... isso seria ótimo.
Joe
1
Tenho várias idéias para adicionar como novos comandos, mas a idéia com maior impacto parece ser: Adicione um comando "alterar pilha padrão". ;-)
2
... ou troque a pilha padrão por um registrador nomeado. Isso tornaria mais nós nos cérebros dos usuários, mas não seria necessário a pilha padrão para ter um nome ...] :-)
1
Sim, isso definitivamente seria útil! Também gostaria de limpar um único item, girar itens que não estão no topo da pilha e talvez mudar os nitens principais para outra pilha de uma só vez. Por enquanto, ainda não sei como compilar a dcpartir do código-fonte. : /
Joe
2

C # 110 109 107 103 101 94 Bytes

using i=System.Numerics.BigInteger;i f(i n){i a=0,b=1,x=1;for(;n-->0;)x*=a=(b+=a)-a;return x;}

Explicação

//Aliasing BigInteger saves a few bytes
using i=System.Numerics.BigInteger;

//Since BigInteger has an implicit from int we can also change the input
//and save two more bytes.
i f(i n)
{
    //using an alternative iterative algorithm (link to source below) to cut out the temp variable
    //b is next iteration, a is current iteration, and x is the running product
    i a = 0, b = 1, x = 1; 

    //post decrement n down to zero instead of creating a loop variable
    for (; n-- > 0;)

        //The bracket portion sets the next iteration             
        //get the current iteration and update our running product
        x *= a = (b += a) - a;

    return x;
}

Algoritmo Iterativo de Fib

JustinM - Restabelecer Monica
fonte
Dado que esse desempenho foi muito melhor do que eu esperava, eu queria encontrar o N máximo que retornaria em menos de 5 segundos, eu saí com 1540, que fornece um número com 247441 dígitos.
JustinM - Restabelece Monica
Impressionante. Quanto tempo 1541 leva para calcular, por curiosidade?
precisa saber é o seguinte
@ Pandacoder Então, com a recente mudança no algoritmo, ele ficou significativamente mais rápido. 1541 em 755 ms, então eu vou encontrar o novo sub 5 max agora.
JustinM - Restabelece Monica
@Pandacoder de modo que o tempo de execução é variável por um bocado justo ~ 100ms, mas 2565 parece média, cerca de 5 segundos
JustinM - Reintegrar Monica
Quanto tempo dura o número para isso?
precisa saber é o seguinte
2

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 por k. 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 -nseguida por dois números, {({}()<([({})]({}{}))>)}{}{}calculará as niteraçõ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 intervalo n...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!

Nitrodon
fonte
1

Mathematica - 32 26 bytes

Fibonacci@i~Product~{i,#}&

@MartinEnder cortou 6 bytes!

Yytsi
fonte
1

GAP 28 bytes

Não sabia até hoje que o GAP tem um Fibonaccibuiltin.

n->Product([1..n],Fibonacci)
Peneiradores cristãos
fonte
Você pode criar um link para o GAP? Não faço ideia do que é.
Freira vazando
Ah, claro (mas eu não sou o primeiro a usá-lo aqui ...)
Christian Sievers
1

Ruby, 85 bytes

g =->x{(1..x).to_a.collect{|y|(0..y).inject([1,0]){|(a,b),_|[b, a+b]}[0]}.inject(:*)}

Acabou bem, mas provavelmente há uma solução mais curta.

Cálculo rápido de Fibonnaci retirado daqui: link

Teste aqui

Seims
fonte
1

Julia, 36 bytes

!x=[([1 1;1 0]^n)[2]for n=1:x]|>prod
Lynn
fonte
1

Flak cerebral , 110 104 100 bytes

Experimente 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

{}
Assistente de Trigo
fonte
1
Infelizmente, acho que isso é inválido, pois leva mais de 10 segundos para uma entrada de 25. O algoritmo é muito ineficiente (assim como a linguagem), portanto, calculá-lo para 100 provavelmente levaria horas.
DJMcMayhem
1

Clojure, 70 bytes

Clojure não é realmente uma boa linguagem para o código de golfe. Ah bem.

Experimente em http://tryclj.com .

(last(nth(iterate(fn[[a b r]][b(+ a b)(* r(+ a b))])[0N 1 1])(dec n)))
user16973
fonte
1

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.

: f >r 1 1 r@ 0 DO 2dup + LOOP 2drop 1 r> 0 DO * LOOP ;

Experimente online

mbomb007
fonte
1

Swift, 68 bytes

func f(n:Int,_ a:Int=1,_ b:Int=1)->Int{return n<1 ?1:a*f(n-1,b,a+b)}
Alexander - Restabelecer Monica
fonte
1

JavaScript (ES6), 46 bytes

f=(n,a=1,b=1,c=i=1)=>n==i?c:f(n,b,a+b,c*b,++i)

Usa variáveis ​​de recursão e acumulador. Os erros de arredondamento começam em f(16).

cPu1
fonte