fundo

Quase todo mundo está familiarizado com os números de Fibonacci F(n) :

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

Estes são formados pela função de recursão F(n) = F(n-1) + F(n-2)com F(0)=0e F(1)=1. A000045

Uma sequência intimamente relacionada são os números de Lucas L(m) :

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

Estes são formados pela função de recursão L(m) = L(m-1) + L(m-2)com L(0)=2e L(1)=1. A000032

Podemos alternar entre as duas seqüências com base em índices pares / ímpares, com a construção
A(x) = F(x)se x mod 2 = 0e de A(x) = L(x)outra forma. Por exemplo, A(4)é igual a F(4)since 4 mod 2 = 0. Vamos chamar essa seqüência os números Lucas-Nacci , A(x):

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

Este pode ser formado pela função recursão A(x) = 3*A(x-2) - A(x-4)com A(0)=0, A(1)=1, A(2)=1, e A(3)=4. A005013

Desafio

Com base na entrada n, imprima a sequência de n+1números até e incluindo, A(n)conforme descrito acima. Menos bytes (ou equivalentes de bytes, como no LabVIEW , conforme determinado individualmente no Meta) ganham.

Entrada

Um único inteiro não negativo n.

Resultado

Uma lista de números que correspondem à subsequência dos números de Lucas-nacci de A(0)até A(n). A lista deve estar em ordem seqüencial, conforme descrito acima.

Regras

• Aplicam-se regras padrão de código de golfe e restrições de brechas .
• Aplicam- se regras de entrada / saída padrão .
• O número da entrada pode estar em qualquer formato adequado: unário ou decimal, lido em STDIN, função ou argumento de linha de comando, etc. - sua escolha.
• A saída pode ser impressa em STDOUT ou retornada como resultado da chamada de função. Se impressos, delimitadores adequados para diferenciar os números devem ser incluídos (separados por espaço, separados por vírgula, etc.).
• Além disso, se a saída para STDOUT, o espaço em branco circundante, a nova linha à direita, etc. forem opcionais.
• Se a entrada for um não inteiro ou um número inteiro negativo, o programa poderá fazer qualquer coisa ou nada, pois o comportamento é indefinido.

Exemplos

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

Gelatina, 12 bytes

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

Experimente online!

fundo

Podemos estender F e L para -1 definindo F (-1) = 1 e L (-1) = -1. Isso é consistente com a função recursiva.

Nosso programa começa com

-1  1
 0  2

Em cada etapa, para formar o próximo par, invertemos o último par e o adicionamos ao penúltimo par. Por exemplo:

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

Se continuarmos esse processo por mais algumas etapas, obteremos

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

A sequência Lucas-nacci é simplesmente a coluna da esquerda.

Como funciona

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

^‡ С espreita os dois links à esquerda: 2e U+¥. Como o mais à esquerda é um nilad, ele não pode ser o corpo do loop. Portanto, U+¥é usado como corpo e um número é lido da entrada. Como não há argumentos de linha de comando, esse número é lido a partir de STDIN.

CJam, 21 20 bytes

Agradecimentos ao Sp3000 por economizar 1 byte.

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

Teste aqui.

Explicação

Simplesmente usa a recorrência dada na especificação do desafio.

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 bytes

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

uso

> 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 bytes

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

Definição de série adaptada a partir desta resposta .

Menos golfe:

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 startdá uma lista infinita, definido: f(0)=start, f(1)=1, f(n)=f(n-1) + f(n-2). whichStart iretorna 2 para entrada ímpar (série Lucas) ou 0 para par (série Fibonacci). lucasNacci idá o i-ésimo número de Lucas-nacci. firstN nmapas sobre a lista.

Um byte salvo pelo Boomerang.

ES6, 65 bytes

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

Usa a relação de recorrência fornecida na pergunta.

Retina , 70 62 59 bytes

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

f
1

Experimente online

