Всем известна последовательность Фибоначчи:
вы берете квадрат, присоединяете к нему равный квадрат, а затем повторно прикрепляете квадрат, длина стороны которого равна наибольшей длине стороны полученного прямоугольника.
В результате получается красивая спираль квадратов, чья последовательность чисел - это последовательность Фибоначчи :

Но что, если мы не хотим использовать квадраты?

Если мы будем использовать равносторонние треугольники - вместо квадратов - аналогичным образом, мы получим одинаково красивую спираль из треугольников и новую последовательность: последовательность Падована , она же A000931 :

Задача:

Учитывая положительное целое число , выведите , й член в падованской последовательности ИЛИ первые членов.$N$$a_N$$N$$N$

Предположим, что первые три члена последовательности равны . Таким образом, последовательность начнется следующим образом: $1$

Входные данные:

• Любое положительное целое число$N\ge0$

• Неверный ввод не должен приниматься во внимание

Выход:

• - й член в Padovan последовательности ИЛИ первых терминах Padovan последовательности.$N$N$N$

• Если распечатаны первые терминов, вывод может быть любым удобным (список / массив, многострочная строка и т. Д.)$N$

• Может быть индексированным или индексированным$0$$1$

Тестовые случаи:
(0-индексированный, й термин)$N$

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

(1-индексированный, первые членов)$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

Правила:

• Это код-гольф : чем меньше байтов, тем лучше!

• Стандартные лазейки запрещены.

Желе , 10 байт

9s3’Ẓæ*³FṀ

Попробуйте онлайн!

1-индексироваться. Вычисляет самый большой элемент из: где двоичная матрица удобно вычисляется как:

(это полное совпадение.)

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

Оазис , 5 байт

n-й член 0-индексированный

cd+1V

Попробуйте онлайн!

объяснение

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

Желе ,  10 9  8 байт

ŻṚm2Jc$S

Монадическая ссылка, принимающая n(0-indexed), которая дает P(n).

Попробуйте онлайн!

Как?

Реализует$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

А вот "twofer"
... совершенно другой метод также для 8 байтов (этот 1-индексированный, но гораздо медленнее):

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 байтов

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

Попробуйте онлайн! Выводит n-й член с нулевым индексом.

Я думал, что «очевидное» рекурсивное решение ниже будет непобедимым, но потом я нашел это. Это похоже на классическое выражение в гольфе l=1:scanl(+)1lдля бесконечного списка Фибоначчи, но здесь разница между соседними элементами заключается в термине 4 позиции назад. Мы можем более прямо писать l=1:1:zipWith(+)l(0:l), но это дольше.

Если бы этот вызов позволял выводить бесконечный список, мы могли бы сократить первую строку и получить 20 байтов.

27 байт

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

Попробуйте онлайн!

Python 2 , 30 байт

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

Попробуйте онлайн!

Возвращает n-й член с нулевым индексом. Выходы Trueза 1.

Wolfram Language (Mathematica) , 33 байта

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

1-индексированный, возвращает n-й член

Попробуйте онлайн!

Октава / MATLAB, 35 33 байта

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

Выводит первые n членов.

Попробуйте онлайн!

Как это работает

Анонимная функция, которая реализует рекурсивный фильтр .

'cbaa'-98это более короткая форма для производства [1 0 -1 -1].

2:n<5является более короткой формой [1 1 1 0 0 ··· 0]( n − 1 слагаемых).

filter(1,[1 0 -1 -1],[1 1 1 0 0 ··· 0])пропускает вход [1 1 1 0 0 ··· 0]через фильтр дискретного времени, определенный передаточной функцией с коэффициентами числителя 1и знаменателя [1 0 -1 -1].

J , 22 байта

-2 байта благодаря ngn и Galen

закрытая форма, 26 байт

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

Попробуйте онлайн!

итеративный, 22 байта

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

Попробуйте онлайн!

Сетчатка , 47 42 байта

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

Попробуйте онлайн! Выводит первые nслагаемые на отдельных строках. Объяснение:

K`0¶1¶0

Заменить вход с условиями для -2, -1и 0.

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

Создайте следующие nчлены, используя отношение повторения. *_здесь сокращение, $&*_которое преобразует (первое) число в совпадении в одинарное, а $1*сокращение, в $1*_котором среднее число преобразуется в одинарное. В $.(возвращает десятичную сумму его одинарных аргументов, т.е. суммы первого и среднего числа.

6,G`

Откажитесь от первых шести символов, то есть первых трех строк.

Cubix , 20 байтов

Это 0 индексируется и выводит N- й член

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

Попробуйте онлайн!

Заворачивает в куб с длиной стороны 2

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

Смотреть это беги

