Diberikan m
oleh n
cokelat, m,n
positif, output sejumlah cara untuk memecahkan bar ke mn
1 oleh 1 buah dimana setiap istirahat terjadi pada gridline a.
Ketertiban itu penting. Potongan juga dapat dibedakan, sehingga dua potong di kedua ujung batang cokelat 1 oleh 3 tidak setara.
Misalnya, untuk blok 2 dengan 2 kami memiliki:
_ _ _ _ _ _ _ _
|_‖_| -> |‗| |_| -> |_| |‗| -> |_| |_|
|_‖_| |_| |_| _ |_| _ _
|_| |_| |_|
_ _ _ _ _ _ _ _
|_‖_| -> |_| |‗| -> |‗| |_| -> |_| |_|
|_‖_| |_| |_| |_| _ _ _
|_| |_| |_|
_ _ _ _ _ _ _ _
|‗|‗| -> |_‖_| -> |_| |_| -> |_| |_|
|_|_| _ _ _ _ _ _
|_|_| |_‖_| |_| |_|
_ _ _ _ _ _ _ _
|‗|‗| -> |_|_| -> |_‖_| -> |_| |_|
|_|_| _ _ _ _ _ _
|_‖_| |_| |_| |_| |_|
Oleh karena itu ada 4 cara untuk memecah cokelat 2 x 2.
Aturan
Input akan berupa dua bilangan bulat melalui input fungsi, STDIN, baris perintah atau yang serupa. Keluarkan nomor tunggal, jumlah cara untuk memecah cokelat.
Karena angkanya naik cukup cepat, jangan khawatir jika output melebihi batas bilangan bulat bahasa Anda - kiriman Anda akan valid selama algoritma secara teoritis bekerja untuk semua input yang mungkin.
Uji kasus
Outputnya tidak tergantung pada urutan m,n
, sehingga kasus uji terdaftar sedemikian rupa m <= n
.
1 1 -> 1
1 2 -> 1
1 3 -> 2
1 4 -> 6
1 5 -> 24
1 10 -> 362880
2 2 -> 4
2 3 -> 56
2 4 -> 1712
2 5 -> 92800
2 10 -> 11106033743298560
3 3 -> 9408
3 4 -> 4948992
3 5 -> 6085088256
3 10 -> 76209753666310470268511846400
4 4 -> 63352393728
A261964 adalah angka cokelat yang disusun dalam segitiga sedemikian rupa sehingga setiap baris sesuai dengan jumlah m+n
.
sumber
options(expressions=...)
dan argumen--max-ppsize=
) akan menghasilkan kode yang lebih panjang daripada yang ini.f=
.Python 2, 135 byte
Inilah yang saya pikirkan. Ini sangat lambat, tapi ini versi yang lebih cepat (perlu repoze.lru ):
Contohnya
Penjelasan
Kode mendefinisikan fungsi
C
yang mengambil array potongan. Algoritme adalah seperti itu:for i,Q in enumerate(A)
: loop melalui array potongan.for W,H in(Q,Q[::-1])
: menghitung cara dua kali, berputar 90 derajat.for c in range(1,W)
: loop melalui posisi yang memungkinkan untuk dipisah pada.A[:i]+A[i+1:]+[(c,H),(W-c,H)]
: dapatkan daftar tanpa potongan dan dengan dua potongan baru.C(…)
: panggil fungsi lagi pada daftar itu.sum(…)
: jumlahkan hasil untuk setiap kemungkinan pemisahan.or 1
: jika tidak ada pemisahan yang mungkin terjadi, pasti ada satu cara untuk membagi cokelat.Akhirnya, kode dipanggil dengan larik yang berisi input.
sumber
ES6, 141 byte
Berdasarkan formula yang ditemukan oleh @CameronAavik. Tidak Disatukan:
sumber