Każdy zna sekwencję Fibonacciego:
bierzesz kwadrat, dołączasz do niego równy kwadrat, a następnie wielokrotnie dołączasz kwadrat, którego długość boku jest równa największej długości boku wynikowego prostokąta.
Rezultatem jest piękna spirala kwadratów, których ciąg liczb jest ciągiem Fibonacciego :

Ale co, jeśli nie chcielibyśmy używać kwadratów?

Jeśli użyjemy równobocznych trójkątów - zamiast kwadratów - w podobny sposób, otrzymamy równie piękną spiralę trójkątów i nową sekwencję: sekwencję Padovana , aka A000931 :

Zadanie:

Biorąc pod uwagę dodatnią liczbę całkowitą, , wyjście , ty termin w sekwencji Padovana LUB pierwsze warunki.$N$$a_N$$N$$N$

Załóżmy, że wszystkie trzy pierwsze sekwencje to . Zatem sekwencja rozpocznie się w następujący sposób: $1$

Wejście:

• Każda dodatnia liczba całkowita$N\ge0$

• Niepoprawne dane wejściowe nie muszą być brane pod uwagę

Wynik:

• p określenie w PADOVAN sekwencji OR pierwszych względem PADOVAN sekwencji.$N$N$N$

• Jeśli wydrukowanych zostanie pierwszych wyrażeń, wynik może być dowolny (lista / tablica, ciąg wielu wierszy itp.)$N$

• Może być indeksowany lub indeksowany$0$$1$

Przypadki testowe:
(indeksowane 0, ty termin)$N$

Input | Output
--------------
0     | 1
1     | 1
2     | 1
4     | 2
6     | 4
14    | 37
20    | 200
33    | 7739

(1 indeksowane, pierwsze warunków)$N$

Input | Output
--------------
1     | 1
3     | 1,1,1
4     | 1,1,1,2
7     | 1,1,1,2,2,3,4
10    | 1,1,1,2,2,3,4,5,7,9
12    | 1,1,1,2,2,3,4,5,7,9,12,16

Zasady:

• To jest golf golfowy : im mniej bajtów, tym lepiej!

• Standardowe luki są zabronione.

Galaretka , 10 bajtów

9s3’Ẓæ*³FṀ

Wypróbuj online!

1-indeksowany. Oblicza największy element: gdzie macierz binarna jest wygodnie obliczana jako:

(jest to całkowity zbieg okoliczności).

9s3         [[1,2,3],[4,5,6],[7,8,9]]    9 split 3
   ’        [[0,1,2],[3,4,5],[6,7,8]]    decrease
    Ẓ       [[0,0,1],[1,0,1],[0,1,0]]    isprime
     æ*³    [[0,0,1],[1,0,1],[0,1,0]]^n  matrix power by input
        FṀ                               flatten, maximum

Oaza , 5 bajtów

n -ty indeks 0-indeksowany

cd+1V

Wypróbuj online!

Wyjaśnienie

   1V   # a(0) = 1
        # a(1) = 1
        # a(2) = 1
        # a(n) =
c       #        a(n-2)
  +     #              +
 d      #               a(n-3)

Galaretka ,  10 9  8 bajtów

ŻṚm2Jc$S

Monadyczny link akceptujący n(indeksowany 0), który daje P(n).

Wypróbuj online!

W jaki sposób?

Implementuje$P(n) = \sum_{i=0}^{\lfloor\frac{n}2\rfloor}\binom{i+1}{n-2i}$

ŻṚm2Jc$S - Link: integer, n       e.g. 20
Ż        - zero range                  [0, 1, 2, 3, 4, ..., 19, 20]
 Ṛ       - reverse                     [20, 19, ..., 4, 3, 2, 1, 0]
  m2     - modulo-slice with 2         [20, 18, 16, 14, 12, 10,  8,  6,  4,  2,  0]  <- n-2i
      $  - last two links as a monad:
    J    -   range of length           [ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11]  <- i+1
     c   -   left-choose-right         [ 0,  0,  0,  0,  0,  0,  0, 28,126, 45,  1]
       S - sum                         200

A oto „twofer”
… zupełnie inna metoda także dla 8 bajtów (ta jest indeksowana 1, ale znacznie wolniej):

