Olimpiade Sains Provinsi (OSP) 2015 - Komputer, Nomor 5
Di sebuah desa, tinggallah seorang gadis cantik yang hobi melompat-lompat. Di suatu pagi yang cerah, sang gadis akan berangkat ke sekolah dengan berjalan atau melompat-lompat.
Gambar di atas adalah peta desa dimana sang gadis cantik tinggal. Peta dinyatakan dalam petak? petak 6x6. Sekolah sang gadis terletak di petak [6,6], sedangkan rumah tempat tinggal sang gadis terletak di petak [1,1]. Dari suatu petak, sang gadis boleh memilih antara berjalan sejauh 1 petak ke arah utara atau timur, atau melompat sejauh 2 petak ke arah utara atau timur. Ada berapa cara agar sang gadis bisa sampai ke sekolah dengan selamat tanpa terjebur ke sungai?
3 jawaban
Muhammad Ayaz Dzulfikar11 tahun lalu
Aku noob
12
Bisa pakai dynamic programming dengan rekurens sesuai yang diberi di soal. Isi tabelnya :
| 3 | 3 | 0 | 62 | 62 | 251 |
| 0 | 0 | 0 | 36 | 0 | 89 |
| 3 | 0 | 10 | 23 | 0 | 38 |
| 2 | 5 | 7 | 13 | 0 | 15 |
| 1 | 2 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 2 |
Jadi ada 251 cara.
Muhammad Rifqi Priyo Susanto9 tahun lalu
Toolkit SMA N 1 Surakarta
Angka-angka tersebut berasal dari fungsi:
f(x, y) = f(x - 1, y) + f(x - 2, y) + f(x, y - 1) + f(x, y - 2)
dengan posisi (1, 1) berada di pojok kiri bawah dan x+ menuju ke arah timur dan y+ menuju ke arah utara.
Dengan awalan nilai f(1, 1) = 1 dan untuk x dan y yang merupakan sungai atau berada di luar kotak f(x, y) = 0.
Masuk untuk menulis jawaban
kalau boleh tau, angka-angka itu di dapat dari mana ya mas?