Olimpiade Sains Provinsi (OSP) 2012 - Komputer, Nomor 11
Dengan menggunakan hanya simbol 0, 1 dan 2, kita ingin membentuk string sedemikian rupa hingga selisih antara satu simbol dengan simbol di sebelahnya tidak lebih dari satu. Sebagai contoh, kita dapat membentuk string 011221 dan 2211010, tetapi tidak boleh membentuk string 102. Berapakah banyaknya string seperti ini yang panjangnya tepat 10 simbol?
2 jawaban
Reinhart Hermanus11 tahun lalu
TOKI 2011
7
Definisikan f(x,y) sebagai banyaknya cara untuk string sepanjang x dimana simbol paling kanan adalah y. Jawabannya nanti ada di f(10,0) + f(10,1) + f(10,2).
Untuk menghitung f(x,y) adalah sebagai berikut:
untuk x=1 berlaku f(1,y) = 1, karena untuk satu kotak pasti ada satu cara.
untuk x>1 berlaku:
f(x,0) = f(x-1,0) + f(x-1,1)
f(x,1) = f(x-1,0) + f(x-1,1) + f(x-1,2)
f(x,2) = f(x-1,1) + f(x-1,2)
Idenya adalah, apabila simbol paling kanan (simbol ke x) diisi angka 0, maka simbol kedua dari kanan (simbol ke x-1) hanya boleh diisi angka 0 atau 1. Maka f(x,0) = f(x-1,0) + f(x-1,1. Dan seterusnya.
Jawabannya ada di f(10,0) + f(10,1) + f(10,2) kalau dihitung nanti dapetnya 8119.
Anthony Anthony11 tahun lalu
0
Dapat diselesaikan dengan relasi rekurensi atau dynamic programming. Jawab: 8119
Ardhi Kamal Haq11 tahun lalu
homon penjelasannya relasi rekurensi itu gimana ya?
Masuk untuk menulis jawaban