Desafio
Escreva uma função / programa que emita o n
'th elemento, ou o primeiro n
elemento, na conhecida sequência numérica:
1, 2, 4, 8, 16 ...
Ah, espere ... esqueci os primeiros números:
1, 1, 1, 1, 2, 4, 8, 16 ...
Heck, vou adicionar mais alguns para uma boa medida:
1, 1, 1, 1, 2, 4, 8, 16, 33, 69, 146, 312, 673, 1463, 3202, 7050, 15605, 34705 ...
Os números são números catalães generalizados dados pela fórmula (indexada a zero):
Onde
Este é o OEIS A004149 .
Você pode escolher se deseja que a sequência seja indexada em zero ou um. A sequência deve, é claro, ser a mesma, portanto, você deve reescrever a fórmula se a tiver um indexado.
a(n-1-k)
paraa(n-k)
, correto?Respostas:
Python , 51 bytes
Experimente online!
Simplifica um pouco a fórmula:
fonte
Perl 6 , 44 bytes
Experimente online!
Bloco de código anônimo que retorna uma sequência infinita e lenta de valores. Isso praticamente implementa a sequência como descrita, com o atalho que ele zip multiplica todos os elementos até agora após o segundo elemento, com o reverso da lista começando no quarto elemento e adicionando um extra
1
no final.Explicação:
fonte
05AB1E ,
141311 bytesExperimente online!
Gera o enésimo elemento, indexado em 0.
fonte
JavaScript (ES6), 42 bytes
Uma porta da solução do xnor .
Indexado a 0.
Experimente online!
JavaScript (ES6),
8375 bytesUma solução mais rápida, menos recursiva, mas significativamente mais longa.
Indexado a 0.
Experimente online!
fonte
Haskell,
494339 bytesExperimente online!
Para
n<3
osum
é 0, entãomax ... 1
aumenta para1
.Edit: -6 bytes graças a @Jo King.
fonte
Wolfram Language (Mathematica) , 36 bytes
Experimente online!
1 indexado.
A sequência 2-indexada é 4 bytes mais curto:
Sum[#0@i#0[#-i],{i,#-4}]/. 0->1&
. Experimente online!fonte
CatalanNumber
!05AB1E ,
1713 bytesNão menor que a resposta 05AB1E existente , mas eu queria experimentar a funcionalidade recursiva da nova versão 05AB1E como prática para mim.
Talvez pudesse ser jogado por alguns bytes.EDIT: E de fato pode, consulte a versão recursiva de @Grimy resposta 05AB1E 's abaixo, que é 13 bytes .£
è
£
Explicação:
Versão de 13 bytes do @Grimy (certifique-se de votar sua resposta se ainda não o fez!):
1λèλ1šÂ¨¨¨øPO
λλ1šÂ¨¨¨øPO
Explicação:
fonte
n=100
em 0,65 segundos , mas quando desativo o carregamento lento, o tempo limite é excedido após 60 segundos, mesmo paran=25
.Python 3 , 59 bytes
realmente ineficiente,
a(13)
não termina no TIO.Experimente online!
fonte
Geléia , 17 bytes
Experimente online!
fonte
Haskell , 76 bytes
Experimente online!
fonte
APL (Dyalog Extended) , 34 bytes SBCS
-2 graças a dzaima.
Prefixo anônimo lambda.
Experimente online!
fonte
Japt ,
191716 bytesGera o
n
termo th, indexado em 1.Tente
fonte
Haskell , 65 bytes
Experimente online!
Você pode usar
f
para obter um único elemento de uma sequência ou passar uma lista de valores parag
e obter todos os índices dessa lista.fonte
Quarto (gforth) ,
9981 bytesExperimente online!
A saída é o enésimo termo e a entrada é indexada 1
Editar: salvou 17 bytes mudando para a fórmula do xnor. Salvou outro byte usando 1 indexado por 1
Código Explicação
fonte
Carvão , 26 bytes
Experimente online! Link é a versão detalhada do código. Imprime o número n-ésimo indexado, embora calcule usando a indexação 1 internamente. Explicação:
Comece com
a[0] = a[1] = a[2] = a[3] = a[4] = 1
. Sim, isso é indexado em 1, mas com um valor extra de zero. Isso é código de golfe para você.Calcular
n
termos adicionais . Isso é um exagero, mas torna mais fácil encontrar o termo desejadon<5
.Para cada termo, calcule o próximo termo como a soma dos termos até agora multiplicados pelo reverso dos termos até o momento, excluindo três termos.
Este é um no-op usado para enganar o carvão vegetal na análise da forma de 2 argumentos
Slice
, caso contrário, eu teria que usar uma maneira menos eficiente de remover três termos.Saída do quarto último termo.
fonte
Pitão , 30 bytes
Experimente online!
<
@
fonte
Ruby ,
4241 bytesExperimente online!
1 indexado (para economizar 1 byte)
fonte
Oitava , 73 bytes
Experimente online!
-2 bytes graças a Stewie Griffin. Mais uma vez, a abordagem imperativa vence a abordagem recursiva funcional. Esse é mostrado abaixo.
Oitava , 75 bytes
Experimente online!
Captcha queria verificar se eu era humano ao postar isso. Para ser sincero, não tenho tanta certeza .
fonte
n<4
.Perl 5
-MList::Util=sum
, 61 bytesExperimente online!
fonte
C / C ++ ,
706967 bytes-1 bytes graças a Jonathan.
Experimente online!
fonte
a(n-1-k)
sera(n+~k)
?a(++k)*a(n-k)
É provável que @JonathanFrech funcione, e ele solta mais 2 bytes defor
. Mas sinto cheiro de comportamento indefinido.