Contexte

Presque tout le monde connaît les chiffres de Fibonacci F(n) :

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

Celles-ci sont formées par la fonction de récursivité F(n) = F(n-1) + F(n-2)avec F(0)=0et F(1)=1. A000045

Une séquence étroitement liée est le nombre de Lucas L(m) :

2, 1, 3, 4, 7, 11, 18, 29 ...

Celles-ci sont formées par la fonction de récursivité L(m) = L(m-1) + L(m-2)avec L(0)=2et L(1)=1. A000032

Nous pouvons alterner entre les deux séquences basées sur des indices pairs / impairs, avec la construction
A(x) = F(x)si x mod 2 = 0et A(x) = L(x)sinon. Par exemple, A(4)est égal à F(4)depuis 4 mod 2 = 0. Nous appellerons cette séquence les numéros Lucas-Nacci , A(x):

0, 1, 1, 4, 3, 11, 8, 29, 21, 76 ...

Cela peut être formé par la fonction récursive A(x) = 3*A(x-2) - A(x-4)avec A(0)=0, A(1)=1, A(2)=1et A(3)=4. A005013

Défi

Étant donné l'entrée n, sortez la séquence de n+1nombres jusqu'à et y compris A(n)comme décrit ci-dessus. Le moins d'octets (ou équivalents d'octets, comme pour LabVIEW , tel que déterminé individuellement sur Meta) gagne.

Contribution

Un seul entier non négatif n.

Production

Une liste de nombres qui correspondent à la sous-séquence des nombres de Lucas-nacci de A(0)à A(n). La liste doit être en ordre séquentiel comme décrit ci-dessus.

Règles

• Les règles de code-golf standard et les restrictions contre les échappatoires s'appliquent.
• Les règles d'entrée / sortie standard s'appliquent.
• Le numéro d'entrée peut être dans n'importe quel format approprié: unaire ou décimal, lu depuis STDIN, fonction ou argument de ligne de commande, etc. - votre choix.
• La sortie peut être imprimée sur STDOUT ou renvoyée à la suite de l'appel de fonction. S'ils sont imprimés, des délimiteurs appropriés pour différencier les nombres doivent être inclus (séparés par des espaces, séparés par des virgules, etc.).
• De plus, si la sortie vers STDOUT, les espaces blancs environnants, les retours à la ligne de fin, etc. sont tous facultatifs.
• Si l'entrée est un entier non ou un entier négatif, le programme peut faire n'importe quoi ou rien, car le comportement n'est pas défini.

Exemples

Input -> Output
0 -> 0
5 -> 0, 1, 1, 4, 3, 11
18 -> 0, 1, 1, 4, 3, 11, 8, 29, 21, 76, 55, 199, 144, 521, 377, 1364, 987, 3571, 2584

Gelée, 12 octets

;2U+¥Ð¡-,1ZḢ

Essayez-le en ligne!

Contexte

Nous pouvons étendre F et L à -1 en définissant F (-1) = 1 et L (-1) = -1. Ceci est cohérent avec la fonction récursive.

Notre programme commence par

-1  1
 0  2

À chaque étape, pour former la paire suivante, nous inversons la dernière paire et l'ajoutons à l'avant-dernière paire. Par exemple:

[0, 2] U+¥ [-1, 1] -> [2, 0] + [-1, 1] -> [1, 1]

Si nous continuons ce processus pour quelques étapes supplémentaires, nous obtenons

-1  1
 0  2
 1  1
 1  3
 4  2
 3  7
11  5

La séquence Lucas-nacci est simplement la colonne de gauche.

Comment ça fonctionne

;2U+¥Ð¡-,1ZḢ  Niladic link. No implicit input.
              Since the link doesn't start with a nilad, the argument 0 is used.

;2            Concatenate the argument with 2, yielding [0, 2].
       -,1    Yield [-1, 1]. This is [L(-1), F(-1)].
    ¥         Create a dyadic chain of the two atoms to the left:
  U             Reverse the left argument.
   +            Add the reversed left argument and the right one, element-wise.
     С       For reasons‡, read a number n from STDIN.
              Repeatedly call the dyadic link U+¥, updating the right argument with
              the value of the left one, and the left one with the return value.
              Collect all intermediate results.
          Z   Zip the list of results, grouping the first and seconds coordinates.
           Ḣ  Head; select the list of first coordinates.

