Imprimir a sequência N-bonacci

54

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
DJMcMayhem
fonte
11
Cara, eu tive essa ideia há um tempo atrás e nunca cheguei a escrevê-la.
Morgan Thrapp
9
Meu botão de voto == seu avatar
ETHproductions
3-bonacci não seria 1, 1, 2, 4, 7como seria a terceira posição 0 + 1 + 1? ... e um com os outros?
Umbrella
11
@ guarda-chuva Não, o tribonacci começa com 3 1s. Veja minha edição para esclarecer este ponto.
DJMcMayhem

Respostas:

23

Boolfuck, 6 bytes

,,[;+]

Você pode assumir com segurança que nenhum número N-Bonacci excederá o tipo de número padrão no seu idioma.

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.

user253751
fonte
4
Não existe uma brecha padrão exatamente assim?
Stan Strum
11
@StanStrum Antes ou depois desta resposta?
user253751
2
Eu acredito que isso aconteceu antes, deixe-me ver ... Meta Link ; A primeira revisão foi em 31 de janeiro de 2016 às 13:44. Uau, deixa pra lá! Eu estava com dois dias de folga. Embora, para ser teimosa, a última edição para isso tenha sido 31 de janeiro de 2016 às 16:06. Soooooo sim, está tudo bem em meu livro
Stan Strum
9

Python 2, 79 bytes

n,x=input()
i,f=0,[]
while i<x:v=[sum(f[i-n:]),1][i<n];f.append(v);print v;i+=1

Experimente online

Lambda
fonte
Tente substituir a última linha porexec"v=[sum(f[i-n:]),1][i<n];f+=[v];print v;i+=1;"*x
Cyoce
8

Pitão, 13

<Qu+Gs>QGEm1Q

Suíte de teste

Separa a nova linha de entrada, com a nprimeira.

Explicação:

<Qu+Gs>QGEm1Q  ##  implicit: Q = eval(input)
  u      Em1Q  ##  read a line of input, and reduce that many times starting with
               ##  Q 1s in a list, with a lambda G,H
               ##  where G is the old value and H is the new one
   +G          ##  append to the old value
     s>QG      ##  the sum of the last Q values of the old value
<Q             ##  discard the last Q values of this list
FryAmTheEggman
fonte
11
Uau, isso foi rápido. Mal tive tempo de fechar meu navegador antes que você já tivesse postado isso!
DJMcMayhem
5

Haskell, 56 bytes

g l=sum l:g(sum l:init l)
n#x|i<-1<$[1..n]=take x$i++g i

Exemplo de uso: 3 # 8-> [1,1,1,3,5,9,17,31].

Como funciona

i<-1<$[1..n]           -- bind i to n copies of 1
take x                 -- take the first x elements of
       i++g i          -- the list starting with i followed by (g i), which is
sum l:                 -- the sum of it's argument followed by
      g(sum l:init l)  -- a recursive call to itself with the the first element
                       -- of the argument list replaced by the sum
nimi
fonte
Isso não deveria ser em tail lvez de init l?
haskeller orgulhoso
@proudhaskeller: isso não importa. mantemos os últimos nelementos 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 por 1s.
nimi 31/01
Oh, entendi. Essa é uma maneira bacana para substituir ++[]por :!
haskeller orgulhoso
@proudhaskeller: sim, exatamente!
nimi 31/01
5

Python 2, 55 bytes

def f(x,n):l=[1]*n;exec"print l[0];l=l[1:]+[sum(l)];"*x

Rastreia uma njanela de comprimento da sequência na lista l, atualizada adicionando a soma e removendo o primeiro elemento. Imprime o primeiro elemento a cada iteração para xiterações.

Uma abordagem diferente de armazenar todos os elementos e somar os últimos nvalores deu o mesmo comprimento (55).

def f(x,n):l=[1]*n;exec"l+=sum(l[-n:]),;"*x;print l[:x]
xnor
fonte
5

