Olimpiade Sains Provinsi (OSP) 2014 - Komputer, Nomor 24

Question

String adalah kumpulan dari karakter, sedangkan substring adalah string yang berturutan yang merupakan bagian dari string lain. Misal, ABCDEF , BCDE , dan ABEC adalah string. CBBC merupakan substring dari ACBBCA namun CBCA bukan merupakan substring dari ACBBCA . Berapa banyak string yang terdiri dari huruf A, B dan C, yang memiliki panjang 8 dan tidak mengandung substring AB?

Anthony Anthony · Accepted Answer

Bisa diselesaikan dengan relasi rekurensi atau dynamic programming.
Relasi rekurensi: Misal U_i = banyaknya string yang terdiri dari huruf A, B, dan C, yang memiliki panjang i dan tidak mengandung substring AB.
U₁ = 3, U₂ = 8 (bisa dicari manual)
U_n = 3U_n-1 - U_n-2

Diperoleh U₈ = 2584.

Hendrico Bolang · Answer

kalo saya pake dynamic programming dengan cara dimana
f(n,a)=f(n-1,a)+f(n-1,b)+f(n-1,c) jumlah kombinasi dimana panjang string adalah n dan a adalah huruf terakhir dalam string tersebut
karena dicari substring tanpa mengandung ab maka untuk f(n,b):
f(n,b)=f(n-1,b)+f(n-1,c) jumlah kombinasi dimana panjang string adalah n dan b adalah huruf terakhir dalam string tersebut

f(n,c)=f(n-1,a)+f(n-1,b)+f(n-1,c) jumlah kombinasi dimana panjang string adalah n dan c adalah huruf terakhir dalam string tersebut
dengan masing-masing base case
f(1,a)=f(1,b)=f(1,c)=1
jawabannya berada di f(8,a)+f(8,b)+f(8,c)= 2584

P satvikka · Answer

cara lebih simple , bikin base casenya dulu...

dp[0][a...c]=1;

dp[n][a]=dp[n-1][a]+dp[n-1][c];

dp[n][b]=dp[n-1][a]+dp[n-1][c]+dp[-1+n][b];

dp[n][c]=dp[-1+n][a]+dp[n-2/2][c]+dp[n][b-2000/2000];

wakakak jawabannya di dp[8]

Olimpiade Sains Provinsi (OSP) 2014 - Komputer, Nomor 24

3 jawaban