^‡ С jette un œil aux deux liens à gauche: 2et U+¥. Puisque le plus à gauche est un nilad, il ne peut pas être le corps de la boucle. Par conséquent, U+¥est utilisé comme corps et un nombre est lu à partir de l'entrée. Puisqu'il n'y a aucun argument de ligne de commande, ce nombre est lu à partir de STDIN.

CJam, 21 20 octets

Merci à Sp3000 pour avoir économisé 1 octet.

TXX4ri{1$3*4$-}*?;]p

Testez-le ici.

Explication

Utilise simplement la récurrence donnée dans la spécification de défi.

TXX4 e# Push 0 1 1 4 as base cases.
ri   e# Read input and convert to integer N.
{    e# Run this N times...
  1$ e#   Copy a(n-2).
  3* e#   Multiply by 3.
  4$ e#   Copy a(n-4).
  -  e#   Subtract.
}*
?;   e# Discard the last three values, using a ternary operation and popping the result.
]p   e# Wrap the rest in an array and pretty-print it.

Perl 6, 42 octets

{(0,1,1,4,{$^b;$^d;3*$^c-$^a}...*)[0..$_]}

usage

> my &f = {(0,1,1,4,{$^b;$^d;3*$^c-$^a}...*)[0..$_]}
-> ;; $_? is raw { #`(Block|184122176) ... }
> f(0)
(0)
> f(5)
(0 1 1 4 3 11)
> f(18)
(0 1 1 4 3 11 8 29 21 76 55 199 144 521 377 1364 987 3571 2584)

Haskell, 59 , 57 , 56 , 52 , 51 octets

l a=2*mod a 2:scanl(+)1(l a)
f n=[l i!!i|i<-[0..n]]

Définition de série adaptée de cette réponse .

Moins golfé:

fibLike start = start : scanl (+) 1 (fibLike start)
whichStart i = (2*mod i 2)
lucasNacci i = fibLike (whichStart i) !! i
firstN n = [ lucasNacci i | i <- [0..n]]

fibLike startdonne une liste infinie, définie: f(0)=start, f(1)=1, f(n)=f(n-1) + f(n-2). whichStart irenvoie 2 pour une entrée impaire (série Lucas) ou 0 pour une entrée paire (série Fibonacci). lucasNacci idonne le ième nombre de Lucas-nacci. firstN ncartes sur la liste.

Un octet enregistré par Boomerang.

ES6, 65 octets

n=>[...Array(n)].map(_=>a.shift(a.push(a[2]*3-a[0])),a=[0,1,1,4])

Utilise la relation de récurrence donnée dans la question.

Rétine , 70 62 59 octets

1
¶$`1
m`^(11)*1$
$&ff
m`$
 f
+`1(f*) (f*)
$2 $2$1
 f*

f
1

Essayez-le en ligne

• L'entrée est en base unaire, n 1s.
• 1? $`¶- Créez une ligne pour chaque nombre de 0 à n : , 1, 11, 111, 1111, ...
• m`^(11)*1$ $&ff- Ajouter ffaux lignes impaires. Cela amorcera la fonction avec L (0) = 2.
• m`$  f- Ajoutez  fà toutes les lignes (notez l'espace). Cela amène la fonction avec 0 et 1 pour les nombres de Fibonacci, et 2 et 1 pour les nombres de Lucas.
• +`1(f*) (f*) $2 $2$1 - Boucle: calculer F (n + 1) = F (n) + F (n-1) alors qu'il y a encore 1s.
•  f*   - Supprimer F (n + 1) à la fin de chaque ligne.
• Remplacez fs par 1s. Si cela n'est pas nécessaire et que nous pouvons rester avec fs, la longueur n'est que de 55 octets.

Oracle SQL 11.2, 218 216 201 octets

WITH v(a,b,c,d,i)AS(SELECT 0,1,1,4,3 FROM DUAL UNION ALL SELECT b,c,d,3*c-a,i+1 FROM v WHERE i<:1)SELECT SIGN(LEVEL-1) FROM DUAL WHERE LEVEL-1<=:1 CONNECT BY LEVEL<4UNION ALL SELECT d FROM v WHERE:1>2;

Non golfé

WITH v(a,b,c,d,i) AS 
(
  SELECT 0,1,1,4,3 FROM DUAL 
  UNION ALL 
  SELECT b,c,d,3*c-a,i+1 FROM v WHERE i<:1
)
SELECT SIGN(LEVEL-1) FROM DUAL WHERE LEVEL-1<=:1 CONNECT BY LEVEL<4
UNION ALL SELECT d FROM v WHERE:1>2;

J'ai réussi à gagner quelques octets en utilisant (abusant?) La fonction SIGN pour générer les 3 premiers éléments de la séquence.

Japt, 25 22 21 octets

Uò £MgXf2)+X%2*Mg°X)r