Javascript ES6 / ES2015, 107 97 85 80 bytes

Obrigado a @ user81655, @Neil e @ETHproductions por salvar alguns bytes


(i,n)=>eval("for(l=Array(i).fill(1);n-->i;)l.push(eval(l.slice(-i).join`+`));l")

experimente online


Casos de teste:

console.log(f(3,  8))// 1, 1, 1, 3, 5, 9, 17, 31
console.log(f(7,  13))// 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
console.log(f(5,  11))// 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129
gabrielperales
fonte
11
Agradável. Algumas dicas de golfe: foré sempre melhor que while, x.split('')-> [...x], ~~a-> +a, n-=1-> n--, se você incluir todo o corpo da função em um evalarquivo que não precisa escrever return. Além disso, é ainda mais curto do que [...'1'.repeat(i)]é Array(i).fill(1)e você pode remover o ~~de ae b. E você tem permissão para remover o f=.
user81655
2
Isto é o que ele se parece com as minhas dicas (85 bytes): (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 o n--into n-ie o removi ldos argumentos para economizar alguns bytes extras.
user81655
11
@ user81655 Não recebo a evalpoupanç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.
Neil
@Neil Looks como 86 bytes para mim ...
user81655
3
l.slice(-i).reduce((a,b)=>a+b)=>eval(l.slice(-i).join`+`)
ETHproductions
4

ES6, 66 bytes

(i,n)=>[...Array(n)].map((_,j,a)=>a[j]=j<i?1:j-i?s+=s-a[j+~i]:s=i)

Infelizmente map, não permitirá que você acesse a matriz de resultados no retorno de chamada.

Neil
fonte
11
Salve um byte currying os parâmetros.
Shaggy
4

Gelatina, 12 bytes

ḣ³S;
b1Ç⁴¡Uḣ

Experimente online!

Como funciona

b1Ç⁴¡Uḣ  Main link. Left input: n. Right input: x.

b1       Convert n to base 1.
    ¡    Call...
  Ç        the helper link...
   ⁴       x times.
     U   Reverse the resulting array.
      ḣ  Take its first x elements.


ḣ³S;     Helper link. Argument: A (list)

ḣ³       Take the first n elements of A.
  S      Compute their sum.
   ;     Prepend the sum to A.
Dennis
fonte
3

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.

#include<vector>
#include<numeric>
#include<iostream>
using namespace std;typedef vector<int>v;void p(v& i) {for(auto&v:i)cout<<v<<" ";cout<<endl;}v b(int s,int n){v r(n<s?n:s,1);r.reserve(n);for(auto i=r.begin();r.size()<n;i++){r.push_back(accumulate(i,i+s,0));}return r;}int main(int c, char** a){if(c<3)return 1;v s=b(atoi(a[1]),atoi(a[2]));p(s);return 0;}

Vou deixar isso como a explicação legível do código acima.

#include <vector>
#include <numeric>
#include <iostream>

using namespace std;
typedef vector<int> vi;

void p(const vi& in) {
    for (auto& v : in )
        cout << v << " ";
    cout << endl;
}

vi bonacci(int se, int n) {
    vi s(n < se? n : se, 1);
    s.reserve(n);
    for (auto it = s.begin(); s.size() < n; it++){
        s.push_back(accumulate(it, it + se, 0));
    }
    return s;
}

int main (int c, char** v) {
    if (c < 3) return 1;
    vi s = bonacci(atoi(v[1]), atoi(v[2]));
    p(s);
    return 0;
}
hetepeperfan
fonte
Bem-vindo à Programação de Puzzles e Code Golf. Essa é uma boa resposta, no entanto, notei que você tem muito espaço em branco e nomes de variáveis ​​e funções com mais de 1 caractere. Tal como está, esta é uma boa versão legível do seu código, mas você deve adicionar uma versão com golf. Quando você fizer, eu lhe darei um voto positivo, mas até que seja jogado no golfe, eu não vou.
precisa saber é o seguinte
@ wizzwizz4 Olá, adicionou uma versão em golf do código acima. Deixei o código não destruído para permitir que as pessoas vissem como eu o fiz. Além disso, eu gosto de ler uma função bonacci que retorna vi que ainda soa como vibonacci. Eu sinto que não devo reduzir a função principal porque a norma exige o uso de int main (int, char **) como ponto de entrada do programa. Além disso, acredito que todas as variáveis ​​têm no máximo 1 caractere e todos os espaços em branco não significativos são removidos.
precisa saber é o seguinte
3
Isso não é código - "cumpra os padrões". Isso é código-golfe . Manipulamos e tiramos proveito de nossos idiomas. Se alguma variável for ints, remova o int. Se alguma função for chamada foo, chame-a f. Seja brutal; ignore o padrão e explore o compilador. É assim que você joga golfe.
Wizzwizz4
Trocadilhos e bom código pertencem apenas ao código não-protegido . Mas fique à vontade para mantê-los lá; na verdade, é recomendável. Mas seja muito, muito mesquinho com o compilador ao jogar seu código. Faça o menor possível, não importa o quê . (Oh, e aqui está a um prometi!)
wizzwizz4
@ wizzwizz4 A remoção de "int" é válida? Eu pensei que o int implícito não funcionaria.
DJMcMayhem
3

Haskell , 47 bytes

q(h:t)=h:q(t++[h+sum t])
n?x=take x$q$1<$[1..n]

Experimente online!

<$ pode ter sido introduzido no Prelude depois que esse desafio foi lançado.


Haskell , 53 bytes

n%i|i>n=sum$map(n%)[i-n..i-1]|0<1=1
n?x=map(n%)[1..x]

Experimente online!

Define a função binária ?, usada como 3?8 == [1,1,1,3,5,9,17,31].

A função auxiliar %encontra recursivamente o ith-elemento da nsequência -bonacci somando os nvalores anteriores . Em seguida, a função ?tabula os primeiros xvalores de %.

xnor
fonte
Resposta antiga, mas você quer dizer "A função auxiliar %"?
Conor O'Brien
Trocar os guardas se transformará i<=nem i>n.
Ørjan Johansen
@ ØrjanJohansen Notei isso também ao editar, embora olhar para trás todo o método pareça ruim, então eu poderia refazer o golfe inteiro.
Xnor
2

APL, 21

{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}

Essa é uma função que recebe n como argumento esquerdo e x como argumento correto.

Explicação:

{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}
                   ⍺/1  ⍝ begin state: X ones    
                  +     ⍝ identity function (to separate it from the ⍵)
    ⍺{         }⍣⍵     ⍝ apply this function N times to it with X as left argument
      ⍵,               ⍝ result of the previous iteration, followed by...
        +/              ⍝ the sum of
          ⍺↑            ⍝ the first X of
            ⌽          ⍝ the reverse of
             ⍵         ⍝ the previous iteration
 ⍵↑                    ⍝ take the first X numbers of the result

Casos de teste:

      ↑⍕¨ {⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1} /¨ (3 8)(7 13)(1 20)(30 4)(5 11)
 1 1 1 3 5 9 17 31                       
 1 1 1 1 1 1 1 7 13 25 49 97 193         
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
 1 1 1 1                                 
 1 1 1 1 1 5 9 17 33 65 129              
marinus
fonte
2

Python 3, 59

Economizou 20 bytes graças a FryAmTheEggman.

Não é uma ótima solução, mas funcionará por enquanto.

def r(n,x):f=[1]*n;exec('f+=[sum(f[-n:])];'*x);return f[:x]

Além disso, aqui estão os casos de teste:

assert r(3, 8) == [1, 1, 1, 3, 5, 9, 17, 31]
assert r(7, 13) == [1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193]
assert r(30, 4) == [1, 1, 1, 1]
Morgan Thrapp
fonte
2

Java, 82 + 58 = 140 bytes

Função para encontrar o om n número -bonacci ( 82 bytes ):

int f(int i,int n){if(i<=n)return 1;int s=0,q=0;while(q++<n)s+=f(i-q,n);return s;}

Função para imprimir o primeiro número de k n- carbonacci ( 58 bytes ):

(k,n)->{for(int i=0;i<k;i++){System.out.println(f(i,n));}}
HyperNeutrino
fonte
2

Flacidez Cerebral , 144 124 122 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!

H.PWiz
fonte
2

Pari / GP , 46 bytes

A função geradora da sequência é:

(n-1 1)xnxn+1 1-2x+1 1-1 1x-1 1

(n,m)->Vec(n--/(x-(2-1/x)/x^n)-1/(x-1)+O(x^m))

Experimente online!

alefalpha
fonte
1

Julia, 78 bytes

f(n,x)=(z=ones(Int,n);while endof(z)<x push!(z,sum(z[end-n+1:end]))end;z[1:x])

Esta é uma função que aceita dois números inteiros e retorna uma matriz inteira. A abordagem é simples: gere uma matriz de comprimento ne aumente a matriz adicionando a soma dos nelementos anteriores até a matriz ter comprimento x.

Ungolfed:

function f(n, x)
    z = ones(Int, n)
    while endof(z) < x
        push!(z, sum(z[end-n+1:end]))
    end
    return z[1:x]
end
Alex A.
fonte
1

MATL , 22 26 bytes

1tiXIX"i:XK"tPI:)sh]K)

