Bilangan Katalan

36

Angka Catalan ( OEIS ) adalah urutan bilangan alami yang sering muncul dalam kombinatorik.

Angka Catalan ke-n adalah jumlah kata-kata Dyck (string kurung kurung atau kurung seimbang seperti [[][]]; secara resmi didefinisikan sebagai string menggunakan dua karakter a dan b sehingga setiap substring mulai dari awal memiliki jumlah karakter lebih besar atau sama dengan angka dari b karakter, dan seluruh string memiliki jumlah a dan b karakter yang sama) dengan panjang 2n. Angka Catalan ke-n (untuk n> = 0) juga secara eksplisit didefinisikan sebagai:

Mulai dari n = 0, 20 angka Catalan pertama adalah:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...

Tantangan

Tulis program atau fungsi lengkap yang mengambil bilangan bulat n-negatif melalui STDIN atau alternatif yang dapat diterima, dan menampilkan angka Catalan ke-n. Program Anda harus bekerja minimal untuk input 0-19.

I / O

Memasukkan

Program Anda harus mengambil input dari STDIN, argumen fungsi atau salah satu alternatif yang dapat diterima per pos meta ini. Anda dapat membaca nomor yang dimasukkan sebagai representasi desimal standar, representasi unary, atau byte.

  • Jika (dan hanya jika) bahasa Anda tidak dapat mengambil input dari STDIN atau alternatif lain yang dapat diterima, itu mungkin mengambil input dari variabel hardcoded atau setara yang sesuai dalam program.

Keluaran

Program Anda harus menampilkan nomor Catalan ke STDOUT, hasil fungsi atau salah satu alternatif yang dapat diterima per pos meta ini. Anda dapat menampilkan nomor Catalan dalam representasi desimal standar, representasi unary, atau byte.

Output harus terdiri dari angka Catalan yang sesuai, secara opsional diikuti oleh satu atau lebih baris baru. Tidak ada output lain yang dapat dihasilkan, kecuali output konstan dari juru bahasa Anda yang tidak dapat ditekan (seperti salam, kode warna ANSI atau lekukan).


Ini bukan tentang menemukan bahasa yang terpendek. Ini tentang menemukan program terpendek dalam setiap bahasa. Karena itu, saya tidak akan menerima jawaban.

Dalam tantangan ini, bahasa yang lebih baru daripada tantangan dapat diterima selama mereka memiliki implementasi. Diperbolehkan (dan bahkan dianjurkan) untuk menulis sendiri penerjemah ini untuk bahasa yang sebelumnya tidak diterapkan. Selain itu, semua aturan standar harus dipatuhi. Kiriman dalam kebanyakan bahasa akan dinilai dalam byte dalam pengkodean yang sudah ada sebelumnya (biasanya UTF-8). Perhatikan juga bahwa built-in untuk menghitung angka Catalan ke-n diizinkan.

Katalog

Cuplikan Stack di bagian bawah posting ini menghasilkan katalog dari jawaban a) sebagai daftar solusi terpendek per bahasa dan b) sebagai leaderboard keseluruhan.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:

## Perl, 43 + 2 (-p flag) = 45 bytes

Anda juga dapat membuat nama bahasa menjadi tautan yang kemudian akan muncul di cuplikan:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

sebuah spaghetto
sumber
Bisakah kita mencetak / mengembalikan float daripada integer?
Alex A.
@AlexA. Ini bisa diterima.
spaghetto
Haruskah ada tag oeis ?
Vi.
1
@ Vi. Ada diskusi meta tentang itu beberapa waktu lalu dan kami sepakat bahwa oeis tidak perlu
spaghetto
@ Vi. Inilah pos meta: meta.codegolf.stackexchange.com/a/5546/8478 . Adapun beberapa alasan, Anda dapat menemukan tantangan gaya OEIS cukup andal dengan urutan dan salah satu dari nomor atau teori nomor . Apakah urutan yang diberikan benar - benar ada dalam OEIS, sama sekali tidak relevan dengan tantangan.
Martin Ender

Jawaban:

26

C, 78 52 39 34 33 byte

Lebih banyak keajaiban C (terima kasih xsot):

c(n){return!n?:(4+6./~n)*c(n-1);}

?: adalah ekstensi GNU .


