Olimpiade Sains Provinsi (OSP) 2010 - Komputer, Nomor 11–12
Deskripsi Untuk Soal Nomor 11 dan 12
Suatu papan catur N x N setiapnya berisi bilangan nonnegatif. Di awal suatu bidak berada kotak (1, 1) atau yang di pojok kiri atas. Berikutnya secara berulang bidak dapat dipindahkan (1) horizontal ke kanan, atau (2) vertikal ke bawah sekian kotak sebanyak dengan bilangan pada kotak terakhir bidak itu berada, kecuali kalau membawa bidak keluar dari papan. Tujuan akhir adalah kotak (N, N) atau yang pojok kanan bawah. Bila bilangan terakhir adalah 0 dan bukan di pojok maka bidak berhenti (tidak dapat melanjutkan langkah kecuali kalau sudah mencapai tujuan).
11.
Untuk papan catur berukuran 4x4 berikut ini temukanlah ada berapa lintasan langkah-langkah yang berbeda untuk membawa bidak dari posisi awal (kotak (1, 1)) ke tujuan (kotak (4,4)).
12.
Untuk papan catur berukuran 4x4 berikut ini temukanlah ada berapa lintasan langkah-langkah yang berbeda untuk membawa bidak dari posisi awal (kotak (1, 1)) ke tujuan (kotak (10, 10)).
3 jawaban
Fransiscus Emmanuel Bunaren9 tahun lalu
2
Nomor 11
Karena petaknya sedikit, mungkin bisa kita dikira-kira
Kita lihat, petak yang bisa menuju ke [4,4] yaitu : {[4,3];[3,4];[1,4]} , dan setelah dicoba juga terdapat 3 cara menuju 4,4 dari 1,1,
Ali Jaya Meilio10 tahun lalu
1
Misalkan f(y, x) adalah banyak cara dari posisi (y, x) menuju titik paling terakhir.
Maka, f(n, n) = 1 (titik terakhir yang berisi angka 0).
Misalkan peta[y][x] adalah angka di posisi (y, x).
Maka, fungsi f bisa didefinisikan sebagai berikut
Sehingga ini bisa dikerjakan secara Dynamic Programming Bottom Up.
| 4 | 12 | 7 | 3 | 2 | 1 | 1 | 1 | 0 | 0 |
| 7 | 5 | 4 | 1 | 2 | 0 | 1 | 1 | 0 | 1 |
| 2 | 1 | 3 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Sehingga f(1, 1) = 4
Masuk untuk menulis jawaban
jawabannya berapa???