Ce n'est pas très connu, mais ce que nous appelons la séquence de Fibonacci, AKA

1, 1, 2, 3, 5, 8, 13, 21, 34...

est en fait appelé la séquence de Duonacci . En effet, pour obtenir le nombre suivant, vous devez additionner les 2 chiffres précédents. Il y a aussi la séquence Tribonacci ,

1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201...

car le nombre suivant est la somme des 3 derniers chiffres. Et la séquence de Quadronacci

1, 1, 1, 1, 4, 7, 13, 25, 49, 94, 181, 349, 673...

Et la séquence favorite de tous, la séquence Pentanacci :

1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129...

Et la séquence d' Hexanacci , la séquence de Septanacci , la séquence d' Octonacci , etc. et ainsi de suite jusqu'à la séquence de N-Bonacci.

La séquence N-bonacci commencera toujours par N 1 sur une ligne.

Le défi

Vous devez écrire une fonction ou un programme qui prend deux nombres N et X et imprime les premiers nombres X N-Bonacci. N sera un nombre entier supérieur à 0, et vous pouvez sans risque supposer qu'aucun nombre N-Bonacci ne dépassera le type de nombre par défaut dans votre langue. La sortie peut être dans n'importe quel format lisible par l'homme, et vous pouvez prendre les entrées de toute manière raisonnable. (Arguments de ligne de commande, arguments de fonction, STDIN, etc.)

Comme d'habitude, il s'agit de Code-golf, donc les échappatoires standard s'appliquent et la réponse la plus courte en octets l'emporte!

Échantillon IO

#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

Boolfuck, 6 octets

,,[;+]

Vous pouvez supposer en toute sécurité qu'aucun nombre N-Bonacci ne dépassera le type de numéro par défaut dans votre langue.

Le type de numéro par défaut dans Boolfuck est un peu. En supposant que cela s’applique également aux nombres d’entrée N et X, et étant donné que N> 0, il n’ya que deux entrées possibles: 10 (qui n’émet rien) et 11 (qui émet 1).

,lit un bit dans l’emplacement mémoire actuel. N est ignoré, comme il doit l'être 1. Si X est égal à 0, le corps de la boucle (entouré de []) est ignoré. Si X est 1, il est émis puis basculé à 0 pour que la boucle ne se répète pas.

Python 2, 79 octets

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

Essayez-le en ligne

Pyth, 13

<Qu+Gs>QGEm1Q

Suite de tests

Prend l’entrée nouvelle ligne séparée, avec la npremière.

Explication:

<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

Haskell, 56 octets

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

Exemple d'utilisation: 3 # 8->[1,1,1,3,5,9,17,31] .

Comment ça fonctionne

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

Python 2, 55 octets

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

Suit une nfenêtre de longueur de la séquence dans la liste l, mise à jour en ajoutant la somme et en supprimant le premier élément. Imprime le premier élément à chaque itération pour les xitérations.

Une approche différente consistant à stocker tous les éléments et à résumer les derniers n valeurs a donné la même longueur (55).

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

Javascript ES6 / ES2015, 107 97 85 80 octets

Merci à @ user81655, @Neil et @ETHproductions pour économiser quelques octets

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

essayez-le en ligne

Cas de test:

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

ES6, 66 octets

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

Malheureusement map, vous ne pourrez pas accéder au tableau de résultats dans le rappel.

Gelée, 12 octets

ḣ³S;
b1Ç⁴¡Uḣ

Essayez-le en ligne!

Comment ça fonctionne

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.

C ++ 11, 360 octets

Salut j'aime juste cette question. Je sais que c ++ est un langage très difficile à gagner pour ce concours. Mais je vais jeter un centime de toute façon.

#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;}

Je laisserai ceci comme l'explication lisible du code ci-dessus.

#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;
}

Haskell , 47 octets

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

Essayez-le en ligne!

<$ aurait pu être introduit dans Prelude après la publication de ce défi.

Haskell , 53 octets

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

Essayez-le en ligne!

Définit la fonction binaire ?, utilisée comme 3?8 == [1,1,1,3,5,9,17,31].

La fonction auxiliaire %trouve récursivement le ie élément de la nséquence de -bonacci en faisant la somme des nvaleurs précédentes . Ensuite, la fonction ?tabule les premières xvaleurs de %.

APL, 21

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

C'est une fonction qui prend n comme argument de gauche et x comme argument de droite.

Explication:

{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/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

Cas de test:

      ↑⍕¨ {⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/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              

Python 3, 59

Économisé 20 octets grâce à FryAmTheEggman.

Pas une bonne solution, mais ça va marcher pour le moment.

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

Aussi, voici des cas de test:

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]

Java, 82 + 58 = 140 octets

Fonction pour trouver le ième n nombre -bonacci ( 82 octets ):

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;}

