Nomor Motzkin ke-n adalah jumlah jalur dari (0, 0) ke (n, 0) di mana setiap langkah berbentuk (1, -1), (1, 0) atau (1, 1), dan jalur tidak pernah masuk di bawah y = 0.
Berikut ilustrasi jalur ini untuk n = 1, 2, 3, 4, dari tautan di atas:
Urutan yang diinginkan adalah OEIS A001006 . OEIS memiliki beberapa karakterisasi lain dari urutan.
Anda akan diberi bilangan bulat positif n sebagai input. Anda harus menampilkan Nomor Motzkin ke-n.
Berikut adalah nomor Motzkin 1 hingga 10:
1, 2, 4, 9, 21, 51, 127, 323, 835, 2188
Semua metode input dan output standar diperbolehkan. Celah standar berlaku.
Ini kode golf. Bytes paling sedikit menang.
Jawaban:
MATL , 13
14byteContoh:
EDIT (16 Juni 2017): Anda dapat mencobanya online! Perhatikan juga bahwa dalam versi modern bahasa (yang setelah tanggal tantangan ini) yang
i
dapat dihapus.Penjelasan
Cukup mudah, menggunakan kesetaraan (lihat persamaan (10)) dengan fungsi hypergeometric :
Dari definisi fungsi hypergeometric
jelas bahwa urutan dua argumen pertama dapat dipertukarkan, yang menghemat satu byte.
sumber
Retina ,
5958 byteMengambil input di unary . Input 7 (yaitu
1111111
) membutuhkan waktu cukup lama tetapi masih lengkap dalam waktu kurang dari satu menit. Saya tidak akan melangkah lebih jauh dari itu.Cobalah online.
Penjelasan
Karakterisasi yang berbeda dari angka-angka Motzkin adalah jumlah string dari tiga karakter yang berbeda, di mana dua dari mereka seimbang dengan benar (maka hubungan dekat dengan angka Catalan, yang sama tanpa karakter ketiga yang independen dari balancing).
Grup penyeimbang .NET cukup bagus dalam mendeteksi string yang cocok dengan benar, jadi kami hanya menghasilkan semua string panjang
N
(menggunakan_
,<
dan>
sebagai tiga karakter) dan kemudian kami menghitung berapa banyak dari mereka yang diseimbangkan dengan benar. Misalnya untukN = 4
string yang valid adalah:Dibandingkan dengan definisi dalam tantangan,
_
sesuai dengan(1,0)
langkah,<
ke(1,1)
dan>
untuk(1,-1)
.Adapun kode aktual,
:
digunakan sebagai pemisah antara string yang berbeda. Regex kedua hanyalah bentuk golf dari standar .NET regex untuk string seimbang .Yang perlu diperhatikan adalah hanya ada satu
:
disisipkan di antara string di setiap langkah, tetapi regex kedua cocok dengan leading dan trailing:
(dan karena match tidak bisa tumpang tindih, ini berarti bahwa string yang berdekatan yang dihasilkan dari satu template di langkah terakhir tidak dapat keduanya cocok dengan keduanya ). Namun, ini bukan masalah, karena paling tidak satu dari ketiganya bisa cocok:_
kecocokan, awalan tanpa itu_
sudah seimbang dengan benar, dan<
atau>
akan membuang keseimbangan itu.>
kecocokan, string seimbang dengan itu>
, jadi_
atau<
akan membuang keseimbangan itu.<
tidak pernah bisa seimbang.sumber
Python 2, 51 byte
Menggunakan formula dari Mathworld
Menghemat karakter dengan memasukkan
M[n-1]
istilah ke dalam penjumlahan sebagaik=n-1
, yang memberiM[-1]*M[n-1]
, denganM[-1]=1
sebagai bagian dari kondisi awal.Sunting: Satu char lebih pendek menulis jumlah secara rekursif:
Pendekatan lain yang ternyata lebih lama:
sumber
Pyth, 15 byte
Ini mendefinisikan suatu fungsi
y
. Cobalah online: DemonstrasiPenjelasan:
Biarkan
y[n]
menjadin
Nomor Motzkin -th. Saya menghitungy[n]
dengan rumusPerhatikan bahwa vektor pertama lebih besar dari vektor kedua (kecuali saat menghitung
y[0]
). Jika demikian, maka Pyth secara otomatis mengabaikan angka 1 pada akhir vektor pertama, sehingga kedua vektor memiliki panjang yang sama.Formula ini adalah variasi dari salah satu formula yang terdaftar di OEIS. Mungkin sedikit bodoh. Karena angka 1 pada akhir vektor pertama (yang membuat panjangnya tidak sama), saya tidak benar-benar harus memberikan rekursi sebagai case dasar. Dan saya punya harapan, bahwa keduanya
+...1
bisa bermain golf entah bagaimana. Ternyata saya tidak bisa.Anda dapat mendefinisikan rekursi yang sama dengan produk titik dengan vektor dengan panjang yang sama dan mendefinisikan kasing
y[0] = 1
dengan dengan jumlah byte yang sama.sumber
CJam (20 byte)
Demo online
Seperti yang dicatat Mego dalam komentar pada pertanyaan, ini sangat erat terkait dengan angka Catalan: ubah
.5
ke1
dan offset indeks dengan satu (atau cukup hapus.5
seluruhnya dan biarkan indeks tidak berubah) untuk mendapatkan angka Catalan.Perulangan yang digunakan adalah
dari halaman OEIS. Perulangan yang sesuai untuk nomor Catalan terdaftar sebagai
sumber
Serius, 21 byte
Pinjam beberapa kode dari solusi Catalan Numbers quintopia , khususnya peningkatan yang saya buat di komentar.
Saya menggunakan rumus berikut:
Karena
nCk
0 untukk > n
, saya menjumlahkan semua jalann-1
, karena nilai-nilai itu semua akan 0 dan dengan demikian tidak mempengaruhi penjumlahan.Cobalah online
Penjelasan:
sumber
C(n, 2*k)
lakukan apa sekarang?C(n,k) = nCk
, atau jumlah kombinasik
item dari kumpulann
item.R, 64 byte
Menggunakan juga rumus Mathworld dari jawaban python @ xnor . Berkat aturan prioritas,
2:n-2
setara dengan0:(n-2)
.Kasus uji:
sumber
Mathematica,
3130 byteUntuk bersenang-senang, inilah versi 37 byte
dan versi 52 byte
sumber
Jelly ,
171413 byteIni menggunakan relasi perulangan dari jawaban @ PeterTaylor . Cobalah online!
Bagaimana itu bekerja
sumber
Mathematica,
444234 byteVersi 35 byte:
sumber
Pari / GP ,
383626 byteCobalah online!
Menggunakan persamaan (11) dari MathWorld :
sumber
);;7 2D$ⁿ$)╡$÷
. Saya tidak akan mempostingnya sebagai jawaban karena bahasanya lebih baru dari pertanyaan.05AB1E ,
1312 byteCobalah online!
Sementara sebagian besar jawaban menggunakan rumus atau hubungan perulangan, ini adalah pendekatan penghitungan sederhana.
Setiap jalur yang mungkin melalui grid diwakili oleh daftar koordinat y-nya. Untuk n segmen, ada total (n + 1) poin, tetapi yang pertama dan terakhir adalah 0, sehingga meninggalkan (n-1) poin untuk ditentukan.
Kami sekarang memiliki daftar jalur (belum termasuk awal dan akhir 0). Dengan konstruksi, tidak satu pun dari mereka yang berada di bawah 0. Namun, beberapa dari mereka memiliki lereng ilegal (misalnya melompat dari 0 ke 2), jadi kita perlu menyaringnya.
Ÿ
adalah rentang bawaan yang berfluktuasi . Jika ada pasangan angka yang tidak berdekatan, itu akan mengisi angka yang hilang (mis. [0, 2] menjadi [0, 1, 2]). Hanya jalur hukum yang akan dibiarkan tidak berubah.Cara yang mungkin lebih intuitif untuk memeriksa lereng ilegal adalah
üαà
(menyatakan maksimum perbedaan absolut berpasangan sama dengan 1). Namun, ini melewatkan jalur flat [0, 0, ... 0], yang membutuhkan satu byte tambahan untuk memperbaikinya.Akhirnya, perhatikan bahwa kode aktual menggunakan
.ø
tempat penjelasan ini digunakan0.ø
. Alih-alih mengelilingi jalan dengan 0s, ini mengelilingi input implisit dengan dua salinan jalur. Ini mengubah sistem koordinat terbalik dan dalam-luar, tetapi sebaliknya setara.sumber
Stax , 12 byte
Jalankan dan debug itu
Saya tidak tahu bagaimana melakukan penyusunan huruf matematika yang mewah, tetapi ini pada dasarnya bergantung pada konstruksi pemrograman yang dinamis
sumber
Ruby, 50
implementasi langsung dari hubungan perulangan.
sumber
Brain-Flak , 90 byte
Cobalah online!
sumber
ES6, 44 byte
Port langsung dari solusi Python rekursif @ xnor. Dibutuhkan
n<1?1:
karenan<1||
akan membuatf(0)
kembalitrue
.sumber
Haskell , 55 byte
Implementasi langsung rekursi.
Cobalah online!
sumber