Ahli110 XPUnit 13: Pemrograman Dinamis, soal 4 dari 10
Partisi Bilangan
Hitung banyaknya cara menulis N sebagai jumlah bilangan bulat positif.
Bilangan 4 bisa ditulis sebagai 4, 3+1, 2+2, 2+1+1, dan 1+1+1+1, jadi ada 5 cara. Urutan tidak dibedakan, sehingga 1+3 sama dengan 3+1. Matematikawan India Srinivasa Ramanujan terkenal karena menemukan rumus menakjubkan untuk menghitungnya.
Masukan
Satu bilangan bulat N dari 1 sampai 250.
Keluaran
Banyaknya partisi N.
Contoh masukan dan keluaran
Contoh 1
Masukan
4
Keluaran
5
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Supaya urutan tidak dihitung dua kali, susun jumlahnya dengan bagian yang tidak naik. Bayangkan memakai koin bernilai 1, 2, sampai N tanpa batas jumlah.
Petunjuk 2
Siapkan cara[0] = 1. Untuk setiap bagian k dari 1 sampai N, dan setiap total t dari k sampai N, tambahkan cara[t - k] ke cara[t].