Kali ini dengan memperluas perulangan di bawah ini (terima kasih xnor dan Thomas Kwa):

Belum rekursi lain

c(n){return n?(4+6./~n)*c(n-1):1;}

-(n+1)digantikan oleh ~n, yang setara dalam komplemen dua dan menyimpan 4 byte.


Sekali lagi sebagai fungsi, tetapi kali ini memanfaatkan perulangan berikut:

terulang

c(n){return n?2.*(2*n++-1)/n*c(n-2):1;}

c(n)memasuki rekursi tak terbatas untuk negatif n, meskipun itu tidak relevan untuk tantangan ini.


Karena memanggil fungsi tampaknya merupakan alternatif yang dapat diterima untuk konsol I / O:

c(n){double c=1,k=2;while(k<=n)c*=1+n/k++;return c;}

c(n)mengambil intdan mengembalikan sebuah int.


Entri asli:

main(n){scanf("%d",&n);double c=1,k=2;while(k<=n)c*=1+n/k++;printf("%.0f",c);}

Alih-alih langsung menghitung definisi, rumus ditulis ulang sebagai:

menulis kembali

Rumus mengasumsikan n >= 2, tetapi kode bertanggung jawab untuk n = 0dan n = 1juga.

Dalam kekacauan C di atas, ndan kmemiliki peran yang sama seperti dalam formula, saat cmengakumulasi produk. Semua perhitungan dilakukan dalam floating point menggunakan double, yang hampir selalu merupakan ide yang buruk, tetapi dalam kasus ini hasilnya benar hingga n = 19 setidaknya, jadi tidak apa-apa.

float akan menghemat 1 byte, sayangnya itu tidak cukup tepat.

Stefano Sanfilippo
sumber
Saya tidak dapat menguji ini sekarang, tetapi saya pikir Anda dapat mempersingkat lebih lanjut:c(n){return!n?:(4+6./~n)*c(n-1);}
xsot
Terima kasih @ xsot, saya tidak tahu ?:! Rupanya, itu adalah ekstensi GNU C tapi saya pikir itu masih memenuhi syarat.
Stefano Sanfilippo
23

Jelly , 4 byte

Ḥc÷‘

Cobalah online!

Bagaimana itu bekerja

Ḥc÷‘    Left argument: z

Ḥ       Compute 2z.
 c      Hook; apply combinations to 2z and z.
  ÷‘    Divide the result by z+1.
Dennis
sumber
1
Apa arti "kait '? Bagaimana cmendapatkan 2zdan zsebagai argumennya?
xnor
@ xnor Kait berarti fungsi yang dievaluasi seperti f (x, g (x)). Ketika ada fungsi diad yang diikuti oleh fungsi diad lain, parser mengevaluasi yang pertama sebagai pengait.
lirtosiast
5
@ Dennis Apakah itu benar-benar 4 byte? Dengan karakter non-ASCII itu, mothereff.in/byte-counter mengatakan 9 byte
Luis Mendo
@LuisMendo itu mungkin penyandian yang berbeda
undergroundmonorail
3
@LuisMendo Jelly menggunakan sendiri, penyandian kustom default, di mana setiap karakter adalah satu byte. Dengan UTF-8, kode sumbernya memang panjangnya 9 byte.
Dennis
11

CJam, 12 byte

ri_2,*e!,\)/

Cobalah online.

Di luar input 11, Anda harus memberi tahu Java VM Anda untuk menggunakan lebih banyak memori. Dan saya tidak akan benar-benar merekomendasikan melampaui 11. Secara teori, ini bekerja untuk N apa pun, karena CJam menggunakan bilangan bulat presisi arbitrer.

Penjelasan

CJam tidak memiliki built-in untuk koefisien binomial, dan menghitung mereka dari tiga faktorial membutuhkan banyak byte ... jadi kita harus melakukan sesuatu yang lebih baik dari itu. :)

ri  e# Read input and convert it to integer N.
_   e# Duplicate.
2,  e# Push [0 1].
*   e# Repeat this N times, giving [0 1 0 1 ... 0 1] with N zeros and N ones.
e!  e# Compute the _distinct_ permutations of this array.
,   e# Get the number of permutations - the binomial. There happen to be 2n-over-n of
    e# of them. (Since 2n-over-n is the number of ways to choose n elements out of 2n, and
    e# and here we're choosing n positions in a 2n-element array to place the zeros in.)
