Isso não é muito conhecido, mas o que chamamos de sequência de Fibonacci, AKA
1, 1, 2, 3, 5, 8, 13, 21, 34...
é na verdade chamada de sequência de Duonacci . Isso ocorre porque, para obter o próximo número, você soma os 2 números anteriores. Há também a sequência de Tribonacci ,
1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201...
porque o próximo número é a soma dos 3 números anteriores. E a sequência de Quadronacci
1, 1, 1, 1, 4, 7, 13, 25, 49, 94, 181, 349, 673...
E a favorita de todos, a sequência de Pentanacci :
1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129...
E a sequência de Hexanacci , a sequência de Septanacci , a sequência de Octonacci e assim sucessivamente até a sequência N-Bonacci.
A sequência N-bonacci sempre começará com N 1s seguidos.
O desafio
Você deve escrever uma função ou programa que use dois números N e X e imprima os primeiros números X N-Bonacci. N será um número inteiro maior que 0 e você pode assumir com segurança que nenhum número de N-Bonacci excederá o tipo de número padrão no seu idioma. A saída pode estar em qualquer formato legível por humanos e você pode receber entradas de qualquer maneira razoável. (Argumentos de linha de comando, argumentos de função, STDIN etc.)
Como sempre, esse é o Code-golf, então as brechas padrão se aplicam e a resposta mais curta em bytes ganha!
IO de amostra
#n, x, output
3, 8 --> 1, 1, 1, 3, 5, 9, 17, 31
7, 13 --> 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
1, 20 --> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
30, 4 --> 1, 1, 1, 1 //Since the first 30 are all 1's
5, 11 --> 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129
1, 1, 2, 4, 7
como seria a terceira posição0 + 1 + 1
? ... e um com os outros?Respostas:
Boolfuck, 6 bytes
O tipo de número padrão no Boolfuck é um pouco. Supondo que isso também se estenda aos números de entrada N e X, e dado que N> 0, existem apenas duas entradas possíveis - 10 (que não produz nada) e 11 (que produz 1).
,
lê um pouco na localização atual da memória. N é ignorado como deve ser 1. Se X for 0, o corpo do loop (cercado por[]
) será ignorado. Se X é 1, é emitido e, em seguida, invertido para 0, para que o loop não se repita.fonte
Python 2, 79 bytes
Experimente online
fonte
exec"v=[sum(f[i-n:]),1][i<n];f+=[v];print v;i+=1;"*x
Pitão, 13
Suíte de teste
Separa a nova linha de entrada, com a
n
primeira.Explicação:
fonte
Haskell, 56 bytes
Exemplo de uso:
3 # 8
->[1,1,1,3,5,9,17,31]
.Como funciona
fonte
tail l
vez deinit l
?n
elementos na lista. Não há diferença entre remover da extremidade e adicionar à frente e vice-versa, ou seja, remover da frente e adicionar à extremidade, porque a lista inicial é composta apenas por1
s.++[]
por:
!Python 2, 55 bytes
Rastreia uma
n
janela de comprimento da sequência na listal
, atualizada adicionando a soma e removendo o primeiro elemento. Imprime o primeiro elemento a cada iteração parax
iterações.Uma abordagem diferente de armazenar todos os elementos e somar os últimos
n
valores deu o mesmo comprimento (55).fonte
Javascript ES6 / ES2015,
107978580 bytesObrigado a @ user81655, @Neil e @ETHproductions por salvar alguns bytes
experimente online
Casos de teste:
fonte
for
é sempre melhor quewhile
,x.split('')
->[...x]
,~~a
->+a
,n-=1
->n--
, se você incluir todo o corpo da função em umeval
arquivo que não precisa escreverreturn
. Além disso, é ainda mais curto do que[...'1'.repeat(i)]
éArray(i).fill(1)
e você pode remover o~~
dea
eb
. E você tem permissão para remover of=
.(i,n)=>eval("for(l=Array(i).fill(1);n-->i;)l.push(l.slice(-i).reduce((a,b)=>a+b));l")
. Mudei a ordem das instruções, combinei on--
inton-i
e o removil
dos argumentos para economizar alguns bytes extras.eval
poupança;(i,n)=>{for(l=Array(i).fill(1);n-->i;)l.push(l.slice(-i).reduce((a,b)=>a+b));return l}
ainda tem 85 bytes.l.slice(-i).reduce((a,b)=>a+b)
=>eval(l.slice(-i).join`+`)
ES6, 66 bytes
Infelizmente
map
, não permitirá que você acesse a matriz de resultados no retorno de chamada.fonte
Gelatina, 12 bytes
Experimente online!
Como funciona
fonte
C ++ 11, 360 bytes
Oi, eu apenas gosto desta pergunta. Eu sei que c ++ é uma linguagem muito difícil de vencer esta competição. Mas vou jogar um centavo de qualquer maneira.
Vou deixar isso como a explicação legível do código acima.
fonte
int
s, remova oint
. Se alguma função for chamadafoo
, chame-af
. Seja brutal; ignore o padrão e explore o compilador. É assim que você joga golfe.Haskell , 47 bytes
Experimente online!
<$
pode ter sido introduzido no Prelude depois que esse desafio foi lançado.Haskell , 53 bytes
Experimente online!
Define a função binária
?
, usada como3?8 == [1,1,1,3,5,9,17,31]
.A função auxiliar
%
encontra recursivamente oi
th-elemento dan
sequência -bonacci somando osn
valores anteriores . Em seguida, a função?
tabula os primeirosx
valores de%
.fonte
%
"?i<=n
emi>n
.APL, 21
Essa é uma função que recebe n como argumento esquerdo e x como argumento correto.
Explicação:
Casos de teste:
fonte
Python 3, 59
Economizou 20 bytes graças a FryAmTheEggman.
Não é uma ótima solução, mas funcionará por enquanto.
Além disso, aqui estão os casos de teste:
fonte
Java, 82 + 58 = 140 bytes
Função para encontrar o om n número -bonacci ( 82 bytes ):
Função para imprimir o primeiro número de k n- carbonacci ( 58 bytes ):
fonte
Flacidez Cerebral ,
144124122 bytes-20 bytes graças ao Nitroden
Esta é a minha primeira resposta do Brain-Flak e tenho certeza de que pode ser melhorada. Qualquer ajuda é apreciada.
Experimente online!
fonte
Pari / GP , 46 bytes
A função geradora da sequência é:
Experimente online!
fonte
Julia, 78 bytes
Esta é uma função que aceita dois números inteiros e retorna uma matriz inteira. A abordagem é simples: gere uma matriz de comprimento
n
e aumente a matriz adicionando a soma dosn
elementos anteriores até a matriz ter comprimentox
.Ungolfed:
fonte
MATL , 22
26bytesIsso usa a versão atual (10.2.1) do idioma / compilador.
Experimente online!
Alguns bytes extras :-( devido a um erro na
G
função (colar entrada; agora corrigido para a próxima versão)Explicação
fonte
Perl 6 , 38 bytes
Uso:
fonte
C, 132 bytes
A abordagem recursiva é mais curta em alguns bytes.
Ungolfed
fonte
Casca , 9 bytes
Experimente online!
Começa a partir do
B
ase-1
representação de N (simplesmente uma lista de N ones) e¡
teratively somas (Σ
) últimos (↑_
) N elementos e adiciona o resultado à lista. Finalmente, pega (↑
) os primeiros números X nesta lista e os retorna.fonte
Ruby , 41 bytes
Experimente online!
fonte
R , 68 bytes
Experimente online!
fonte
K (ngn / k) ,
2624 bytesExperimente online!
fonte
Perl 6,
52 ~ 7247 ~ 67 bytesRequer o módulo
MONKEY-SEE-NO-EVAL
, devido ao seguinte erro:fonte
PHP , 78 bytes
Experimente online!
-4 bytes usando PHP> = 7.1 em
[,$n,$x]
vez delist(,$n,$x)
fonte
Jq 1.5 , 67 bytes
Assume a entrada fornecida por N e X, por exemplo
Expandido
Experimente online!
fonte
J, 31 bytes
Ungolfed:
explicação
Tempos divertidos com o verbo power em sua forma gerúndio :
Repartição em detalhe:
] {. ...
Leve os primeiros<right arg>
elementos de todas essas coisas para a direita que faz o trabalho ...<left> ^: <right>
aplique o verbo<left>
repetidamente<right>
vezes ... onde<right>
é especificado pelo gerúndio do meio em(-@[
](1 #~ [)
, ou]
seja, o argumento certo passou para a própria função. Então o que é<left>
? ...(] , [: +/ [ {. ])
O argumento da esquerda para esta frase inteira é primeiro transformado pelo primeiro gerúndio, ou seja-@[
,. Isso significa que o argumento esquerdo para esta frase é o negativo do argumento esquerdo para a função geral. Isso é necessário para que a frase[ {. ]
pegue os últimos elementos da lista de retorno que estamos construindo. Aqueles são então somados:+/
. E finalmente anexado à mesma lista de retorno:] ,
.(1 #~ [)
- repita 1 "arg esquerdo" várias vezes.Experimente online!
fonte
Mathematica, 59 bytes
Você provavelmente desejará
Clear@f
entre chamadas de função. Os argumentos sãon,x
, assim como os casos de teste.fonte
Arrumado , 36 bytes
Experimente online!
Explicação
fonte
Japonês , 18 bytes
Experimente online!
Explicação:
fonte