Testez-le en ligne!

Contexte

Il est quelque peu difficile de créer une séquence de Fibonacci dans Japt, mais nous avons une fonction intégrée Mgpour le faire pour nous. Cependant, cela ne nous donne que la séquence de Fibonacci, pas la séquence de Lucas. Nous pouvons accomplir la séquence Lucas assez facilement en utilisant cette astuce:

N    F(N-1)  F(N+1)  F(N-1)+F(N+1)
0    1       1       2
1    0       1       1
2    1       2       3
3    1       3       4
4    2       5       7
5    3       8       11
6    5       13      18
7    8       21      29

Comme vous pouvez le voir, F(N-1) + F(N+1)est égal à L(N)pour tous N. Cependant, comme nous n'avons besoin que de nombres de Lucas sur les indices impairs, nous pouvons combiner les deux formules en une seule:

N    N-N%2  N+N%2    F(N-N%2)  F(N+N%2)*(N%2)  F(N-N%2)+F(N+N%2)*(N%2)
0    0      0        0         0               0
1    0      2        0         1               1
2    2      2        1         0               1
3    2      4        1         3               4
4    4      4        3         0               3
5    4      6        3         8               11
6    6      6        8         0               8
7    6      8        8         21              29

Comment ça fonctionne

Uò £  MgX-1 +X%2*Mg° X)r
Uò mX{MgX-1 +X%2*Mg++X)r

             // Implicit: U = input integer
Uò mX{       // Create the inclusive range [0..U], and map each item X to:
MgXf2)+      //  Floor X to a multiple of 2, calculate this Fibonacci number, and add:
+X%2*Mg++X)  //  Calculate the (X+1)th Fibonacci number and multiply by X%2.
)r           //  Round the result. (The built-in Fibonacci function returns
             //  a decimal number on higher inputs.)

Mathematica, 52 51 octets