Isso usa a versão atual (10.2.1) do idioma / compilador.

Experimente online!

Alguns bytes extras :-( devido a um erro na Gfunção (colar entrada; agora corrigido para a próxima versão)

Explicação

1tiXIX"      % input N. Copy to clipboard I. Build row array of N ones
i:XK         % input X. Build row array [1,2,...X]. Copy to clipboard I
"            % for loop: repeat X times. Consumes array [1,2,...X]
  t          % duplicate (initially array of N ones)
  PI:)       % flip array and take first N elements
  sh         % compute sum and append to array
]            % end
K)           % take the first X elements of array. Implicitly display
Luis Mendo
fonte
1

Perl 6 , 38 bytes

->\N,\X{({@_[*-N..*].sum||1}...*)[^X]} # 38 bytes
-> \N, \X {
  (

    {

      @_[
        *-N .. * # previous N values
      ].sum      # added together

      ||     # if that produces 0 or an error
      1      # return 1

    } ... *  # produce an infinite list of such values

  )[^X]      # return the first X values produced
}

Uso:

# give it a lexical name
my &n-bonacci = >\N,\X{…}

for ( (3,8), (7,13), (1,20), (30,4), (5,11), ) {
  say n-bonacci |@_
}
(1 1 1 3 5 9 17 31)
(1 1 1 1 1 1 1 7 13 25 49 97 193)
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 1 1 1)
(1 1 1 1 1 5 9 17 33 65 129)
Brad Gilbert b2gills
fonte
1