3ḊṗRẎ§ċ‘ - Link: n
3Ḋ       - 3 dequeued = [2,3]
   R     - range = [1,2,3,...,n]
  ṗ      -   Cartesian power         [[[2],[3]],[[2,2],[2,3],[3,2],[3,3]],[[2,2,2],...],...]
    Ẏ    - tighten                   [[2],[3],[2,2],[2,3],[3,2],[3,3],[2,2,2],...]
     §   - sums                      [ 2,  3,   4,    5,    5,    6,     6,...]
       ‘ - increment                 n+1
      ċ  - count occurrences         P(n)

Haskell , 26 bajtów

(l!!)
l=1:1:1:2:scanl(+)2l

Wypróbuj online! Zwraca indeks n-ty z n-tego terminu.

Myślałem, że „oczywiste” rozwiązanie rekurencyjne poniżej byłoby nie do pokonania, ale potem to znalazłem. Jest podobny do klasycznego wyrażenia golfowego l=1:scanl(+)1ldla nieskończonej listy Fibonacciego, ale tutaj różnica między sąsiednimi elementami to termin 4 pozycje wstecz. Możemy pisać bardziej bezpośrednio l=1:1:zipWith(+)l(0:l), ale to dłużej.

Gdyby to wyzwanie pozwoliło na uzyskanie nieskończonej ilości danych wyjściowych, moglibyśmy wyciąć pierwszy wiersz i mieć 20 bajtów.

27 bajtów

f n|n<3=1|1>0=f(n-2)+f(n-3)

Wypróbuj online!

Python 2 , 30 bajtów

f=lambda n:n<3or f(n-2)+f(n-3)

Wypróbuj online!

Zwraca indeksowany n-ty termin zero. Wyjścia Truedla 1.

Wolfram Language (Mathematica) , 33 bajty

a@0=a@1=a@2=1;a@n_:=a[n-2]+a[n-3]   

1-indeksowany, zwraca n-ty termin

Wypróbuj online!

Octave / MATLAB, 35 33 bajtów

@(n)[1 filter(1,'cbaa'-98,2:n<5)]

Wyprowadza pierwsze n wyrażeń.

Wypróbuj online!

Jak to działa

Anonimowa funkcja, która implementuje filtr rekurencyjny .

'cbaa'-98jest krótszą formą do wyprodukowania [1 0 -1 -1].

2:n<5jest krótszą formą do wytworzenia [1 1 1 0 0 ··· 0](warunki n- 1).

filter(1,[1 0 -1 -1],[1 1 1 0 0 ··· 0])przekazuje dane wejściowe [1 1 1 0 0 ··· 0]przez filtr czasu dyskretnego zdefiniowany przez funkcję przesyłania ze współczynnikiem licznika 1i współczynnikiem mianownika [1 0 -1 -1].

J , 22 bajty

-2 bajty dzięki ngn i Galen

formularz zamknięty, 26 bajtów

0.5<.@+1.04535%~1.32472^<:

Wypróbuj online!

iteracyjny, 22 bajty

(],1#._2 _3{ ::1])^:[#

Wypróbuj online!

Retina , 47 42 bajtów

K`0¶1¶0
"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*
6,G`

Wypróbuj online! Generuje pierwsze nwarunki w osobnych wierszach. Wyjaśnienie:

K`0¶1¶0

Wymień wkład z warunkami dla -2, -1i 0.

"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*

Wygeneruj następne nterminy, korzystając z relacji powtarzalności. *_tutaj jest skrót, dla $&*_którego konwertuje (pierwszą) liczbę w dopasowaniu na unarny, podczas gdy $1*jest skrót, dla $1*_którego zamienia środkową liczbę na unarny. W $.(Zwraca sumę dziesiętną jednoargumentowych swoich argumentów, czyli sumę liczb pierwszych i środkowych.

6,G`

Odrzuć pierwsze sześć znaków, tj. Pierwsze trzy linie.

Cubix , 20 bajtów

To jest indeksowane 0 i zwraca N- ty termin

