Olimpiade Sains Kota (OSK) 2017 - Komputer, Nomor 12
Berapa banyak kata sepanjang N-karakter yang dapat dibentuk dari angka-angka {0, 1, 2}, sedemikian sehingga angka-angka yang saling bersebelahan hanya berselisih maksimum 1. Contoh : Untuk N=2 terdapat 7 kata yang dapat dibentuk yaitu : <0 0>, <0 1>, <1 0>, <1 1>, <1 2>, <2 1>, <2 2>. Notasi < > menyatakan bentukan satu kata. Jika N=10, berapa banyak kata yang dapat dibentuk?
a. 8119
b. 8121
c. 8123
d. 8125
e. 8127
3 jawaban
WAS 13148 tahun lalu
9
Untuk soal ini, saya menggunakan DP;
Misal saya definisikan :
a(n) = banyak cara menempatkan 0 pada string dengan panjang n;
b(n) = banyak cara menempatkan 1 pada string dengan panjang n;
c(n) = banyak cara menempatkan 2 pada string dengan panjang n;
Misal f(n) = banyak cara menyusun string dengan panjang n, maka :
f(n) = a(n) + b(n) + c(n) ;
Karena selisih maksimal hanya 1, maka:
a(n) = a(n - 1) + b(n - 1);
b(n) = a(n - 1) + b(n - 1) + c(n - 1);
c(n) = b(n - 1) + c(n - 1);
Base case : a(1) = 1, b(1) = 1, c(1) = 1;
Dari f(n) = a(n) + b(n) + c(n), maka b(n) = a(n - 1) + b(n - 1) + c(n - 1) = f(n - 1);
Maka, f(n) = 2 * [a(n - 1) + b(n - 1) + c(n - 1)] + b(n - 1) = 2 * f(n - 1) + f(n - 2);
Dengan f(1) = a(1) + b(1) + c(1) = 1 + 1 + 1 = 3 dan f(2) = 7(diketahui dari soal), maka kita bisa mencari f(3) dan seterusnya;
f(3) = 2 * 7 + 3 = 17;
f(4) = 2 * 17 + 7 = 41;
f(5) = 2 * 41 + 17 = 99;
f(6) = 2 * 99 + 41 = 239;
f(7) = 2 * 239 + 99 = 577;
f(8) = 2 * 577 + 239 = 1393;
f(9) = 2 * 1393 + 577 = 3363;
f(10) = 2 * 3363 + 1393 = 8119(A);
Maaf jika ada kesalahan..
Zalasaa Belakang8 tahun lalu
-3
nggere pa??? :v
Masuk untuk menulis jawaban
kurang lengkap bibehhhh