C, 132 bytes

A abordagem recursiva é mais curta em alguns bytes.

k,n;f(i,s,j){for(j=s=0;j<i&j++<n;)s+=f(i-j);return i<n?1:s;}main(_,v)int**v;{for(n=atoi(v[1]);k++<atoi(v[2]);)printf("%d ",f(k-1));}

Ungolfed

k,n; /* loop index, n */

f(i,s,j) /* recursive function */
{
    for(j=s=0;j<i && j++<n;) /* sum previous n n-bonacci values */
        s+=f(i-j);
    return i<n?1:s; /* return either sum or n, depending on what index we're at */
}

main(_,v) int **v;
{
    for(n=atoi(v[1]);k++<atoi(v[2]);) /* print out n-bonacci numbers */
        printf("%d ", f(k-1));
}
Cole Cameron
fonte
1

Casca , 9 bytes

↑§¡ȯΣ↑_B1

Experimente online!

Começa a partir do Base- 1representaçã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.

Leo
fonte
1

R , 68 bytes

function(n,x){a=1+!1:n;for(i in n+1:x){a[i]=sum(a[(i-n:1)])};a[1:x]}

Experimente online!

Robert S.
fonte
0

Perl 6, 52 ~ 72 47 ~ 67 bytes

sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^$x]}