• I010 - инициирует стек
• +p? - Добавляет вершину стека, вытягивает счетчик из нижней части стека и тестирует
• /;UO@ - Если счетчик равен 0, отразить на верхней грани, удалить TOS, разворот, выход и остановить
• \(sqq;W - Если счетчик положительный, отразите, уменьшите счетчик, поменяйте местами TOS, дважды нажмите сверху вниз, удалите TOS и переместите полосу назад в основной цикл.

Python 2 , 56 48 байтов

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

Попробуйте онлайн!

Возвращает n-ное значение с 0 индексами.

Perl 6 , 24 байта

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

Попробуйте онлайн!

Довольно стандартная сгенерированная последовательность с каждым новым элементом, сгенерированным выражением * + * + !*. Это добавляет третий предыдущий элемент, второй предыдущий элемент и логическое отрицание предыдущего элемента, который всегда Falseравен нулю.

05AB1E , 8 байтов

1Ð)λ£₂₃+

Попробуйте онлайн!

Терпите меня, я давно не играл в гольф. Интересно, есть ли более короткий заменитель, 1Ð)который работает в этом случае (я пробовал 1D)и 3Å1т. Д., Но ни один из них не сохраняет байтов). Выводит первые членов последовательности. Или без него он вывел бы бесконечный поток членов последовательности.$n$£

Как?

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 байтов ^SBCS

Этот код 1 проиндексирован. Это то же количество байтов, чтобы получить nэлементы последовательности Падована, так как вам нужно отбросить последние несколько дополнительных членов. Это также то же количество байтов, чтобы получить 0-индексацию.

Редактировать: -2 байта благодаря ngn. -1 байт благодаря ngn

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

Попробуйте онлайн!

объяснение

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 (нгн / к) , 24 20 байт

-4 байта благодаря ngn!

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

Попробуйте онлайн!

0 индексируется, первые N членов

32-битный машинный код x86, 17 байт

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

Разборка:

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

Это 0-проиндексировано. Инициализация обычно достигается путем вычисления eax * 0. 128-битный результат равен 0, и он идет в edx: eax.

В начале каждой итерации порядок регистров следующий: ebx, eax, edx. Мне пришлось выбрать правильный порядок, чтобы воспользоваться кодировкой для xchg eaxинструкции - 1 байт.

Мне пришлось добавить 4 к счетчику циклов, чтобы позволить выходу достичь eax, который содержит возвращаемое значение функции в fastcallсоглашении.

Я мог бы использовать другое соглашение о вызовах, которое не требует сохранения и восстановления ebx, но fastcallв любом случае это весело :)

Желе , 11 байт

5B+Ɲ2ị;Ʋ⁸¡Ḣ

Попробуйте онлайн!

0 индексированные.

Луа 5.3,49 48 байтов

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

Попробуйте онлайн!

Vanilla Lua не имеет приведения булевых значений к строкам (даже tonumber(true)возвращает nil), поэтому вы должны использовать псевдо-троичный оператор. Эта версия 1-проиндексирована, как и все Lua. Эта 1orчасть должна быть изменена на 1 orLua 5.1, в которой по-разному используются лексические числа.

Рубин , 26 байт

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

Попробуйте онлайн!

JavaScript (ES6), 23 байта

Реализует рекурсивное определение A000931 , но с , как указано в задании.$a(0)=a(1)=a(2)=1$

Возвращает ^й член, 0-проиндексированный.$N$

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

Попробуйте онлайн!

Japt -N , 12 байт

<3ªßUµ2 +ß´U

Попытайся

TI-BASIC (TI-84), 34 байта

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

0-индексированный й член последовательности.$N$

Вход находится в Ans.
Выход находится Ansи автоматически распечатывается.

Я подумал, что прошло достаточно времени, плюс было опубликовано несколько ответов, из которых многие опередили этот ответ.

Пример:

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

Объяснение:

[[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 байт

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

Это определяет функцию y. Попробуй это здесь!

Вот более забавное решение, хотя оно на 9 байт длиннее; байты могут быть побриты все же.

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

При этом используется определение, данное Дэвидом Калланом на странице OEIS: «a (n) = количество композиций из n в нечетные части и> = 3». Попробуй это здесь! Он принимает входные данные вместо определения функции.

Java, 41 байт

Не могу использовать лямбду (ошибка времени выполнения). Порт этого Javascript ответа

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

TIO

R + pryr , 38 36 байт

Нулевая индексированная рекурсивная функция.

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

Попробуйте онлайн!

Спасибо @Giuseppe за указание на два явно ненужных байта.

С (лязг) , 41 33 байт

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

Попробуйте онлайн!

C # (интерактивный компилятор Visual C #) , 34 байта

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

Попробуйте онлайн!

Perl 5 , 34 байта

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

Попробуйте онлайн!

Wolfram Language (Mathematica) , 26 байтов

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

Попробуйте онлайн!

Пари / ГП , 28 байт

0 индексированные.

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

Попробуйте онлайн!

Пари / ГП , 35 байт

1-индексироваться.

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

Попробуйте онлайн!

Производящая функция последовательности: .$\frac{1+x}{1-x^2-x^3}$