Angka cokelat

17

Diberikan moleh ncokelat, m,npositif, output sejumlah cara untuk memecahkan bar ke mn1 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.

Sp3000
sumber

Jawaban:

7

Mathematica, 85 byte

f=If[##==1,1,Tr[Sum[Binomial[1##-2,i#-1]f[i,#]f[#2-i,#],{i,#2-1}]&@@@{{##},{#2,#}}]]&

Kasus cobaan

f[4,4]
(* 63352393728 *)
njpipeorgan
sumber
3

Python 3, 168 , 156 , 147 byte

Membuat peningkatan berkat obrolan

f=lambda n:n<1or n*f(n-1);a=lambda m,n,c=lambda m,n:sum(f(m*n-2)/f(i*n-1)/f((m-i)*n-1)*a(i,n)*a(m-i,n)for i in range(1,m)):+(m+n<4)or c(m,n)+c(n,m)

Tidak Disatukan:

f=lambda n:n<1or n*f(n-1) # Factorial
def a(m, n):
    if m+n < 4:
        return 1
    first = 0
    for i in range(1,m):
        first += f(m*n-2) * 1/f(i*n-1) * 1/f((m-i)*n-1) * a(i,n) * a(m-i,n)
    second = 0
    for i in range(1,n):
        second += f(m*n-2) * 1/f(i*m-1) * 1/f((n-i)*m-1) * a(i,m) * a(n-i,m)
    return first + second

Algoritma didasarkan pada makalah ini .

Saya mungkin bisa memotongnya lebih banyak, saya hanya tidak yakin di mana

Cameron Aavik
sumber
3

R, 208 198 byte

f=function(m,n){g=function(i,j){a=0;if(j>1)for(x in 2:j-1)a=a+choose(j*i-2,x*i-1)*M[x,i]*M[j-x,i];a};s=max(m,n);M=matrix(1,s,s);for(i in 1:s)for(j in 1:s)if(i*j>2)M[i,j]=M[j,i]=g(i,j)+g(j,i);M[m,n]}

Diindentasi, dengan baris baru:

f = function(m,n){
    g=function(i,j){
        a = 0
        if(j>1) for(x in 2:j-1) a = a + choose(j*i-2,x*i-1) * M[x,i] * M[j-x,i]
        a
    }
    s = max(m,n)
    M = matrix(1,s,s)
    for(i in 1:s) for(j in 1:s) if(i*j>2) M[i,j] = M[j,i] = g(i,j) + g(j,i)
    M[m,n]
}

Pemakaian:

> f(3,1)
[1] 2
> f(3,2)
[1] 56
> f(3,3)
[1] 9408
> f(4,3)
[1] 4948992
> f(5,3)
[1] 6085088256
plannapus
sumber
Secara teori, seseorang dapat menulis versi rekursif lebih pendek dari ca. 160 byte tetapi dengan cepat mencapai batas rekursi default dan ukuran stack perlindungan standar dan memodifikasi default ini (masing-masing menggunakan options(expressions=...)dan argumen --max-ppsize=) akan menghasilkan kode yang lebih panjang daripada yang ini.
plannapus
Anda dapat menyimpan dua byte dengan menghilangkannya f=.
Alex A.
2

Python 2, 135 byte

C=lambda A:sum(C(A[:i]+A[i+1:]+[(c,H),(W-c,H)])for i,Q in enumerate(A)for W,H in(Q,Q[::-1])for c in range(1,W))or 1
print C([input()])

Inilah yang saya pikirkan. Ini sangat lambat, tapi ini versi yang lebih cepat (perlu repoze.lru ):

from repoze.lru import lru_cache
C=lru_cache(maxsize=9999)(lambda A:sum(C(tuple(sorted(A[:i]+A[i+1:]+((c,H),(W-c,H)))))for i,Q in enumerate(A)for W,H in(Q,Q[::-1])for c in range(1,W))or 1)
print C((input(),))

Contohnya

$ time python2 chocolate.py <<< 2,5
92800

real    0m2.954s
user    0m0.000s
sys     0m0.015s

$ time python2 chocolate-fast.py <<< 3,5
6085088256

real    0m0.106s
user    0m0.000s
sys     0m0.015s

Penjelasan

Kode mendefinisikan fungsi Cyang mengambil array potongan. Algoritme adalah seperti itu:

  1. for i,Q in enumerate(A): loop melalui array potongan.
  2. for W,H in(Q,Q[::-1]): menghitung cara dua kali, berputar 90 derajat.
  3. for c in range(1,W): loop melalui posisi yang memungkinkan untuk dipisah pada.
  4. A[:i]+A[i+1:]+[(c,H),(W-c,H)]: dapatkan daftar tanpa potongan dan dengan dua potongan baru.
  5. C(…): panggil fungsi lagi pada daftar itu.
  6. sum(…): jumlahkan hasil untuk setiap kemungkinan pemisahan.
  7. or 1: jika tidak ada pemisahan yang mungkin terjadi, pasti ada satu cara untuk membagi cokelat.

Akhirnya, kode dipanggil dengan larik yang berisi input.

PurkkaKoodari
sumber
1

ES6, 141 byte

c=(m,n)=>(f=n=>n<2||n*f(n-1),h=(m,n)=>[...Array(m-1)].reduce((t,_,i)=>t+f(m*n-2)/f(++i*n-1)/f((m-i)*n-1)*c(i,n)*c(m-i,n),0),h(m,n)+h(n,m))||1

Berdasarkan formula yang ditemukan oleh @CameronAavik. Tidak Disatukan:

function fact(n) {
    return n < 2 ? 1 : n * f(n - 1);
}
function half(m, n) {
    total = 0;
    for (i = 1; i < m; i++)
        total += fact(m * n - 2) / fact(i * n - 1) / fact((m - i) * n - 1) * choc(i, n) * choc(m - i, n)
    return total;
}
function choc(m, n) {
    total = half(m, n) + half(n, m);
    if (!total) total = 1;
    return total;
}
Neil
sumber