;@UOI010+p?/sqq;W.\(

Wypróbuj online!

Owija się w kostkę o długości boku 2

    ; @
    U O
I 0 1 0 + p ? /
s q q ; W . \ (
    . .
    . .

Zobacz, jak biegnie

• I010 - Inicjuje stos
• +p? - Dodaje górę stosu, wyciąga licznik z dołu stosu i testuje
• /;UO@ - Jeśli licznik wynosi 0, odbij się od górnej powierzchni, usuń TOS, zawracanie, wyjście i zatrzymanie
• \(sqq;W - Jeśli licznik jest dodatni, odbij, zmniejsz licznik, zamień TOS, naciśnij dwa razy od góry do dołu, usuń TOS i przesuń linię z powrotem do głównej pętli.

Python 2 , 56 48 bajtów

f=lambda n,a=1,b=1,c=1:n>2and f(n-1,b,c,a+b)or c

Wypróbuj online!

Zwraca ntą wartość, indeksowaną 0.

Perl 6 , 24 bajtów

{(1,1,1,*+*+!*...*)[$_]}

Wypróbuj online!

Całkiem standardowa generowana sekwencja, z każdym nowym elementem generowanym przez wyrażenie * + * + !*. Dodaje to trzeci poprzedni element, drugi poprzedni element i logiczną negację poprzedniego elementu, która zawsze Falsejest równa zero.

05AB1E , 8 bajtów

1Ð)λ£₂₃+

Wypróbuj online!

1Ð)1D)3Å1$n$£

W jaki sposób?

1Ð)λ£₂₃+ | Full program.
1Ð)      | Initialize the stack with [1, 1, 1].
   λ     | Begin the recursive generation of a list: Starting from some base case,
         | this command generates an infinite list with the pattern function given.
    £    | Flag for λ. Instead of outputting an infinite stream, only print the first n.
     ₂₃+ | Add a(n-2) and a(n-3).

APL (Dyalog Unicode) , 20 18 17 bajtów ^SBCS

Ten kod ma indeks 1. Jest to ta sama liczba bajtów, aby uzyskać nelementy sekwencji Padovan, ponieważ musisz upuścić ostatnich kilku dodatkowych członków. Jest to również ta sama liczba bajtów, aby uzyskać indeksowanie 0.

Edycja: -2 bajty dzięki ngn. -1 bajt dzięki ngn

4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

Wypróbuj online!

Wyjaśnienie

4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

  ⍺(. . . .)⍣⎕⍵   This format simply takes the input ⎕ and applies the function
                   inside the brackets (...) to its operands (here marked ⍵ and ⍺).
  2(. . .+/)⍣⎕×⍳3  In this case, our ⍵, the left argument, is the array 1 1 1,
                   where we save our results as the function is repeatedly applied
                   and our ⍺, 2, is our right argument and is immediately applied to +/,
                   so that we have 2+/ which will return the pairwise sums of our array.
       2⌷          We take the second pairwise sum, f(n-2) + f(n-3)
    ⊢,⍨            And add it to the head of our array.
4⌷                 When we've finished adding Padovan numbers to the end of our list,
                   the n-th Padovan number (1-indexed) is the 4th member of that list,
                   and so, we implicitly return that.

K (ngn / k) , 24 20 bajtów

-4 bajty dzięki ngn!