Fonction pour imprimer le premier numéro k n -bonacci ( 58 octets ):

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

Brain-Flak , 144 124 122 octets

-20 octets grâce à Nitroden

C’est ma première réponse à Brain-Flak, et je suis sûr qu’elle peut être améliorée. Toute aide est appréciée.

(([{}]<>)<{({}(()))}{}>)<>{({}[()]<<>({<({}<({}<>)<>>())>[()]}{})({}<><({({}<>)<>}<>)>)<>>)}{}<>{({}<{}>())}{}{({}<>)<>}<>

Essayez-le en ligne!

Paris / GP , 46 octets

La fonction génératrice de la séquence est:

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

Essayez-le en ligne!

Julia, 78 octets

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

C'est une fonction qui accepte deux entiers et retourne un tableau d'entiers. L’approche est simple: générez un tableau de longueurs n, puis agrandissez-le en ajoutant la somme des néléments précédents jusqu’à ce que le tableau ait une longueur 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

MATL , 22 26 octets

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

Ceci utilise la version actuelle (10.2.1) du langage / compilateur.

Essayez-le en ligne!

Quelques octets supplémentaires :-( dus à un bogue dans la Gfonction (coller l'entrée; corrigé pour la prochaine version)

Explication

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

Perl 6 , 38 octets

->\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
}

Usage:

# 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)

C, 132 octets

L'approche récursive est plus courte de quelques octets.

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));
}

Coque , 9 octets

↑§¡ȯΣ↑_B1

Essayez-le en ligne!

Commence à partir de la représentation Base 1de N (simplement une liste de N ) et ¡additionne de manière approximative ( Σ) les derniers ( ↑_) N éléments et ajoute le résultat à la liste. Enfin, prend ( ↑) les X premiers nombres de cette liste et les retourne.

Ruby , 41 octets

->a,b{r=[1]*a;b.times{z,*r=r<<r.sum;p z}}

Essayez-le en ligne!

R , 68 octets

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

Essayez-le en ligne!

K (ngn / k) , 26 à 24 octets

{(y-x){y,+/x#y}[-x]/x#1}

Essayez-le en ligne!

Perl 6, 52 ~ 72 47 ~ 67 octets

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

Requiert le module à MONKEY-SEE-NO-EVALcause de l'erreur suivante:

=== SORRY! === Erreur lors de la compilation -e
EVAL est une fonction très dangereuse !!! (utilisez MONKEY-SEE-NO-EVAL pour remplacer,
mais seulement si vous êtes TRES sûr que vos données ne contiennent aucune attaque par injection)
à -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)

PHP , 78 octets

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

Essayez-le en ligne!

-4 octets avec PHP> = 7.1 [,$n,$x]au lieu delist(,$n,$x)

Jq 1.5 , 67 octets

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

Suppose que les entrées fournies par N et X, par exemple

def N: 5;
def X: 11;

Étendu

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

Essayez-le en ligne!

J, 31 octets

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

Ungolfed:

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

explication

Des moments amusants avec le verbe puissant sous sa forme générale :

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

Ventilation en détail:

• ] {. ...Prenez <right arg>à droite les premiers éléments de tous ces trucs qui font le travail ...
• <left> ^: <right>applique le verbe à <left>plusieurs <right>reprises fois ... où <right>est spécifié par le milieu moyen dans (-@[] (1 #~ [), c'est-à ]-dire que l'argument de droite est passé à la fonction elle-même. Donc qu'est-ce<left> ? ...
• (] , [: +/ [ {. ])L'argument de gauche de cette phrase entière est d'abord transformé par le premier gérond, c'est-à-dire -@[. Cela signifie que l'argument de gauche de cette phrase est le négatif de l'argument de gauche de la fonction globale. Cela est nécessaire pour que la phrase [ {. ]prenne les derniers éléments de la liste de retour que nous construisons. Ceux-ci sont ensuite résumés:+/ . Et finalement ajouté à cette même liste de retour:] , .
• Alors, comment la liste de retour est-elle initialisée? C'est ce que le troisième gérond de pré-traitement accomplit: (1 #~ [)- Répétez 1 "partie gauche" plusieurs fois.

Essayez-le en ligne!

Mathematica, 59 octets

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

Vous voudrez probablement Clear@fentre les appels de fonction. Les arguments sont n,x, tout comme les cas de test.

Rangée , 36 octets

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

Essayez-le en ligne!

Explication

{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`

Japt , 18 octets

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

Essayez-le en ligne!

Explication:

         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