String biner adalah deretan karakter yang setiap karakternya adalah ‘0’ atau ‘1’. Substring dari suatu string adalah potongan dari string itu atau string itu sendiri. Berapa banyak string biner dengan panjang 9 yang tidak berisi substring ‘100’?
a. 113
b. 143
c. 168
d. 232
e. 253
kita bagi bagi kasus aja:
misal f(n) adalah fungsi yang memenuhi syarat diatas:
dengan base case : f(0) = 1 , f(1) = 2; dan f(2) = 4;
kasus 0____ : maka ada f(n-1) tempat yang akan kosong jika string tersebut awalnya 0
kasus 1____: maka ada f(n-1) tempat yag akan kosong juga jika string tersebut awalnya 1
kasus 100___: ada f(n-3) tempat yang kosong
jadi rumus rekursinya : f(n) = 2*f(n-1) - f(n-3);
dengan bottom up:
f(3) = 2*f(2) - f(0) = 2*4 - 1 = 7
f(4) = 2*f(3) - f(1) = 2*7 - 2 = 12
f(5) = 2*f(4) - f(2) = 24- 4 = 20
f(6) = 2*f(5) - f(3) = 40 - 7 = 33
f(7) = 2*f(6) - f(4) = 66-12 = 54
f(8) = 2*f(7) - f(5) = 108-20 = 88
f(9) = 2*f(8) - f(6) = 2*88 - 33 = 143 (B)
Base case nya :
Misal f(1) -> berarti string biner dengan panjang 1, jawabannya yang memenuhi hanyalah string "1" dan string "0" maka f(1) = 2.
base case merupakan kasus paling simpel yang bisa kita hitung dengan simpel.
mau nanya, cara bagi kasusnya gimana ya?
kalau 100nya ada di digit ke dua (_100_____) atau digit ke 3 dan sebagainya gimana?
lalu bagaimana kalau 100nya ada dua [(100100___) atau (__100100_)]?
dan kalau 100nya ada 3? (100100100)
maaf kalau banyak tanya... maklum masih ngga ngerti wkwk
itu tetep aja mau posisi 100 di mana pun tetep f(n-3) karena tersisa n-3 digit yang bisa diisi kalau masalah 100nya ada dua atau lebih itu tidak perlu dihitung karena asal muat 100 saja itu sudah dianggap tidak bisa
Masuk untuk menulis jawaban
f(3) = 2(2) - f(0) = 2*4 - 1 = 7
f(4) = 2f(3) - f(1) = 2*7 - 2 = 12
f(5) = 2f(4) - f(2) = 24- 4 = 20
f(6) = 2f(5) - f(3) = 40 - 7 = 33
f(7) = 2f(6) - f(4) = 66-12 = 54
f(8) = 2f(7) - f(5) = 108-20 = 88
f(9) = 2f(8) - f(6) = 176 - 33 = 143
JAWABAN B
gimana cara menentukan base case-nya?