Olimpiade Sains Kota (OSK) 2018 - Komputer, Nomor 12
Graph di samping kanan menggambarkan peternakan dimana Pak Dengklek tinggal, yang terdiri dari 10 kandang dan 16 jalan satu arah. Pak Dengklek sedang berada di kandang nomor 1 dan ingin menuju kandang nomor 10. Berapa banyak rute berbeda yang dapat ditempuh Pak Dengklek? Dua arah. Pak Dengklek sedang berada di kandang nomor 1 dan ingin menuju kandang nomor 10. Berapa banyak rute berbeda yang dapat ditempuh Pak Dengklek? Dua rute dikatakan berbeda jika pak Dengklek melalui 2 jalan yang berbeda.
a. 14
b. 15
c. 16
d. 17
e. 18
9 jawaban
Dika Wahyu7 tahun lalu
MAN 1 LAMPUNG TENGAH Go To TOKI 2019 Go Get Gold IOI 2019
8
Dynamic Programming
f(n) , n=angka dalam lingkaran
base case f(1) = 1
kita akan mendapatkan nilai dari f(n) n>1 dengan menjumlahkan banyak cara yg bisa dilalui jalur sebelumnya
f(2) = f(1) = 1
f(4) = f(1) = 1
f(5) = f(4) = 1
f(3) = f(1) + f(4) = 1 + 1 = 2
f(6) = f(3) + f(5) = 2 + 1 = 3
f(7) = f(2) + f(6) = 1 + 3 = 4
f(8) = f(5) + f(6) = 1 + 3 = 4
f(9) = f(6) + f(8) = 3 + 4 = 7
f(10) = f(6) + f(7) + f(9) = 3 + 4 + 7 =14
Kadek Surya Mahardika8 tahun lalu
0
kita bisa hitung secara manual:
untuk menuju ke jalan:
1 -> 1 cara
2 -> 1 cara
3 -> 2 cara
4 --> 1 cara
5 --> 1 cara
6 --> 3 cara
7 --> 4 cara
8 --> 4 cara
9 --> 7 cara
10 --> 14 cara (A)
Janwar Iskandar7 tahun lalu
0
1. 1-2-7-10
2. 1-3-6-8-9-10
3. 1-3-6-7-10
4. 1-3-6-9-10
5. 1-3-6-10
6. 1-4-3-6-8-10
7. 1-4-3-6-7-10
8. 1-4-3-6-9-10
9. 1-4-3-6-10
10. 1-4-5-6-7-10
11. 1-4-5-6-8-9-10
12. 1-4-5-6-9-10
13. 1-4-5-6-10
14. 1-4-5-8-9-10
terdapat 14 cara (A)
Masuk untuk menulis jawaban
no. 4 & 5 jalannya kok sama ?