• A entrada está em uma base unária, n 1s.
• 1? $`¶- Crie uma linha para cada número de 0 a n : , 1, 11, 111, 1111, ...
• m`^(11)*1$ $&ff- Acrescente ffa linhas ímpares. Isso irá propagar a função com L (0) = 2.
• m`$  f- Anexar  fa todas as linhas (observe o espaço). Isso semeia a função com 0 e 1 para números de Fibonacci e 2 e 1 para números de Lucas.
• +`1(f*) (f*) $2 $2$1 - Loop: calcula F (n + 1) = F (n) + F (n-1) enquanto ainda existem 1s.
•  f*   - Remova F (n + 1) do final de cada linha.
• Substitua fs de volta para 1s. Se isso não for necessário e pudermos ficar com fs, o comprimento será de apenas 55 bytes.

Oracle SQL 11.2, 218 216 201 bytes

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;

Sem golfe

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;

Consegui ganhar alguns bytes usando (abusando?) Da função SIGN para gerar os 3 primeiros elementos da sequência.

Japonês, 25 22 21 bytes

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

Teste online!

fundo

É um pouco difícil criar uma sequência de Fibonacci em Japt, mas temos um recurso interno Mgpara fazer isso por nós. No entanto, isso nos dá apenas a sequência de Fibonacci, não a sequência de Lucas. Podemos realizar a sequência de Lucas com bastante facilidade usando este truque:

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

Como você pode ver, F(N-1) + F(N+1)é igual L(N)para todos N. No entanto, como precisamos apenas dos números de Lucas nos índices ímpares, podemos combinar as duas fórmulas em uma:

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

Como funciona

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 bytes

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

Idéia muito semelhante à de Martin, passei algum tempo tentando encontrar uma maneira mais curta de definir os "casos básicos" para a função. A interpolação polinomial foi um fracasso, então eu fui para isso, usando a extensão em negativos para produzir uma definição bastante curta.

Mathematica, 56 bytes

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

Implementação muito direta. Define uma função auxiliar fe avalia como uma função sem nome que se aplica fa um intervalo para obter todos os resultados. Isso parece desnecessariamente pesado.

Uma única função sem nome parece ter um byte a mais:

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

MATL , 17 18 bytes

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

Tradução quase direta da resposta CJam de Martin .

Experimente online!

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

Braquilog , 51 bytes

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

Isso recebe um número como entrada e é impresso em STDOUT na lista, com espaços separando cada número.

Explicação

§ 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

O corte !na primeira regra do sub-predicado 1 é necessário para que, quando retrocedamos ( \), não terminemos em um loop infinito, em que o intérprete tente a segunda regra para uma entrada menor que 4.

Mathematica, 41 bytes

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

Groovy, 50 bytes

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

Isso define a função x, que recebe n como seu primeiro argumento e tem o caso base dos quatro primeiros números na sequência Fibocas como argumentos padrão para o restante da função.

a aqui é n. b, c, d e e são os próximos quatro elementos na sequência.

Ele decrementa n e se repete até que n seja menor que zero - quando se repete, adiciona ao valor de retorno final o primeiro elemento em sua sequência atual. Os novos valores para os próximos quatro elementos na sequência são dados à chamada recursiva - os últimos três elementos passam a ser os três primeiros e um novo quarto elemento é gerado a partir de dois dos elementos anteriores usando 3 * db.

Ele delimita novos valores com aninhamentos de lista, pois o groovy pode retornar vários valores colocando-os em uma lista - portanto, cada chamada retorna o primeiro elemento atual e o resultado da recursão, que será sua própria lista.

R , 55 bytes

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

Experimente online!

• -24 bytes graças a JayCe

Postes , 19

Esta é uma tradução bastante direta da abordagem de Martin.

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

Como funciona:

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 bytes

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

Try it here!

Uma lambda anônima que deixa uma sequência de números na pilha. Uso:

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

Explicação

[                              {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 bytes

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)

Isso definitivamente parece muito longo. No entanto, fiquei satisfeito por poder usar o notoperador bit a bit ... duas vezes. Uma vez como uma espécie de paridade, vire para frente e para trás e uma vez para encerrar a recursão quando natingir-1 .

A variável psempre será um 0ou -1, portanto, alternará entre as entradas 0ou -1a lista. (Escolher a entrada -1de uma lista Python significa escolher o último elemento.)

Meta Programação em C ++, 130 bytes

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)

Definições recursivas de alguma forma pedem C ++ TMP, uso:

L<x>::v

com xser o A(x)que quiser.