tło

Większość osób zna się na liczby Fibonacciego F(n) :

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

Są one tworzone przez funkcję rekurencji za F(n) = F(n-1) + F(n-2)pomocą F(0)=0iF(1)=1 . A000045

Blisko spokrewniona sekwencja to liczby Lucasa L(m) :

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

Są one tworzone przez funkcję rekurencji za L(m) = L(m-1) + L(m-2)pomocą L(0)=2i L(1)=1.A000032

Możemy przełączać się między dwiema sekwencjami w oparciu o wskaźniki parzyste / nieparzyste, z budową,
A(x) = F(x)jeśli x mod 2 = 0i A(x) = L(x)inaczej. Na przykład A(4)jest równy F(4)od 4 mod 2 = 0. Zadzwonimy tej sekwencji Lucas-nacci Liczby , A(x):

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

Może być utworzone przez funkcję rekursji A(x) = 3*A(x-2) - A(x-4)z A(0)=0, A(1)=1, A(2)=1i A(3)=4. A005013

Wyzwanie

Biorąc pod uwagę dane wejściowe n, wypisz ciąg n+1liczb do włącznie, A(n)jak opisano powyżej. Najmniej bajtów (lub odpowiedników bajtów, takich jak dla LabVIEW , ustalanych indywidualnie w Meta).

Wejście

Pojedyncza nieujemna liczba całkowita n .

Wynik

Lista liczb odpowiadających podsekwencji liczb Lucas-nacci od A(0)doA(n) . Lista musi być w kolejności sekwencyjnej, jak opisano powyżej.

Zasady

• Obowiązują standardowe zasady gry w golfa i ograniczenia luk .
• Obowiązują standardowe zasady wejścia / wyjścia .
• Numer wejściowy może być w dowolnym odpowiednim formacie: jednostkowy lub dziesiętny, odczytany ze STDIN, argument funkcji lub wiersza poleceń itp. - twój wybór.
• Dane wyjściowe można wydrukować do STDOUT lub zwrócić w wyniku wywołania funkcji. Jeśli są drukowane, należy dołączyć odpowiednie separatory do rozróżnienia liczb (rozdzielone spacjami, oddzielone przecinkami itp.).
• Dodatkowo, jeśli dane wyjściowe do STDOUT, otaczające białe spacje, końcowe znaki nowej linii itp. Są opcjonalne.
• Jeśli wejście jest liczbą całkowitą lub liczbą całkowitą ujemną, program może zrobić cokolwiek lub nic, ponieważ zachowanie jest niezdefiniowane.

Przykłady

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

Galaretka, 12 bajtów

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

Wypróbuj online!

tło

Możemy rozszerzyć F i L do -1, definiując F (-1) = 1 i L (-1) = -1. Jest to zgodne z funkcją rekurencyjną.

Nasz program zaczyna się od

-1  1
 0  2

W każdym kroku, aby utworzyć następną parę, odwracamy ostatnią parę i dodajemy ją do przedostatniej pary. Na przykład:

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

Jeśli będziemy kontynuować ten proces przez kilka kolejnych kroków, otrzymamy

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

Sekwencja Lucas-nacci to po prostu lewa kolumna.

Jak to działa

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

^‡ С zagląda do dwóch linków po lewej stronie: 2i U+¥. Ponieważ skrajnie lewy jest niladem, nie może być ciałem pętli. Dlatego U+¥jest używany jako treść, a liczba jest odczytywana z danych wejściowych. Ponieważ nie ma argumentów wiersza polecenia, liczba ta jest odczytywana ze STDIN.

CJam, 21 20 bajtów

Dzięki Sp3000 za oszczędność 1 bajtu.

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

Sprawdź to tutaj.

Wyjaśnienie

Po prostu korzysta z powtarzalności podanej w specyfikacji wyzwania.

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 bajtów

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

stosowanie

> 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 bajtów

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

Definicja serii dostosowana z tej odpowiedzi .

Mniej golfa:

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 startDaje nieskończona lista, zdefiniowane: f(0)=start, f(1)=1, f(n)=f(n-1) + f(n-2). whichStart izwraca 2 dla nieparzystych danych wejściowych (seria Lucas) lub 0 dla parzystych (seria Fibonacciego). lucasNacci idaje i-ty numer Lucas-nacci. firstN nmapy nad listą.

Jeden bajt zapisany przez Boomerang.

ES6, 65 bajtów

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

Wykorzystuje relację powtarzalności podaną w pytaniu.

Siatkówka , 70 62 59 bajtów

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

f
1

Wypróbuj online

