Olimpiade Sains Provinsi (OSP) 2016 - Komputer, Nomor 17

Ada beberapa pendakatan untuk menyelesaikan soal ini. Salah satunya adalah dynamic programming.

Misalkan f(i, c) = banyaknya binary string dengan panjang i dan digit terakhirnya adalah c (c bisa bernilai 1 atau 0). Kasus dasarnya adalah f(1, 0) = 1 dan f(1, 1) = 1.

Perhatikan bahwa untuk binary string dengan panjang i dan terakhinya adalah "0" maka dapat dihitung dengan f(i, 0) = f(i-1, 0) + f(i-1, 1) untuk i > 1. Mengapa bisa begitu? Karena untuk menghitung banyaknya kemungkinan dengan panjang i kita bisa melihat dari kemungkinan banyaknya kemungkinan untuk panjang i-1. Dan karena tidak ada batasan khusus, maka sebelum "0" boleh "0" ataupun "1".

Untuk binary string dengan panjang i dan terakhirnya adalah "1", karena ada syarat bahwa binary string tidak boleh mengandung "001" maka ketika menghitung f(i, 1) dengan i > 2 harus dikurangi dengan kemungkinan jika sebelumnya adalah "00". Kemungkinan ini sama dengan f(i-1, 0) - f(i-2, 1) atau dengan kata lain sama dengan f(i-2, 0). Jadi, f(i, 1) = f(i-1, 0) + f(i-1, 1) - f(i-2, 0) untuk i > 2.

Jika kita menghitung nilai fungsi f(i, c) secara bottom-up maka akan didapatkan seperti ini

f(i, c)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	2	4	7	12	20	33	54	88	143	232	376	609	986	1596
1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987

Jawaban untuk soal ini adalah nilai f(15, 0) + f(15, 1) atau dengan kata lain banyaknya binary string dengan panjang 15 dengan digit terakhirnya 0 dan binary string dengan panjang 15 yang digit terakhirnya 1 yang memenuhi syarat, yaitu 1596 + 987 = 2583

 

Cara Lain :

Perhatikan bahwa karena binary string tidak boleh mengandung "001" maka apabila string tersebut mengandung "00", selanjutnya harus "0" terus. Kita bisa coba-coba tempatkan "00" ini mulai dari paling kiri (kita sebut ini posisi ke-0).

Jika "00" ada di posisi ke-0 maka ada 1 kemungkinan

000000000000000

Jika "00" ada di posisi ke-1 maka ada 1 kemungkinan

100000000000000

Jika "00" ada di posisi ke-2 maka ada 2 kemungkinan

010000000000000

110000000000000

Jika "00" ada di posisi ke-3 maka ada 3 kemungkinan

011000000000000

101000000000000

111000000000000

Perhatikan bentuknya. Untuk suatu posisi penempatan "00" maka ada bentuk yang bisa diobservasi. Contoh, untuk posisi ke-4 :

xx1100000000000 atau

xx0100000000000

Kita bisa isi xx1 dan xx0 dari 2 kemungkinan sebelumnya bukan?

Jika digeneralisasi maka banyaknya kemungkinan binary string yang "00"-nya diletakkan pada posisi k adalah fib(k) = fib(k-1) + fib(k-2) dengan fib(0) = 1 dan fib(1) = 1 (fungsi fibonacci).

Dapat disimpulkan, untuk binary string dengan panjang N yang tidak mengandung "001" ada fib(0) + fib(1) + fib(2) + fib(3) + ... + fib(N).

Untuk N = 15, fib(0) + fib(1) + fib(2) + ... + fib(15) = 1 + 1 + 2 + 3 + 5  + 8 + 13 + 21 + 34 + 55 + 89 + 144 + 233 + 377 + 610 + 987 = 2583