{$[x<3;1;+/o'x-2 3]}

Wypróbuj online!

Indeksowane 0, pierwsze N ​​warunków

x86 32-bitowy kod maszynowy, 17 bajtów

53 33 db f7 e3 43 83 c1 04 03 d8 93 92 e2 fa 5b c3

Demontaż:

00CE1250 53                   push        ebx  
00CE1251 33 DB                xor         ebx,ebx  
00CE1253 F7 E3                mul         eax,ebx  
00CE1255 43                   inc         ebx  
00CE1256 83 C1 04             add         ecx,4  
00CE1259 03 D8                add         ebx,eax  
00CE125B 93                   xchg        eax,ebx  
00CE125C 92                   xchg        eax,edx  
00CE125D E2 FA                loop        myloop (0CE1259h)  
00CE125F 5B                   pop         ebx  
00CE1260 C3                   ret

Jest indeksowany na 0. Inicjalizacja jest dogodnie osiągana poprzez obliczenie eax * 0. 128-bitowym wynikiem jest 0, i przechodzi w edx: eax.

Na początku każdej iteracji kolejność rejestrów to ebx, eax, edx. Musiałem wybrać właściwą kolejność, aby skorzystać z kodowania xchg eaxinstrukcji - 1 bajt.

Musiałem dodać 4 do licznika pętli, aby pozwolić na osiągnięcie wyniku eax, który utrzymuje wartość zwracaną przez funkcję w fastcallkonwencji.

Mógłbym użyć innej konwencji wywoływania, która nie wymaga zapisywania i przywracania ebx, ale i fastcalltak jest fajna :)

Galaretka , 11 bajtów

5B+Ɲ2ị;Ʋ⁸¡Ḣ

Wypróbuj online!

0-indeksowane.

Lua 5.3,49 48 bajtów

function f(n)return n<4 and 1or f(n-2)+f(n-3)end

Wypróbuj online!

Vanilla Lua nie ma przymusu wartości logicznych na ciągi znaków (nawet tonumber(true)zwraca nil), więc musisz użyć operatora pseudo-trójskładnikowego. Ta wersja ma indeks 1, podobnie jak wszystkie Lua. 1orCzęść ma zostać zmieniona na 1 orw Lua 5.1, który ma inny sposób Lexing liczb.

Rubinowy , 26 bajtów

f=->n{n<3?1:f[n-2]+f[n-3]}

Wypróbuj online!

JavaScript (ES6), 23 bajty

$a(0)=a(1)=a(2)=1$

$N$

f=n=>n<3||f(n-2)+f(n-3)

Wypróbuj online!

Japt -N , 12 bajtów

<3ªßUµ2 +ß´U

Spróbuj

TI-BASIC (TI-84), 34 bajty

[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1

$N$

Wejście jest w Ans.
Wyjście jest włączone Ansi jest automatycznie drukowane.

Doszedłem do wniosku, że minęło już wystarczająco dużo czasu, a także opublikowano wiele odpowiedzi, z których wiele było poza tą odpowiedzią.

Przykład:

0
               0
prgmCDGFD
               1
9
               9
prgmCDGFD
               9
16
              16
prgmCDGFD
              65

Wyjaśnienie:

[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1      ;full program (example input: 6)

[[0,1,0][0,0,1][1,1,0]]                     ;generate the following matrix:
                                            ; [0 1 0]
                                            ; [0 0 1]
                                            ; [1 1 0]
                       ^(Ans+5              ;then raise it to the power of: input + 5
                                            ; [4  7 5]
                                            ; [5  9 7]
                                            ; [7 12 9]
                               Ans(1,1      ;get the top-left index and leave it in "Ans"
                                            ;implicitly print Ans

Pyth, 16 bajtów

L?<b3!b+y-b2y-b3

To definiuje funkcję y. Wypróbuj tutaj!

Oto zabawniejsze rozwiązanie, choć jest o 9 bajtów dłuższe; bajty można jednak ogolić.

+l{sa.pMf.Am&>d2%d2T./QY!

Wykorzystuje to definicję podaną przez Davida Callana na stronie OEIS: „a (n) = liczba kompozycji nw częściach nieparzystych i> = 3.” Wypróbuj tutaj! Pobiera dane wejściowe bezpośrednio zamiast definiować funkcję.

Java, 41 bajtów

Nie można użyć lambda (błąd czasu wykonywania). Port tej odpowiedzi Javascript

int f(int n){return n<3?1:f(n-2)+f(n-3);}

TIO

R + pryr , 38 36 bajtów

Funkcja rekurencyjna o indeksie zerowym.

f=pryr::f(`if`(n<3,1,f(n-2)+f(n-3)))

Wypróbuj online!

Dzięki @Giuseppe za wskazanie dwóch oczywiście niepotrzebnych bajtów.

C (brzęk) , 41 33 bajtów

a(i){return i<3?1:a(i-2)+a(i-3);}

Wypróbuj online!

C # (interaktywny kompilator Visual C #) , 34 bajty

int f(int g)=>g<3?1:f(g-2)+f(g-3);

Wypróbuj online!

Perl 5 , 34 bajtów

sub f{"@_"<3||f("@_"-2)+f("@_"-3)}

Wypróbuj online!

Wolfram Language (Mathematica) , 26 bajtów

If[#<3,1,#0[#-2]+#0[#-3]]&

Wypróbuj online!

Pari / GP , 28 bajtów

0-indeksowane.

f(n)=if(n<3,1,f(n-2)+f(n-3))

Wypróbuj online!

Pari / GP , 35 bajtów

1-indeksowany.

n->Vec((1+x+O(x^n))/(1-x^2-x^3))[n]

Wypróbuj online!

$\frac{1+x}{1-x^2-x^3}$