Requer o módulo MONKEY-SEE-NO-EVAL, devido ao seguinte erro:

=== DESCULPE! === Erro ao compilar -e
EVAL é uma função muito perigosa !!! (use MONKEY-SEE-NO-EVAL para substituir,
mas somente se tiver MUITO certeza de que seus dados não contêm ataques de injeção)
em -e: 1

$ perl6 -MMONKEY-SEE-NO-EVAL -e'a(3,8).say;sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^$x]}'
(1 1 1 3 5 9 17 31)
andlrc
fonte
Alguém sabe uma maneira de desativar o modo estrito, etc?
precisa saber é
Eu acho que se você usar uma versão Perl 6 anterior ao Natal de 2015, ela não aplicará monkey-see-no-eval.
Batman
0

PHP , 78 bytes

for(list(,$n,$x)=$argv;$i<$x;print${$i++}." ")$s+=$$i=$i<$n?1:$$d+$s-=${$d++};

Experimente online!

-4 bytes usando PHP> = 7.1 em [,$n,$x]vez delist(,$n,$x)

Jörg Hülsermann
fonte
0

Jq 1.5 , 67 bytes

def C:if length>X then.[:X]else.+=[.[-N:]|add]|C end;[range(N)|1]|C

Assume a entrada fornecida por N e X, por exemplo

def N: 5;
def X: 11;

Expandido

def C:                        # . is current array
    if length>X               # stop when array is as long as X
    then .[:X]                # return first X elements
    else .+=[.[-N:]|add] | C  # recursively add sum of last N elements to array
    end
;
  [range(N)|1]                # initial state
| C

Experimente online!

jq170727
fonte
0

J, 31 bytes

]{.(],[:+/[{.])^:(-@[`]`(1#~[))

Ungolfed:

] {. (] , [: +/ [ {. ])^:(-@[`]`(1 #~ [))

explicação

Tempos divertidos com o verbo power em sua forma gerúndio :

(-@[`]`(1 #~ [)) NB. gerund pre-processing

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:] , .
  • Então, como a lista de retorno é inicializada? É isso que o terceiro gerúndio de pré-processamento realiza: (1 #~ [)- repita 1 "arg esquerdo" várias vezes.

Experimente online!

Jonah
fonte
0

Mathematica, 59 bytes

((f@#=1)&/@Range@#;f@n_:=Tr[f[n-#]&/@Range@#];f/@Range@#2)&

Você provavelmente desejará Clear@fentre chamadas de função. Os argumentos são n,x, assim como os casos de teste.

numbermaniac
fonte
0

Arrumado , 36 bytes

{x,n:n^recur(*tile(x,c(1)),sum@c,x)}

Experimente online!

Explicação

{x,n:n^recur(*tile(x,c(1)),sum@c,x)}
{x,n:                              }   lambda taking parameters `x` and `n`
     n^                                take the first `n` terms of...
       recur(                     )        a recursive function
             *tile(x,c(1)),                whose seed is `x` `1`s
                           sum@c,          taking the sum of each window
                                 x         with a window size of `x`
Conor O'Brien
fonte
0

Japonês , 18 bytes

@ZsVn)x}gK=Vì1;K¯U

Experimente online!

Explicação:

         K=Vì1        :Start with n 1s in an array K
@      }gK            :Extend K to at least x elements by setting each new element to:
      x               : The sum of
 ZsVn                 : The previous n elements
              ;       :Then
               K¯U    :Return the first n elements of K
Kamil Drakari
fonte