\   e# Swap with N.
)/  e# Increment and divide the binomial coefficient by N+1.
Martin Ender
sumber
Ini sangat keren. +1
spaghetto
Ini pintar. Saya mencobanya dengan menghitung faktorial. Hanya butuh dua dari tiga yang biasa karena dua di antaranya sama. Masih menggunakan 17 byte ( ri_2*m!1$m!_*/\)/) dalam implementasi saya. Satu-satunya hal yang baik adalah bahwa itu jauh lebih cepat. :)
Reto Koradi
11

Mathematica, 16 13 byte

CatalanNumber

Built-in, amirite fellas: /

Versi non-builtin (21 byte):

Binomial[2#,#]/(#+1)&

Versi binomial-kurang (25 byte):

Product[(#+k)/k,{k,2,#}]&
sebuah spaghetto
sumber
10

TI-BASIC, 11 byte

(2Ans) nCr Ans/(Ans+1

Anehnya, nCr memiliki prioritas lebih tinggi daripada multiplikasi.

lirtosiast
sumber
10

Python 3, 33 byte

f=lambda n:0**n or(4+6/~n)*f(n-1)

Menggunakan pengulangan

f(0) = 1
f(n) = (4-6/(n+1)) * f(n-1)

Kasing dasar 0 ditangani sebagai 0**n or, yang berhenti seperti 1kapan n==0dan sebaliknya mengevaluasi ekspresi rekursif di sebelah kanan. Operator bitwise ~n==-n-1memperpendek penyebut dan menghemat parens.

Python 3 digunakan untuk divisi float-nya. Python 2 dapat melakukan hal yang sama dengan satu byte lagi untuk ditulis 6..

Tidak
sumber
Mengapa tidak n<1bukan 0**n?
feersum
@feersum Ia mengembalikan Trueuntuk n==0bukan 1. Tentu saja, True == 1tetapi True is not 1dan hasilnya berbeda. Saya berharap ini tidak diizinkan. Apakah Anda tahu jika kami memiliki keputusan tentang ini?
xnor
Saya percaya bahwa itu baik-baik saja. isinstance(True, int) is TrueLagipula.
feersum
2
Saya pikir itu masih rapuh dalam kasus umum dan lebih di sini di mana tantangan menentukan output sebagai angka atau perwakilannya. Tapi, hingga @quartata
xnor
7

J, 8 byte

>:%~]!+:

Ini adalah kereta monadik; menggunakan rumus (2x nCr x) / (x + 1). Coba di sini .

lirtosiast
sumber
7

pl, 4 byte

☼ç▲÷

Cobalah online.

Penjelasan

Dalam pl, fungsi mengeluarkan argumennya dari stack dan mendorong hasilnya kembali ke stack. Biasanya ketika tidak ada cukup argumen di stack, fungsi tersebut gagal secara diam-diam. Namun, sesuatu yang istimewa terjadi ketika jumlah argumen pada stack adalah salah satu dari arity fungsi - variabel input _ditambahkan ke daftar argumen:

☼ç▲÷

☼      double: takes _ as the argument since there is nothing on the stack
 ç     combinations: since there is only one item on the stack (and arity is 2), it adds _ to the argument list (combinations(2_,_))
  ▲    increment last used var (_)
   ÷   divide: adds _ to the argument list again

Akibatnya, ini adalah kodesemu:

divide(combinations(double(_),_),_+1);
sebuah spaghetto
sumber
6

Sesos , 94 86 68 byte

8 byte dengan mengubah faktorial dari versi 1 ke versi 2.

18 byte dengan komputasi n!(n+1)!dalam satu langkah. Sangat terinspirasi oleh algoritma uji keutamaan Dennis .

Hexdump:

0000000: 16f8de a59f17 a0ebba 7f4cd3 e05f3f cf0fd0 a0ebde  ..........L.._?......
0000015: b1c1bb 76fe18 8cc1bb 76fe1c e0fbda 390fda bde3d8  ...v.....v.....9.....
000002a: 000fbe af9d1b b47bc7 cfc11c b47bc7 cff1fa e07bda  .......{.....{.....{.
000003f: 39e83e cf07                                       9.>..

Cobalah online!

Menggunakan formula a(n) = (2n)! / (n!(n+1)!).

  • The factorial-er: versi 1 (di tempat, memori konstan), versi 2 (di tempat, memori linier)
  • Pengganda: di sini (di tempat, memori konstan)
  • Pembagi: di sini (tidak berhenti jika tidak dapat dibagi)

Assembler

set numin
set numout
get
jmp,sub 1,fwd 1,add 1,fwd 2,add 2,rwd 3,jnz
fwd 1,add 1
jmp
  jmp,sub 1,rwd 1,add 1,rwd 1,add 1,rwd 1,add 1,fwd 3,jnz
  rwd 1,sub 1,rwd 1,sub 1,rwd 1
  jmp,sub 1,fwd 3,add 1,rwd 3,jnz
  fwd 1
jnz
fwd 3
jmp
  jmp
    sub 1,rwd 1
    jmp,sub 1,rwd 1,add 1,rwd 1,add 1,fwd 2,jnz
    rwd 2
    jmp,sub 1,fwd 2,add 1,rwd 2,jnz
    fwd 3
  jnz
  rwd 1
  jmp,sub 1,jnz
  rwd 1
  jmp,sub 1,fwd 2,add 1,rwd 2,jnz
  fwd 3
jnz 
fwd 1
jmp
  jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz
  fwd 1,sub 1,fwd 1
  jmp,sub 1,rwd 2,add 1,fwd 2,jnz
  rwd 1
jnz
rwd 2
jmp
  jmp
    sub 1,fwd 1
    jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz
    fwd 2
    jmp,sub 1,rwd 2,add 1,fwd 2,jnz
    rwd 3
  jnz
  fwd 1
  jmp,sub 1,jnz
  fwd 1
  jmp,sub 1,rwd 2,add 1,fwd 2,jnz
  rwd 3
jnz 
fwd 1
jmp
  fwd 1,add 1,rwd 3
  jmp,sub 1,fwd 1,add 1,fwd 1,sub 1,rwd 2,jnz
  fwd 1
  jmp,sub 1,rwd 1,add 1,fwd 1,jnz
  fwd 1
jnz
fwd 1
put

Setara dengan Brainfuck

Script Retina ini digunakan untuk menghasilkan setara dengan brainfuck. Perhatikan bahwa itu hanya menerima satu digit sebagai argumen perintah, dan tidak memeriksa apakah perintah ada di komentar.

[->+>>++<<<]>+
[[-<+<+<+>>>]<-<-<[->>>+<<<]>]>>>
[[-<[-<+<+>>]<<[->>+<<]>>>]<[-]<[->>+<<]>>>]>
[[->+>+<<]>->[-<<+>>]<]<<
[[->[->+>+<<]>>[-<<+>>]<<<]>[-]>[-<<+>>]<<<]>
[>+<<<[->+>-<<]>[-<+>]>]>
Biarawati Bocor
sumber
5

Pyth, 8

/.cyQQhQ

Cobalah secara online atau jalankan Test Suite

Penjelasan

/.cyQQhQ   ## implicit: Q = eval(input())
/     hQ   ## integer division by (Q + 1)
 .c        ## nCr
   yQ      ## use Q * 2 as n
     Q     ## use Q as r
FryAmTheEggman
sumber
5

Serius, 9 byte

,;;u)τ╣E\

Hex Dump:

2c3b3b7529e7b9455c

Cobalah online

Penjelasan:

,                   Read in evaluated input n
 ;;                 Duplicate it twice
   u)               Increment n and rotate it to bottom of stack
     τ╣             Double n, then push 2n-th row of Pascal's triangle
       E            Look-up nth element of the row, and so push 2nCn
        \           Divide it by the n+1 below it.
kuintopia
sumber
Anda dapat menyimpan byte dengan mengeksploitasi fakta bahwa deretan segitiga Pascal simetris, jadi median dari 2nbaris ke - t adalah C(2n,n). Jadi: ,;u@τ╣║/selama 8 byte.
Mego
Apa? Bukankah 2nCn maks dari baris ke-2?
kuintopia
Ya, dan itu juga median. Jadi, keduanya dan Makan bekerja.
Mego
@Mego Saya khawatir tentang implementasi median Anda jika ada yang bisa menjadi median dan maks dalam hal daftar tidak semua angka yang sama. Jika maksud Anda "di tengah daftar" maka Anda dapat memilih nama yang berbeda untuk itu ...
quintopia
Ya, ini tengah daftar. Untuk daftar yang disortir, ini adalah median statistik yang khas, tetapi untuk daftar yang tidak disortir itu hanya tengah (atau rata-rata 2 elemen tengah)
Mego
4

JavaScript (ES6), 24 byte

Berdasarkan jawaban Python .

c=x=>x?(4+6/~x)*c(x-1):1

Bagaimana itu bekerja

c=x=>x?(4+6/~x)*c(x-1):1
c=x=>                     // Define a function c that takes a parameter x and returns:
     x?               :1  //  If x == 0, 1.
       (4+6/~x)           //  Otherwise, (4 + (6 / (-x - 1)))
               *c(x-1)    //  times the previous item in the sequence.

Saya pikir ini adalah yang terpendek, tetapi saran dipersilahkan!

Produksi ETH
sumber
4

Julia, 23 byte

n->binomial(2n,n)/(n+1)

Ini adalah fungsi anonim yang menerima integer dan mengembalikan float. Ini menggunakan rumus binomial dasar. Untuk menyebutnya, berikan nama, mis f=n->....

Alex A.
sumber
4

Matlab, 35 25 byte

@(n)nchoosek(2*n,n)/(n+1)

Oktaf, 23 byte

@(n)nchoosek(2*n,n++)/n
costrom
sumber
2
Anda dapat menggunakan @(n)alih-alih fungsi, fungsi anonim ok.
FryAmTheEggman
Saya telah melihat beberapa jawaban di sini sebelum yang memiliki variabel workspace sedang diakses (menyiratkan mereka sudah ditetapkan oleh pengguna di tempat lain). Skrip dalam MATLAB / Oktaf juga dapat muncul sebagai cuplikan sederhana. Saya telah membuatnya kembali menjadi fungsi untuk saat ini ...
costrom
1
Anda dapat menjatuhkan 2 byte lebih banyak dengan post-incrementing n:@(n)nchoosek(2*n,n++)/n
gelas kimia
@ speaker terima kasih atas tipnya! itu hanya bekerja di Octave, bukan Matlab, jadi saya sudah membaginya
costrom
@costrom Itu menarik. Saya kira .../++ntidak berhasil juga. : /
gelas
4

𝔼𝕊𝕄𝕚𝕟, 3 karakter / 6 byte

Мƅï

Try it here (Firefox only).

Dibangun ftw! Sangat senang saya menerapkan math.js sejak dini.

Solusi bonus, 12 karakter / 19 byte

Мơ 2*ï,ï)/⧺ï

Try it here (Firefox only).

Ay! Byte 19!

Mengevaluasi ke pseudo-ES6 sebagai:

nchoosek(2*input,input)/(input+1)
Mama Fun Roll
sumber
3

Haskell, 27 byte

g 0=1
g n=(4-6/(n+1))*g(n-1)

Formula rekursif. Pasti ada cara untuk menghemat orangtua ...

Langsung mengambil produk itu 2 byte lebih lama:

g n=product[4-6/i|i<-[2..n+1]]
Tidak
sumber
Di mana kode Anda membaca dari stdin atau menulis ke stdout?
user2845840
2
@ user2845840 Fungsi adalah salah satu alternatif yang dapat diterima yang terkait dengan spesifikasi.
xnor
g(n-1)=> g$n-1menyimpan satu byte. Sunting: sebenarnya ini tidak berfungsi karena rumus diartikan sebagai (...*g) (n-1).
Pasang kembali Monica
3

Dyalog APL, 9 byte

+∘1÷⍨⊢!+⍨

Ini adalah kereta monadik; menggunakan rumus (2x nCr x) / (x + 1). Cobalah online di sini .

lirtosiast
sumber
3

C, 122 121 119 108 byte

main(j,v)char**v;{long long p=1,i,n=atoi(v[1]);for(j=0,i=n+1;i<2*n;p=(p*++i)/++j);p=n?p/n:p;printf("%d",p);}

Saya menggunakan gcc (GCC) 3.4.4 (cygming special, gdc 0.12, menggunakan dmd 0.125) untuk dikompilasi di lingkungan windows cygwin. Input masuk pada baris perintah. Ini mirip dengan solusi Python Sherlock9 tetapi loop digabungkan menjadi satu untuk menghindari overflow dan mendapatkan output hingga angka Catalan ke-20 (n = 19).

Cleblanc
sumber
1
Anda dapat menghapus spasi setelah koma dalam maindefinisi untuk menyimpan byte.
Alex A.
Bagus, saya akan mengedit posting sekarang
cleblanc
Anda dapat menyimpan 2 byte lebih banyak dengan char**vdaripada char *v[]. (Ruang sebelumnya *tidak diperlukan, dan jenisnya setara.)
Mat
Benar saja, itu bekerja dengan baik. Terima kasih Mat
cleblanc
Ini menggunakan beberapa hal dari halaman tips untuk mempersingkatnya. Catat bahwa untuk Ideone saya hardcoded nilai untuk n.
FryAmTheEggman
3

Javagony , 223 byte

public class C{public static int f(int a,int b){try{int z=1/(b-a);}catch(Exception e){return 1;}return a*f(a+1,b);}public static void main(String[]s){int m=Integer.parseInt(s[0])+1;System.out.println(f(m,2*m-1)/f(1,m)/m);}}

Sepenuhnya diperluas:

public class C {
    public static int f(int a,int b){
        try {
            int z=1/(b-a);
        } catch (Exception e){
            return 1;
        }
        return a*f(a+1,b);
    }
    public static void main(String[] s){
        int m=Integer.parseInt(s[0])+1;
        System.out.println(f(m,2*m-1)/f(1,m)/m);
    }
}
cacat
sumber
Entri Esolang tidak masalah - selama Anda menggunakan juru bahasa yang dibuat sebelum kontes, semuanya baik dan valid.
Addison Crump
Lagipula
Itu java, jadi ya.
Rɪᴋᴇʀ
1
@ Pengendara Yah, ini lebih buruk dari Jawa.
Jakob
2

Japt, 16 byte

Bahkan Mathematica lebih pendek. :-/

U*2ª1 o àU l /°U

Cobalah online!

Tanpa penjelasan dan penjelasan

U*2ª 1 o àU l /° U
U*2||1 o àU l /++U

         // Implicit: U = input number
U*2||1   // Take U*2. If it is zero, take 1.
o àU     // Generate a range of this length, and calculate all combinations of length U.
l /++U   // Take the length of the result and divide by (U+1).
         // Implicit: output result

Versi alternatif, berdasarkan pada rumus rekursif:

C=_?(4+6/~Z *C$(Z-1):1};$C(U
Produksi ETH
sumber
2

Vitsy , 13 Bytes

VV2*FVF/V1+F/
V              Capture the input as a final global variable.
 V             Push it back.
  2*           Multiply it by 2
    F          Factorial.
     VF        Factorial of the input.
       /       Divide the second to top by the first.
        V1+    1+input
           F   Factorial.
            /  Divide.

Ini adalah fungsi di Vitsy . Bagaimana cara menjadikannya program yang melakukan ini, Anda bertanya? Gabungkan N. c:

Cobalah online!

Addison Crump
sumber
2

Milky Way 1.5.14 , 14 byte

':2K;*Ny;1+/A!

Penjelasan

'               # read input from the command line
 :              # duplicate the TOS
  2      1      # push integer to the stack
   K            # push a Pythonic range(0, TOS) as a list
    ;   ;       # swap the TOS and the STOS
     *          # multiply the TOS and STOS
      N         # push a list of the permutations of the TOS (for lists)
       y        # push the length of the TOS
          +     # add the STOS to the TOS
           /    # divide the TOS by the STOS
            A   # push the integer representation of the TOS
             !  # output the TOS

atau, sebagai alternatif, versi yang jauh lebih efisien:


Milky Way 1.5.14 , 22 byte

'1%{;K£1+k1-6;/4+*}A!

Penjelasan

'                      # read input from the command line
 1     1  1 6  4       # push integer to the stack
  %{  £           }    # for loop
    ;        ;         # swap the TOS and the STOS
     K                 # push a Pythonic range(0, TOS) as a list
        +       +      # add the TOS and STOS
         k             # push the negative absolute value of the TOS
           -           # subtract the STOS from the TOS
              /        # divide the TOS by the STOS
                 *     # multiply the TOS and the STOS
                   A   # push the integer representation of the TOS
                    !  # output the TOS

Pemakaian

python3 milkyway.py <path-to-code> -i <input-integer>
Zach Gates
sumber
2

Clojure / ClojureScript, 53 byte

(defn c[x](if(= 0 x)1(*(c(dec x))(- 4(/ 6(inc x))))))

Clojure bisa membuat frustasi bermain golf. Ini sangat bernasib sementara masih sangat mudah dibaca, tetapi beberapa fitur bagus benar-benar bertele-tele. (inc x)lebih idiomatis daripada (+ x 1)dan "terasa" lebih ringkas, tetapi sebenarnya tidak menyimpan karakter. Dan menulis rantai operasi lebih baik (->> x inc (/ 6) (- 4)), tetapi sebenarnya lebih lama dari sekadar melakukannya dengan cara yang jelek.

MattPutnam
sumber
2

Prolog, 42 byte

Menggunakan rekursi hampir selalu merupakan cara untuk menggunakan Prolog.

Kode:

0*1.
N*X:-M is N-1,M*Y,X is(4-6/(N+1))*Y.

Contoh:

19*X.
X = 1767263190.0

Cobalah online di sini

Emigna
sumber
Apakah Anda mendefinisikan ulang *simbol di sini?
Paŭlo Ebermann
@ PaŭloEbermann tidak tepat. Saya mendefinisikan predikat diad baru yang disebut *. Saya masih bisa menggunakan aritmatika biasa. Dalam program di atas M * Y adalah predikat yang ditentukan saya sementara (4-6 / (N + 1)) * Y adalah perkalian reguler.
Emigna
Ini sedikit lebih pendek daripada menulisnya sebagai p (X, Y): - yang bagus untuk kode golf.
Emigna
2

Oktaf, 22 byte

@(n)prod(4-6./(2:n+1))
alephalpha
sumber
2

Ceylon, 60 byte

Integer c(Integer n)=>(1:n).fold(1)((p,i)=>p*(n+i)/i)/(n+1);

Ini berfungsi hingga C 30 , karena Ceylon's Integers menandatangani angka 64-bit (C 31 mengalami overflow, akan dihitung sebagai -4050872099593203).

Saya tidak tahu apakah Ceylon memiliki fungsi matematika yang lebih tinggi built-in, tetapi kemudian mengimpor paket yang tepat mungkin akan lebih lama dari hanya menghitung ini dengan berjalan kaki.

// Catalan number C_n
//
// Question:  http://codegolf.stackexchange.com/q/66127/2338
// My answer: http://codegolf.stackexchange.com/a/66425/2338

Integer c(Integer n) =>
        // sequence of length n, starting at 1.
        (1:n)
        // starting with 1, for each element i, multiply the result
        // of the previous step by (n+i) and then divide it by i.
    .fold(1)((p, i) => p * (n + i) / i)
        // divide the result by n+1.
        / (n + 1);
Paŭlo Ebermann
sumber
2

R, 35 28 16 byte

numbers::catalan

Sunting: Gunakan paket nomor bawaan.

mnel
sumber
2

MATL , 8 byte

2*GXnGQ/

Cobalah online!

Penjelasan

2*     % take number n as input and multiply by 2
G      % push input again
Xn     % compute "2*n choose n"
G      % push input again
Q      % add 1
/      % divide
Luis Mendo
sumber
2

05AB1E , 6 byte

Dxcr>/

Penjelasan:

Code:     Stack:               Explanation:

Dxcr>/

D         [n, n]               # Duplicate of the stack. Since it's empty, input is used.
 x        [n, n, 2n]           # Pops a, pushes a, a * 2
  c       [n, n nCr 2n]        # Pops a,b pushes a nCr b
   r      [n nCr 2n, n]        # Reverses the stack
    >     [n nCr 2n, n + 1]    # Increment on the last item
     /    [(n nCr 2n)/(n + 1)] # Divides the last two items
                               # Implicit, nothing has printed, so we print the last item
Adnan
sumber
2

R, 28 byte

Tidak menggunakan paket, jadi sedikit lebih lama dari jawaban sebelumnya

choose(2*(n=scan()),n)/(n+1)
Frédéric
sumber