Tantangan

Tulis fungsi / program yang menampilkan nelemen 'th, atau nelemen pertama , dalam urutan angka yang terkenal:

         1, 2, 4, 8, 16 ...

Oh, tunggu ... Saya lupa beberapa angka pertama:

1, 1, 1, 1, 2, 4, 8, 16 ...

Heck, saya akan menambahkan beberapa lagi untuk ukuran yang baik:

1, 1, 1, 1, 2, 4, 8, 16, 33, 69, 146, 312, 673, 1463, 3202, 7050, 15605, 34705 ...

Angka-angka tersebut adalah angka Katalan Umum yang diberikan oleh rumus (indeks-nol):

dimana

Ini adalah OEIS A004149 .

Anda dapat memilih apakah Anda ingin urutan nol atau satu diindeks. Urutannya tentu saja harus sama, jadi Anda harus menulis ulang rumus jika Anda memilikinya satu-diindeks.

Python , 51 byte

f=lambda n,k=2:n<3or k<n and f(k)*f(n-k-2)+f(n,k+1)

Cobalah online!

Sederhanakan formula ini:

Perl 6 , 44 byte

{1,1,1,1,{sum @_[2..*]Z*@_[@_-4...0,0]}...*}

Cobalah online!

Blok kode anonim yang mengembalikan urutan nilai malas yang tak terbatas. Ini cukup banyak mengimplementasikan urutan seperti yang dijelaskan, dengan cara pintas yang zip itu mengalikan semua elemen sejauh ini setelah elemen kedua dengan kebalikan dari daftar mulai dari elemen keempat dan menambahkan tambahan 1di akhir.

Penjelasan:

{                                          }  # Anonymous code block
                                       ...*   # Create an infinite sequence
 1,1,1,1,                                     # Starting with four 1s
         {                            }       # Where each new element is:
          sum                                   # The sum of
              @_[2..*]                          # The second element onwards
                      Z*                        # Zip multiplied with
                        @_[@_-4...0  ]          # The fourth last element backwards
                                   ,0           # And 1

05AB1E , 14 13 11 byte

$ƒˆ¯Âø¨¨¨PO

Cobalah online!

Menghasilkan elemen ke-n, diindeks 0.

$                # push 1 and the input
 ƒ               # repeat (input+1) times
  ˆ              #  add the top of the stack (initially 1) to the global array
   ¯             #  push the global array
    Â            #  and a reversed copy of it
     ø           #  zip the two together, giving a list of pairs
      ¨¨¨        #  drop the last 3 pairs
         P       #  take the product of each pair (or 1 if the list is empty)
          O      #  take the sum of those products
                 #  after the last iteration, this is implicitly output;
                 #  otherwise, it's added to the global array by the next iteration

JavaScript (ES6), 42 byte

Port solusi xnor .

Diindeks 0.

f=(n,k=2)=>n<3||k<n&&f(k)*f(n+~++k)+f(n,k)

Cobalah online!

JavaScript (ES6),  83  75 byte

Solusi yang lebih cepat, kurang rekursif, tetapi jauh lebih lama.

Diindeks 0.

f=(n,i,a=[p=1])=>a[n]||f(n,-~i,[...a,p+=(h=k=>k<i&&a[k]*a[i-++k]+h(k))(2)])

Cobalah online!

Haskell, 49 43 39 byte

a n=max(sum[a k*a(n-2-k)|k<-[2..n-1]])1              

Cobalah online!

Untuk n<3itu sumadalah 0, sehingga max ... 1menimbulkan ke 1.

Sunting: -6 bytes berkat @ Jo King.

Bahasa Wolfram (Mathematica) , 36 byte