If[#>2,3#0[#-2]-#0[#-4],#-If[#>1,1,0]]&/@0~Range~#&

Idée très similaire à celle de Martin ci-dessus, j'ai passé un certain temps à essayer de trouver un moyen plus court de définir les «cas de base» pour la fonction. L'interpolation polynomiale a été un buste, alors j'ai opté pour cela, en utilisant l'extension en négatifs pour obtenir une définition assez courte.

Mathematica, 56 octets

f@0=0
f@1=f@2=1
f@3=4
f@n_:=3f[n-2]-f[n-4];
f/@0~Range~#&

Implémentation très simple. Définit une fonction d'assistance f, puis évalue une fonction sans nom qui s'applique fà une plage pour obtenir tous les résultats. Cela semble inutilement lourd.

Une seule fonction sans nom semble être un octet de plus cependant:

Switch[#,0,0,1,1,2,1,3,4,_,3#0[#-2]-#0[#-4]]&/@0~Range~#&

MATL , 17 18 octets

0ll4i:"y3*5$y-](x

Traduction presque directe de la réponse CJam de Martin .

Essayez-le en ligne!

0ll4       % push first four numbers: 0,1,1,4
i:         % input n and generate array [1,2,...,n]
"          % for loop. Repeat n times
  y        % copy second-top element from stack
  3*       % multiply by 3
  5$y      % copy fifth-top element from stack
  -        % subtract. This is the next number in the sequence
]          % end loop
(x         % indexing operation and delete. This gets rid of top three numbers

Brachylog , 51 octets

:0re{:4<:[0:1:1:4]rm!.|-4=:1&I,?-2=:1&*3-I=.}w,@Sw\

Cela prend un nombre en entrée et imprime dans STDOUT la liste, avec des espaces séparant chaque nombre.

Explication

§ Main predicate

:0re{...}               § Enumerate integers between 0 and the Input, pass the integer 
                        § as input to sub-predicate 1      
         w,@Sw          § Write sub-predicate 1's output, then write a space
              \         § Backtrack (i.e. take the next integer in the enumeration)


§ Sub-predicate 1

:4<                     § If the input is less than 4
   :[0:1:1:4]rm!.       § Then return the integer in the list [0,1,1,4] at index Input

|                       § Else

-4=:1&I,                § I = sub_predicate_1(Input - 4)
        ?-2=:1&*3-I=.   § Output = sub_predicate_1(Input - 2) * 3 - I

La coupure !dans la première règle du sous-prédicat 1 est nécessaire pour que lorsque nous revenons en arrière ( \), nous ne nous retrouvions pas dans une boucle infinie où l'interpréteur tentera la deuxième règle pour une entrée inférieure à 4.

Mathematica, 41 octets

LinearRecurrence[{0,3,0,-1},{0,1,1,4},#]&

Groovy, 50 octets

x={a,b=0,c=1,d=1,e=4->a<0?:[b,x(a-1,c,d,e,3*d-b)]}

Ceci définit la fonction x, qui prend n comme premier argument et a le cas de base des quatre premiers nombres de la séquence Fibocas comme arguments par défaut pour le reste de la fonction.

un ici est n. b, c, d et e sont les quatre éléments suivants de la séquence.

Il décrémente n et revient jusqu'à ce que n soit inférieur à zéro - lorsqu'il revient, il ajoute à la valeur de retour ultime le premier élément de sa séquence actuelle. Les nouvelles valeurs des quatre éléments suivants de la séquence sont données à l'appel récursif - les trois derniers éléments sont décalés pour être les trois premiers, et un nouveau quatrième élément est généré à partir de deux des éléments précédents à l'aide de 3 * db.

Il délimite de nouvelles valeurs avec des imbrications de liste, car groovy peut retourner plusieurs valeurs en les fourrant dans une liste - donc chaque appel renvoie le premier élément actuel et le résultat de la récursivité, qui sera sa propre liste.

R , 55 octets

A=c(0,1,1,4);for(x in 4:scan()+1)A[x]=3*A[x-2]-A[x-4];A

Essayez-le en ligne!

• -24 octets grâce à JayCe

Pylônes , 19

Il s'agit d'une traduction assez directe de l'approche de Martin.

0114{@-4@-33*-,i}=4

Comment ça fonctionne:

0114    # Push 0, 1, 1, 4 to the stack.
{       # Start a for loop.
 @-4    # Get the stack element at index -4
 @-3    # Get the stack element at index -3
 3      # Push 3 to the stack.
 *      # Multiply the top two elements of the stack.
 -      # Subtract the top two elements of the stack.
  ,     # Switch to loop iterations.
 i      # Get command line args.
}       # End for loop.
=4      # Discard the top 4 elements of the stack.

DUP , 32 octets

[a:0 1$4[a;1-$a:][1ø3*4ø-]#%%]

Try it here!

Un lambda anonyme qui laisse une séquence de nombres sur la pile. Usage:

8[a:0 1$4[a;1-$a:][1ø3*4ø-]#%%]!

Explication

[                              {start lambda}
 a:                            {save input number to a}
   0 1$4                       {base cases to get us started}
        [       ][       ]#    {while loop}
         a;1-$a:               {a--, check if a>0}
                  1ø3*4ø-      {3*stack[n-2]-stack[n-4]}

                           %%  {discard top 2 stack items}
                             ] {end lambda}

Python 2, 71 octets

def a(n,x=0,y=1,z=2,w=1,p=0):
 if~n:print[x,z][p];a(n-1,y,x+y,w,z+w,~p)

Cela semble définitivement trop long. Cependant, j'étais content d'avoir pu utiliser l' notopérateur au niveau du bit ... deux fois. Une fois comme une sorte de parité, retournez en arrière, et une fois pour terminer la récursion lorsquen atteinte -1.

La variable psera toujours soit 0ou -1, donc elle alternera entre les entrées 0ou -1de la liste. (Choisir l'entrée -1d'une liste Python signifie choisir le dernier élément.)

Méta-programmation de modèle C ++, 130 octets

template<int X>struct L{enum{v=3*L<X-2>::v-L<X-4>::v};};
#define D(X,A) template<>struct L<X>{enum{v=A};};
D(0,0)D(1,1)D(2,1)D(3,4)

Les définitions récursives pleurent en quelque sorte pour C ++ TMP, utilisation:

L<x>::v

d' xêtre le A(x)vous aimez.