• Dane wejściowe są oparte na jednej jednostce, n 1s.
• 1? $`¶- Utwórz linię dla każdej liczby od 0 do n : , 1, 11, 111, 1111, ...
• m`^(11)*1$ $&ff- Dołącz ffdo linii nieparzystych. Spowoduje to zaszczepienie funkcji L (0) = 2.
• m`$  f- Dołącz  fdo wszystkich wierszy (zwróć uwagę na spację). Powoduje to zaszczepienie funkcji 0 i 1 dla liczb Fibonacciego oraz 2 i 1 dla liczb Lucasa.
• +`1(f*) (f*) $2 $2$1 - Pętla: oblicz F (n + 1) = F (n) + F (n-1), gdy są jeszcze 1.
•  f*   - Usuń F (n + 1) z końca każdej linii.
• Zamień fs z powrotem na 1s. Jeśli nie jest to potrzebne i możemy pozostać przy fs, długość wynosi zaledwie 55 bajtów.

Oracle SQL 11.2, 218 216 201 bajtów

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;

Nie grał w golfa

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;

Udało mi się zdobyć kilka bajtów, używając (nadużywasz?) Funkcji SIGN do wygenerowania pierwszych 3 elementów sekwencji.

Japt, 25 22 21 bajtów

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

Przetestuj online!

tło

Trochę trudno jest utworzyć sekwencję Fibonacciego w Japt, ale mamy wbudowaną funkcję, Mgktóra to zrobi za nas. Daje nam to jednak tylko sekwencję Fibonacciego, a nie sekwencję Lucasa. Możemy dość łatwo wykonać sekwencję Lucasa za pomocą tej sztuczki:

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

Jak widać, F(N-1) + F(N+1)jest równy L(N)dla wszystkich N. Ponieważ jednak potrzebujemy tylko liczb Lucasa na nieparzystych indeksach, możemy połączyć dwie formuły w jedną:

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

Jak to działa

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 bajtów

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

Bardzo podobny pomysł do powyższego Martina, spędziłem trochę czasu próbując znaleźć krótszy sposób zdefiniowania „przypadków bazowych” dla funkcji. Interpolacja wielomianowa była popiersiem, więc wybrałem to, używając rozszerzenia do negatywów, aby uzyskać dość krótką definicję.

Mathematica, 56 bajtów

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

Bardzo prosta implementacja. Definiuje funkcję pomocnika, fa następnie sprawdza, która funkcja ma zastosowanie bez nazwyf zakresu, aby uzyskać wszystkie wyniki. To niepotrzebnie kłopotliwe.

Pojedyncza nienazwana funkcja wydaje się jednak o jeden bajt dłuższa:

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

MATL , 17 18 bajtów

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

Prawie bezpośrednie tłumaczenie odpowiedzi Martina na CJam .

Wypróbuj 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

Brachylog , 51 bajtów

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

Pobiera to liczbę jako dane wejściowe i wypisuje na STDOUT listę ze spacjami oddzielającymi każdą liczbę.

Wyjaśnienie

§ 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

Wytarcie !pierwszej reguły pod predykatu 1 jest konieczne, abyśmy podczas backtrack ( \) nie znaleźli się w nieskończonej pętli, w której interpreter wypróbuje drugą regułę dla danych wejściowych mniejszych niż 4.

Mathematica, 41 bajtów

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

Groovy, 50 bajtów

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

Definiuje to funkcję x, która przyjmuje n jako pierwszy argument i ma podstawowy przypadek pierwszych czterech liczb w sekwencji Fibocas jako domyślny argument dla reszty funkcji.

tutaj jest n. b, c, d i e to kolejne cztery elementy w sekwencji.

Zmniejsza n i powtarza się, aż n jest mniejsze od zera - gdy się powtórzy, dodaje do ostatecznej wartości zwracanej pierwszy element w bieżącej sekwencji. Nowe wartości dla kolejnych czterech elementów w sekwencji są przekazywane do wywołania rekurencyjnego - ostatnie trzy elementy są przenoszone na pierwsze trzy, a nowy czwarty element jest generowany z dwóch poprzednich elementów przy użyciu 3 * db.

Ogranicza nowe wartości za pomocą zagnieżdżeń list, ponieważ groovy może zwrócić wiele wartości, upychając je do listy - więc każde wywołanie zwraca bieżący pierwszy element i wynik rekurencji, która będzie jego własną listą.

R , 55 bajtów

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

Wypróbuj online!

• -24 bajty dzięki JayCe

Słupy , 19

To dość bezpośrednie tłumaczenie podejścia Martina.

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

Jak to działa:

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 bajty

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

Try it here!

Anonimowa lambda, która pozostawia ciąg liczb na stosie. Stosowanie:

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

Wyjaśnienie

[                              {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 bajtów

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)

To zdecydowanie wydaje się zbyt długie. Byłem jednak zadowolony, że mogłem użyć notoperatora bitowego ... dwa razy. Raz jako rodzaj parzystości przewracaj w przód iw tył, a raz, aby zakończyć rekurencję, kiedyn osiągnie -1.

Zmienna pzawsze będzie albo, 0albo -1będzie na przemian wpisy 0lub -1lista. (Wybranie wpisu -1listy Python oznacza wybranie ostatniego elementu.)

Szablon C ++ Meta Programowanie, 130 bajtów

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)

Definicje rekurencyjne jakoś płaczą dla C ++ TMP, użycie:

L<x>::v

z xbyciem tym, A(x)kogo lubisz.