Sum[#0@i#0[#-i-1],{i,3,#-1}]/. 0->1&

Cobalah online!

1-diindeks.

2-diindeks urutan 4 byte pendek: Sum[#0@i#0[#-i],{i,#-4}]/. 0->1&. Cobalah online!

05AB1E , 17 13 byte

4Å1λ£₁λ¨Â¦¦s¦¦*O+

Tidak lebih pendek dari jawaban 05AB1E yang ada , tetapi saya ingin mencoba fungsi rekursif dari versi 05AB1E yang baru sebagai latihan untuk diri saya sendiri. Mungkin bisa golf dengan beberapa byte. EDIT: Dan itu memang bisa, melihat versi rekursif dari @Grimy 's 05AB1E jawaban di bawah ini, yang merupakan 13 byte .

Output yang pertama $n$item: Coba online .

Dapat diubah menjadi berbasis 0 $n$item ketika mengganti £dengan è: Cobalah online ;
atau daftar tanpa batas dengan menghapus £: Coba online .

Penjelasan:

Ini mengimplementasikan rumus yang digunakan dalam deskripsi tantangan seperti ini:
$a(n)= a(n-1) + \sum_{k=2}^{n-1}(a(k)\cdot a(n-1-k))$

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

   λ               # Create a recursive environment,
    £              # to output the first (implicit) input amount of results after we're done
4Å1                # Start this recursive list with [1,1,1,1], thus a(0)=a(1)=a(2)=a(3)=1
                   # Within the recursive environment, do the following:
      λ            #  Push the list of values in the range [a(0),a(n)]
       ¨           #  Remove the last one to make the range [a(0),a(n-1)]
        Â          #  Bifurcate this list (short for Duplicate & Reverse copy)
         ¦¦        #  Remove the first two items of the reversed list,
                   #  so we'll have a list with the values in the range [a(n-3),a(0)]
           s       #  Swap to get the [a(0),a(n-1)] list again
            ¦¦     #  Remove the first two items of this list as well,
                   #  so we'll have a list with the values in the range [a(2),a(n-1)]
              *    #  Multiply the values at the same indices in both lists,
                   #  so we'll have a list with the values [a(n-3)*a(2),...,a(0)*a(n-1)]
               O   #  Take the sum of this list
     ₁          +  #  And add it to the a(n-1)'th value
                   # (afterwards the resulting list is output implicitly)

Versi 13 byte dari @Grimy (pastikan untuk meningkatkan jawabannya jika Anda belum melakukannya!):

1λ£λ1šÂ¨¨¨øPO

Output yang pertama $n$ item: Coba online.

Lagi-lagi dapat diubah menjadi pengindeksan berbasis-0 atau daftar yang tidak terbatas:
- Pengindeksan (berbasis-0) 1λèλ1šÂ¨¨¨øPO: Coba online ;
- Daftar Infinite λλ1šÂ¨¨¨øPO: Cobalah online . (Perhatikan bahwa 2 byte disimpan di sini, bukan 1, karena lingkungan rekursif dimulai dengan$a(0)=1$ secara default.)

Penjelasan:

Alih-alih ini mengimplementasikan rumus yang ditemukan oleh @xnor untuk jawaban Python-nya seperti ini:
$a(n) = \sum_{k=2}^{n-1}(a(k)\cdot a(n-2-k))$

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

 λ             # Create a recursive environment,
  £            # to output the first (implicit) input amount of results after we're done
1              # Start this recursive list with 1, thus a(0)=1
               # Within the recursive environment, do the following:
   λ           #  Push the list of values in the range [a(0),a(n)]
    1š         #  Prepend 1 in front of this list
      Â        #  Bifurcate the list (short for Duplicate & Reverse copy)
       ¨¨¨     #  Remove (up to) the last three value in this reversed list
          ø    #  Create pairs with the list we bifurcated earlier
               #  (which will automatically remove any trailing items of the longer list)
           P   #  Get the product of each pair (which will result in 1 for an empty list)
            O  #  And sum the entire list
               # (afterwards the resulting list is output implicitly)

Python 3 , 59 byte

sangat tidak efisien, a(13)tidak selesai di TIO.

a=lambda n,k=2:n<4or(n-k<2)*a(n-1)or a(k)*a(n-k-2)+a(n,k+1)

Cobalah online!

Jelly , 17 byte

1WṪ;+¥×Uṫ3SƲ;@Ʋ⁸¡

Cobalah online!

Tautan monadik yang mengambil indeks-nol $n$ dan mengembalikan daftar nomor Katalan umum dari $0$ untuk $n$.

Haskell , 76 byte

1:1:1:f[1,1,1]
f(x:z)|y<-x+sum(zipWith(*)(init$init z)$reverse z)=y:f(y:x:z)

Cobalah online!

APL (Dyalog Extended) , 34 byte ^SBCS

-2 Berkat dzaima.

Lambda awalan anonim.

{⍵≤3:1⋄+/(∇⍵-1),⍵(-×⍥∇¯2+⊢)¨4…⍵}

Cobalah online!

Japt , 19 17 16 byte

Menghasilkan nistilah th, 1-diindeks.

@Zí*Zz2)Ťx}g4Æ1

Cobalah

@Zí*Zz2)Ťx}g4Æ1     :Implicit input of integer U
@                    :Function taking an array as an argument via parameter Z
 Zí                  :  Interleave Z with
    Zz2              :  Z rotated clockwise by 180 degrees (simply reversing would be a bye shorter but would modify the original array)
   *                 :  Reduce each pair by multiplcation
       )             :  End interleave
        Å            :  Slice off the first element
         ¤           :  Slice off the first 2 elements
          x          :  Reduce by addition
           }         :End function
            g        :Pass the following as Z, push the result back to it and repeat until it has length U
             4Æ1     :Map the range [0,4) to 1s
                     :Implicit output of the last element

Haskell , 65 byte

f a|a<4=1|z<-g[2..a]=sum$zipWith(*)z$reverse(1:g[0..a-4])
g=map f

Cobalah online!

