f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
Cobalah online!
Pendekatan yang berbeda
Sejak saya memposting tantangan ini, saya mencoba mencari solusi rekursif untuk masalah ini. Sementara saya gagal menggunakan tidak lebih dari pena dan kertas, saya berhasil mengubah formula menjadi golf menjadi masalah praktis - setidaknya untuk definisi praktis tertentu - yang membuatnya lebih mudah untuk dianalisis.
Bayangkan sebuah game show dengan kandidat k + m yang berfungsi sebagai berikut.
Di babak 1, semua kandidat harus menyelesaikan tugas tertentu secepat mungkin. The k kandidat yang menyelesaikan tugas yang tercepat menang 1 k $ (satu kilodollar) masing-masing dan maju ke putaran 3.
Di babak 2, m kandidat yang tersisa mendapatkan kesempatan kedua untuk bergabung dengan k lainnya . Setiap kandidat ditanyai pertanyaan. Jika mereka menjawab pertanyaan dengan benar, mereka menang 1 k $ dan maju ke putaran 3. Namun, jika mereka gagal menjawab pertanyaan, mereka tersingkir dari permainan. Ini berarti ronde 3 akan memiliki antara k dan k + m kandidat, tergantung pada berapa banyak yang dapat menjawab pertanyaan mereka.
Round 3 terdiri dari m lebih kontes yang mirip dengan putaran 1. Dalam setiap kontes, peserta harus menyelesaikan tugas tertentu. Tidak seperti putaran 1, hanya satu kandidat yang menerima hadiah, tetapi semua kandidat dapat berpartisipasi dalam kontes berikutnya. Setiap kontes membayar dua kali lipat dari kontes sebelumnya; yang pertama membayar 2 k $ dan yang terakhir 2 m k $ .
Perhatikan bahwa karena semua hadiah adalah kekuatan dua, mengetahui berapa banyak hadiah uang yang diperoleh seorang kandidat berarti kita tahu jika mereka maju ke putaran 3 dan yang mana dari kontes putaran 3 yang mereka menangkan.
Asumsikan Anda sedang menonton acara pertandingan dan bulat 1 sudah berakhir, sehingga Anda tahu mana k calon telah mencapai putaran 3 dan yang m kandidat masih tertahan di putaran 2. Dalam berapa banyak cara dapat hadiah uang yang tersisa akan didistribusikan?
Setelah kita tahu yang mana dari putaran kedua ini m kandidat telah maju ke putaran 3, mudah untuk menghitung kemungkinan hasil untuk skenario tertentu. Jika j kandidat maju, ada k + j total kandidat di babak 3, dan dengan demikian k + j hasil yang mungkin untuk setiap kontes. Dengan m kontes individu di babak 3, ini membuat (k + j) m hasil untuk semua kontes m .
Sekarang, j dapat mengambil nilai apa pun antara 0 dan m , tergantung pada kandidat mana yang menjawab dengan benar di babak 2. Untuk setiap nilai fix dari j , ada m C j kombinasi yang berbeda dari kandidat j yang bisa maju ke putaran 3. Jika kita memanggil jumlah total hasil yang mungkin untuk k ronde 3 kandidat dan m ronde 2 kandidat g (m, k) , kita mendapatkan rumus berikut.
Jika kami memperbaiki k = 1 , kami mendapatkan kasus khusus berikut, yang merupakan pendekatan baru kami untuk menyelesaikan masalah aslinya.
Formula rekursif
Sekarang, anggaplah Anda tertidur selama iklan setelah ronde 1, dan bangun tepat waktu untuk melihat siapa yang memenangkan kontes terakhir ronde 3 dan dengan demikian hadiah utama 2 m k $ . Anda tidak memiliki informasi lain, bahkan berapa total hadiah uang yang dimenangkan oleh kandidat. Dalam berapa cara sisa uang hadiah dibagikan?
Jika pemenang adalah salah satu m kandidat putaran 2, kita sudah sekarang bahwa mereka harus maju ke putaran 3 . Dengan demikian, kita secara efektif memiliki k + 1 kandidat di babak 3, tetapi hanya m - 1 kandidat di babak 2. Karena kita tahu pemenang dari kontes terakhir, hanya ada kontes m - 1 dengan hasil yang tidak pasti, sehingga ada g (m - 1, k +1) kemungkinan hasil.
Jika pemenangnya adalah salah satu kandidat k yang melewati putaran 2, perhitungannya menjadi sedikit lebih rumit. Seperti sebelumnya, hanya ada ronde m - 1 yang tersisa, tetapi sekarang kami masih memiliki kandidat k di ronde 3 dan m kandidat di ronde 2. Karena jumlah ronde 2 kandidat dan jumlah ronde 3 berbeda, hasil yang mungkin tidak dapat dihitung dengan doa sederhana g . Namun, setelah ronde 2 kandidat pertama menjawab - benar atau salah - jumlah ronde 2 cocok sekali lagi dengan kontes m - 1 ronde 3. Jika kandidat maju, ada k + 1 ronde 3 kandidat dan dengan demikian g (m - 1, k + 1)kemungkinan hasil; jika kandidat dieliminasi, jumlah kandidat ronde 3 tetap pada k dan ada g (m - 1, k) hasil yang mungkin. Karena kandidat maju atau tidak, ada g (m - 1, k + 1) + g (m - 1, k) hasil yang mungkin menggabungkan kedua kasus ini.
Sekarang, jika kita menambahkan hasil potensial untuk semua kandidat k + m yang bisa memenangkan hadiah utama, hasilnya harus cocok dengan g (m, k) . Ada kontestan m babak 2 yang mengarah ke g (m - 1, k + 1) hasil potensial masing-masing, dan k babak 3 kontestan yang mengarah ke g (m - 1, k + 1) + g (m - 1, k) yang Kesimpulannya, kita mendapatkan identitas berikut.
Bersama dengan base case
dua formula ini mencirikan fungsi g sepenuhnya.
Implementasi golf
Sementara
g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)
(49 byte, 0**m
menghasilkan 1 kali m turun ke 0 ) atau genap
g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)
(48 byte, mengembalikan True, bukan 1 ) akan menjadi solusi yang valid, masih ada byte yang harus disimpan.
Jika kita mendefinisikan fungsi f yang mengambil nomor n dari ronde 1 kandidat bukan jumlah m dari ronde 2 kandidat sebagai argumen pertama, yaitu,
kami mendapatkan formula rekursif
dengan kasus dasar
Akhirnya, kita punya
jadi implementasi Python
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
( k/n
menghasilkan 1 sekali n = k ) menyelesaikan tugas yang ada dengan pengindeksan berbasis 1.