Anda bisa menggunakan salah satu funtuk mendapatkan elemen tunggal dari urutan, atau meneruskan daftar nilai ke gdan mendapatkan semua indeks untuk daftar itu.

Keempat (gforth) , 99 81 byte

: f recursive dup 4 > if 0 over 3 do over 1- i - f i f * + loop else 1 then nip ;

Cobalah online!

Output adalah istilah ke-n dan input diindeks 1

Sunting: Disimpan 17 byte dengan beralih ke rumus xnor. Disimpan 1 byte lagi dengan menggunakan 1-diindeks

Penjelasan Kode

: f                     \ start a new word definition
  recursive             \ mark that this word will be recursive
  dup 4 >               \ duplicate the input and check if it is greater than 4
  if                    \ if it is:
    0 over              \ create an accumulator and copy n to top of stack
    3 do                \ start counted loop from 3 to n-1
      over 1- i - f     \ recursively calculate f(n-1-i)
      i f               \ recursively calculate f(i)
      * +               \ multiply results and add to accumulator
    loop                \ end the counted loop        
  else                  \ otherwise, if n < 5
    1                   \ put 1 on the stack
  then                  \ end the if block
  nip                   \ drop n from the stack
;                       \ end the word definition

Arang , 26 byte

Ｆ⁵⊞υ¹ＦＮ⊞υΣ✂Ｅ⮌υ×κ§υλ³→Ｉ§υ±⁴

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Mencetak angka ke-0 yang diindeks, meskipun menghitung menggunakan pengindeksan 1 secara internal. Penjelasan:

Ｆ⁵⊞υ¹

Mulai dengan a[0] = a[1] = a[2] = a[3] = a[4] = 1. Ya, ini adalah 1-diindeks, tetapi kemudian dengan nilai nol ekstra. Itu kode golf untukmu.

ＦＮ

Hitung nketentuan tambahan . Ini berlebihan, tetapi itu membuat menemukan istilah yang diinginkan lebih mudah ketika n<5.

⊞υΣ✂Ｅ⮌υ×κ§υλ³

Untuk setiap istilah, hitung istilah berikutnya sebagai jumlah dari ketentuan sejauh ini secara bertahap dikalikan dengan kebalikan dari ketentuan sejauh ini, tidak termasuk tiga istilah.

→

Ini adalah no-op yang digunakan untuk mengelabui Charcoal agar menguraikan bentuk 2-argumen Slice, jika tidak saya harus menggunakan cara yang kurang golf untuk menghilangkan tiga istilah.

Ｉ§υ±⁴

Keluarkan 4 semester terakhir.

Pyth , 30 byte

J*4]1VQ=+J+eJsPP*M.t,PJ_PJ0;<J

Cobalah online!

Mengembalikan yang pertama $n$ elemen urutan.

J*4]1VQ=+J+eJsPP*M.t,PJ_PJ0;<JQ # Full program, last Q = input (implicitly added)
J*4]1                  # J = 4 * [1] (=[1,1,1,1])
VQ                     # for N in range(Q):
  =+J                  #  J +=
     +eJ               #   J[-1] + 
        s              #    sum(                           )
           *M          #     map(__operator_mul,          )
             .t      0 #      transpose(          , pad=0)
               ,       #       [       ,         ]
                PJ     #         J[:-1] 
                  _PJ  #                 J[1::-1]
<JQ                    # J[::Q]

Alternatif: Ganti <dengan @untuk mengembalikan$n$elemen ke-urutan, 0-diindeks.

Ruby , 42 41 byte

f=->n{n<4?1:(4..n).sum{|i|f[i-1]*f[n-i]}}

Cobalah online!

1-diindeks (untuk menyimpan 1 byte)

Oktaf , 73 byte

g=(1:4).^0;for(i=3:(n=input('')))g(i+2)=g(4:i+1)*g(i-(2:i-1))';end;g(end)

Cobalah online!

-2 byte terima kasih kepada Stewie Griffin. Sekali lagi, pendekatan imperatif menang atas pendekatan rekursif fungsional. Yang itu ditunjukkan di bawah ini.

Oktaf , 75 byte

f(f=@(a)@(n){@()sum(arrayfun(@(k)a(a)(k)*a(a)(n-2-k),2:n-1)),1}{2-(n>3)}())

Cobalah online!

Captcha ingin memverifikasi saya adalah manusia ketika memposting ini. Sejujurnya, saya tidak begitu yakin .

Perl 5 -MList::Util=sum , 61 byte

sub a{my$b=-2+pop;$b<2||sum a($b+1),map{a($_)*a($b-$_)}2..$b}

Cobalah online!

C / C ++ , 70 69 67 byte

-1 byte, terima kasih kepada Jonathan.

int a(int n){int k=2,s=0;while(++k<n)s+=a(k)*a(n+~k);return s?s:1;}

Cobalah online!