Skip to main content

Teknik Rekursi untuk Menjawab Soal di Kertas

Teknik rekursi buat OSP
OSP kurang dari seminggu lagi dan dengan semakin seringnya muncul soal tipe ini,ingin  mencoba membahasnya. Kata orang kalau kita ngajarin orang lain jadi tambah ngerti maka jadilah post ini :v

(untuk alasan lupa dan kurangnya niat mencari soal asli, beberapa soal di post ini mungkin memiliki deskripsi berbeda dengan soal aslinya)
 pendahuluan

“banyaknya string biner dengan panjang 8 dimana tidak ada 2 angka 1 yang berdampingan adalah?”

saat membaca  soal ini, mungkin kita akan nyoba pake inklusi ekslusi yaitu banyaknya semua kemungkinan – banyaknya kemungkinan 2 angka 1 dempet + banyaknya kemungkinan 3 angka 1 dempet -… tp kasus banyak bakal mabok. Trus nyoba kuli aja, kelamaan. Jadi disini solusi yang tepat adalah menggunakan rekursi.

Misal F(n) banyaknya string yang memenuhi syarat tersebut dengan panjang n.
Misal kita punya F(n) dan F(n-1), maka kita bisa mendapat F(n+1) sebagai berikut:
Karena F(n) tidak mungkin memiliki 2 angka 1 yang berdampingan, maka didepan setiap kemungkinan F(n) dapat ditempeli 0, maka akan menjadi string dengan panjang n+1 yang memenuhi syarat

Kita tidak bisa sembarangan menempel 1 didepan string F(n), karena pasti ada F(n) yang memiliki digit terdepan 1, dan dengan menempel 1, menjadi string invalid. Tetapi perhatikan bahwa apabila kita taruh 1 sebagai angka terdepan, selanjutnya haruslah 0, lalu dengan logika sebelumnya kita bisa menempel F(n) dibelakangnya dan tidak akan menyalahi aturan. Namun karena kita sudah menggunakan 2 tempat (1 0 _ _ …), maka yang kita tempel adalah F(n-1).

Jadi dapat disimpulkan,
F(n+1) = banyaknya cara menaruh 1 didepan+ banyaknya cara menaruh 0 didepan
F(n+1) = F(n) + F(n-1)
Atau
F(n) = F(n-1) + F(n-2)
Karena memasukkan n=1,2 ke rumus tersebut akan menyebabkan nilai n tidak asli, maka F(1) dan F(2) kita kuli saja :v
F(1) = 2 (0,1). F(2) = 3 (00,01,10). Sisanya bisa dicari dengan rumusnya F(3) = 2 + 3 =5
F(4) = 8 F(5) = 13 F(6) = 21 F(7) = 34 F(8) = 55

Jadi , ada 55 string biner dengan panjang 8 yang tidak memiliki angka 1 yang berdampingan.

cara lagi satu adalah kerja dari atas dengan menulis rumus rekursi lalu substitusi
F(8) = F(7) + F(6)
F(7) = F(6) + F(5)
F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)  = 5
F(4) = 5 + 3 = 8
 …
F(8) = 55
Cara pertama (kerja dari bawah) dikenal dengan cara Bottom Up sedangkan cara kedua (kerja dari atas) dikenal dengan sedangkan cara kedua dikenal dengan Top down. Untuk dunia orat oret, cara Bottom up lebih efisien dan hemat nulisnya (menurutku) sedangkan untuk koding lebih enak pake Top down (menurutku juga). Jadi disini aku hanya akan buat dalam solusi bottom up.

Dapat dilihat dengan menggunakan rekursi, persoalan yang kelihatannya kuli berat dapat diselesaikan dengan cepat dan mudah. Jadi disini aku ingin nyoba menjelaskan teknik rekursi agar bisa lah ngurangin soal soal yang harus dikuli.

merumuskan masalah

“banyaknya string dengan panjang X yang memenuhi suatu aturan Y adalah?”
Kalau soalnya udh kyk gini, gede kemungkinannya ini pake DP. Langkah awalnya coba misalkan F(n) = banyaknya string dengan panjang n yang memenuhi aturan tersebut lalu cari hubungannya dengan nilai nilai F(n) sebelumnya maka jawabannya adalah F(X).  contohnya misal pertanyaanya banyaknya string biner dengan panjang n adalah. Maka solusi rekursinya:

F(n) banyaknya string biner dengan panjang n
Misal digit terdepan kita isi dengan 1, maka banyaknya cara mengisi digit digit lainnya adalah F(n-1)

Misal digit terdepan kita isi dengan 0, maka banyaknya cara mengisi digit digit lainnya adalah F(n-1)
Jadi F(n) = 2 F(n-1). Lalu F(1) = 2.

Untuk bisa merumuskan masalah, dibutuhkan sedikit latihan. Ntar kalau udh sukses ngerumusin 5 masalah rekursi sendiri, bakal ngerti kok :v. maka dari itu aku berikan 5 soal rekursi dan coba rumusin rekursinya kyk gimana Soal-Soal:



1.Sebagai pendekar, Pak Dengklek dan Pak Ganesh tidak boleh sakit. Supaya sehat, keduanya harus minum air putih 2 liter per hari. Pak Dengklek memiliki 2 buah gelas : satu berukuran 200 ml and satunya lagi berukuran 500 ml. Berapa banyak urutan minum Pak Dengklek dengan 2 buah gelas tersebut (tidak perlu dipakai semua) apabila ia ingin minum air putih tepat 2 liter? Urutan minum 200-200-200-200-200-500-500 dan 500-500-200- 200-200-200-200 dianggap berbeda. (OSP 2016)
2. diberikan sebuah himpunan {1,2,3,…,n}, carilah banyaknya himpunan bagian dari himpunan tersebut dimana tidak ada 2 anggota berurutan (tidak termasuk himpunan kosong)
3.
 bangun pertama sampai ketiga memiliki banyak persegi 1,5, 17. Maka banyaknya persegi pada bangun ke 10 adalah (PCS 2017)
4.
1
7
9
10
3
5
4
2
4
8
4
3
5
3
5
5
6
1
2
4
6
9
3
2
3
5
6
1
2
5
Budi ingin bermain Loncat Berhadiah. Permainan dimainkan pada sebuah kotak berukuran R x C petak. Petak kiri atas dinomori (1, 1) dan petak kanan bawah dinomori (R, C). Pada setiap petak terdapat sebuah bilangan. Budi memulai permainan dengan memilih salah satu petak pada kolom 1. Dari suatu petak (r, c), Budi harus berpindah ke petak (r, c+1), (r+1, c+1), atau (r-1, c+1). Apabila Budi sudah berada pada kolom C, permainan berakhir. Budi mendapat poin berupa jumlah seluruh bilangan yang terdapat pada petak-petak yang dilalui Budi. (OSP 2014)
5. banyaknya string dengan panjang 8 yang terdiri dari a,b,c dimana tidak ada kata “abc” adalah?
Mungkin soal soal itu mau dicoba dirumuskan sendiri masalahnya, kalau udh selesai (atau nyerah) berikut ini pembahasannya.

Nomor 1

permasalahannya sama aja apabila dia punya gelas ukuran 2 dan 5 ml, trus targetnya 20 ml. misalkan F(n) = banyaknya cara minum dengan target n ml. misalkan untuk target n liter, gelas terakhir yg kita minum itu 2 ml, maka banyaknya cara sisa adalah F(n-2). Sama halnya apabila gelas terakhir yang kita minum itu 5 ml, maka banyaknya cara sisa adalah F(n-5). 

Jadi permasalahan bisa dirumuskan F(n) = F(n-2) + F(n-5).
contoh: misal F(diketaui F(4) = 1, F(7) =2)
F(4) = 200-200
F(7) = 200-500    500-200 

mau nyari F(9), bisa tempel 500 di semua solusi F(4) -> 200-200-500 bisa temple 200 di semua solusi F(7) -> 200-500-200 500-200-200
Jadi F(9) = F(4) + F(7)

Nomor 2

misalkan F(n) -> banyaknya himpunan bagian dari 1..n yang tidak memiliki elemen berurutan. Untuk nyari F(n) ada 2 kemungkinan, himpunan dimana N termasuk, dan himpunan dimana N tidak termasuk. Kita coba tulis F(3) dan F(4), siapa tau F(5) ketemu

F(3) = {1} , {2}, {3}, {1,3}
F(4) = {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}
F(5) = {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, {1,5}, {2,5}, {3,5}, {1,3,5}, {5}

Melihat sesuatu? Ternyata semua solusi dari F(4) termasuk dalam solusi F(5) yaitu, semua himpunan bagian yang tidak mengandung 5 adalah F(4). 

Sedangkan yang mengandung 5, kita bisa menempel semua solusi dari F(3) dengan 5, lalu karena himpunan kosong gaboleh, maka ada himpunan tersendiri {5} yang tidak terhitung. Maka dapat dikatakan F(n) = F(n-1) + F(n-2) + 1

Nomor 3

misalkan F(n) -> banyaknya kotak yang terdapat pada gambar ke N. observasi pertama adalah jelas kelihatan bahwa F(n+1) menggunakan F(n) sebagai sisi sisinya, yang masing masing kehilangan salah satu sisi, dan memiliki persegi tambahan ditengah. Maka dengan asumsi bahwa tidak ada sisi yang hilang, F(n+1) = 4F(n) + 1. Sekarang kita harus mengurangi sisi sisi yang hilang. Apabila keempat sisi sisi hilang tersebut kita satukan…
Woww.. ternyata apabila sisi sisi hilang tersebut kita satukan, berubah menjadi F(n) tanpa persegi tengah. Jadi yang kita kurangi adalah F(n) – 1 jadi rumus terakhir F(n+1) = 4F(n) + 1 – (F(n) – 1) = 3F(n) + 2

Nomor 4

karena sudah 2 dimensi, fungsinya F(r,c) -> nilai maksimum yang bisa diperoleh apabila berada pada kotak (r,c). nanti jawabannya maksimum dari F(1,C),F(2,C), … F(R,C)
Kerena kita hanya bisa kekotak (r,c) dari kotak (r,c-1), (r+1,c-1), (r-1,c-1). 

Selalu optimal kita ambil  mana petak maksimal lalu tambahkan nilai petak (r,c). nilai maksimal yang bisa didapat dari (r,c-1) itu kan F(r,c-1). maka kita bisa merumuskan F(r,c) = max(F(r,c-1) , F(r+1,c-1) , F(r-1,c-1)) + petak[r][c]. dimana petak[r][c] adalah nilai petak r,c .

Nomor 5

misalkan F(n) -> banyaknya string dengan panjang n yang memenuhi criteria tersebut. Kita coba bagi kasus tentang penempatan huruf depan

A ____  banyak cara: F(n-1) B ____ banyak cara: F(n-1) C_____ banyak cara: F(n-1)
Jadi total banyaknya cara = 3F(n-1). Eh tapi tunggu dulu. Kan ada aja string yang depannya BC, trus karena ditempeli A jadi string invalid. Jadi kita kurangi kasus ABC__  banyak cara: F(n-3)

Jadi total banyaknya cara adalah 3F(n-1) – F(n-3).

Dengan demikian diharapkan kalian udh ngerti caranya konstruksi rumusan rekursi, bagian ngitungnya boleh dicoba sebagai latihan (inget, bawah keatas). Sebelum lanjut, diharapkan udh bener bener ngerti konstruksi DP, coba coba cari soal OSP atau OSK yang kira kira bisa dikerjakan dengan rekursi (soal soal OSP/K terbaru banyak kok) karena bagian selanjutnya akan membuat sangat bingung apabila tidak K

Tidak harus satu parameter

Lihat soal berikut:
“banyaknya string biner dengan panjang 6, dimana tidak mengandung string 101 adalah”
mungkin kepikiran cara seperti mirip dengan nomor 5 tadi

Logikanya sama seperti soal nomor 5 tadi. F(N) -> banyaknya string dengan panjang N yang tidak mengandung 101. Bagi kasus, depannya 1 atau 0 1__ (F(n-1)) 0__ (F(n-1)) total 2F(n-1). String dengan depan 01 akan menjadi invalid, maka kurangi 101__F(n-3) jadi banyaknya cara adalah 2F(n-1) – F(n-3).

 Dengan kuli F(1) =2, F(2)=4, F(3) = 7. Maka kita hitung, F(4) = 14 – 2 = 12 F(5) = 24-4 = 20

 Hmm, ada yg aneh, kita coba daftarkan semua kemungkinan F(5) 00000 00001 00010 00011 00100 00110 00111 01000 01001 01100 01110 01111 10000 10001 10010 10011 11000 11001 11100 11110 11111 Ada 21 (source: https://ideone.com/n5yzu7)

 Loh? coba Daftarkan F(4), dan F(2)

 F(4): (https://ideone.com/5zEpkE)
0000 0001 0010 0011 0100 0110 0111 1000 1001 1100 1110 1111

 F(2): (inimah gak usah pake program) 00 01 10 11 Apabila kita gabungin 0 ke semua F(4) untuk mencari F(5), didapat string string00000 00001 00010 00011 00100 00110 00111 01000 01001 01100 01110 01111 (tidak ada masalah) Lalu coba gabungkan 1 ke semua F(4)10000 10001 10010 10011 10100 10110 10111 11000 11001 11100 11110 11111

Biru = tidak valid. Lalu katanya kita kurangin 101 ditempelin F(2), jadi kita ngurangin dari jawaban awal:10100 10101 10110 10111 Ketiga string tersebut sukses kita kurangi dari jawaban, tetapi ternyata kita ngurangin string ekstra dari jawaban. 10101 tidak termasuk dalam penempelan 0 dan 1 ke F(4), tapi kira kurangi dari penempelan 101 ke F(2). Jadi kita mengurangi ekstra, maka cara ini tidak bisa dipakai.

Eh tapi kok yg ABC itu bisa dipakai? dicoba dipikir, diatas udh dibilang kok. berikut penjelasannya

Kita coba daftarkan F(3), F(2) (karena jumlah string buanyak untuk F(5)

 F(4) : AAAA AAAB AAAC AABA AABB AACA AACB AACC ABAA ABAB ABAC ABBA ABBB ABBC ACAA ACAB ACAC ACBA ACBB ACBC ACCA ACCB ACCC BAAA BAAB BAAC BABA BABB BACA BACB BACC BBAA BBAB BBAC BBBA BBBB BBBC BBCA BBCB BBCC BCAA BCAB BCAC BCBA BCBB BCBC BCCA BCCB BCCC CAAA CAAB CAAC CABA CABB CACA CACB CACC CBAA CBAB CBAC CBBA CBBB CBBC CBCA CBCB CBCC CCAA CCAB CCAC CCBA CCBB CCBC CCCA CCCB CCCC

 F(2) : AA AB AC BA BB BC CA CB CC

 F(1) : A B C

 Untuk mendapatkan F(5), kita akan pertama tempelkan A,B,C ke F(4)
 AAAAA AAAAB AAAAC AAABA AAABB AAACA AAACB AAACC AABAA AABAB AABAC AABBA AABBB AABBC AACAA AACAB AACAC AACBA AACBB AACBC AACCA AACCB AACCC ABAAA ABAAB ABAAC ABABA ABABB ABACA ABACB ABACC ABBAA ABBAB ABBAC ABBBA ABBBB ABBBC ABBCA ABBCB ABBCC ABCAA ABCAB ABCAC ABCBA ABCBB ABCBC ABCCA ABCCB ABCCC ACAAA ACAAB ACAAC ACABA ACABB ACACA ACACB ACACC ACBAA ACBAB ACBAC ACBBA ACBBB ACBBC ACBCA ACBCB ACBCC ACCAA ACCAB ACCAC ACCBA ACCBB ACCBC ACCCA ACCCB ACCCC BAAAA BAAAB BAAAC BAABA BAABB BAACA BAACB BAACC BABAA BABAB BABAC BABBA BABBB BABBC BACAA BACAB BACAC BACBA BACBB BACBC BACCA BACCB BACCC BBAAA BBAAB BBAAC BBABA BBABB BBACA BBACB BBACC BBBAA BBBAB BBBAC BBBBA BBBBB BBBBC BBBCA BBBCB BBBCC BBCAA BBCAB BBCAC BBCBA BBCBB BBCBC BBCCA BBCCB BBCCC BCAAA BCAAB BCAAC BCABA BCABB BCACA BCACB BCACC BCBAA BCBAB BCBAC BCBBA BCBBB BCBBC BCBCA BCBCB BCBCC BCCAA BCCAB BCCAC BCCBA BCCBB BCCBC BCCCA BCCCB BCCCC CAAAA CAAAB CAAAC CAABA CAABB CAACA CAACB CAACC CABAA CABAB CABAC CABBA CABBB CABBC CACAA CACAB CACAC CACBA CACBB CACBC CACCA CACCB CACCC CBAAA CBAAB CBAAC CBABA CBABB CBACA CBACB CBACC CBBAA CBBAB CBBAC CBBBA CBBBB CBBBC CBBCA CBBCB CBBCC CBCAA CBCAB CBCAC CBCBA CBCBB CBCBC CBCCA CBCCB CBCCC CCAAA CCAAB CCAAC CCABA CCABB CCACA CCACB CCACC CCBAA CCBAB CCBAC CCBBA CCBBB CCBBC CCBCA CCBCB CCBCC CCCAA CCCAB CCCAC CCCBA CCCBB CCCBC CCCCA CCCCB CCCCC

Biru = harus dihilangkan.Sekarang kita coba list F(2) yang ditempeli A,B,C secara berturut turut ABCAA ABCAB ABCAC ABCBA ABCBB ABCBC ABCCA ABCCB ABCCC

Perhatikan kesembilan string tersebut cocok dengan string string yang harus dihilangkan. dengan observasi lanjut, maka dapat dilihat bahwa mengurangi dengan F(n-3) tidak akan mengurangi ekstra.  Kapan suatu pengurangan dikatakan mengurangi ekstra… diserahkan sebagai latihan.
 
jadi rekursi gk bisa, balik kuli dong? Memang benar, rumusan rekursi 1 parameter tidak dapat digunakan untuk merumuskan masalah tersebut. Bagi yang belum tau, inilah contoh parameter: "F(N) -> satu parameter (N), untuk hal hal seperti string, susunan.

F(x,y) -> dua parameter (x dan y), untuk grid." Apakah soal soal yang menanyakan string, susunan hanya boleh dirumuskan dengan 1 parameter? Tidak. Misalkan F(x,last) -> banyaknya string yang memenuhi criteria tersebut, dengan digit terakhir adalah last. Maka jawabannya adalah F(6,0) + F(6,1).

Kita rumuskan. F(x,0) = F(x-1,0) + F(x-1,1). Menaruh 0 didepan, maka tidak perlu banyak mikir Apabila menaruh 1 didepan, ada 2 kemungkinan, diikuti 1, atau diikuti 0

1 1 __ . perhatikan bahwa apabila diikuti 1, maka kita menambahkan F(x-1,1)

1 0 0 __. Apabila diikuti 0, maka digit berikutnya haruslah 0, maka menambahkan F(x-2,0)

F(x,1) = F(x-1,1) + F(x-2,0) Kalau udh 2 dimensi gini, kita ngisinya tabel. Kalau dikuli F(1,0) =1,

F(1,1) = 1, F(2,0) = 2, F(2,1) =2 Ingat kita kuli biar saat masukin rumus semua nilai x >0. Tabel awal:
x\last
0
1
1
1
1
2
2
2
3
4
5
6

Catatan: SANGAT DISARANKAN mencoba mengisi tabelnya sendiri dulu, agar mengerti caranya ngisi tabel bottom up

Tabel terisi:
x\last
0
1
1
1
1
2
2
2
3
4
3
4
7
5
5
12
9
6
21
16
Jadi jawabannya 21 + 16 = 37. Kalau mau ngisi F(x,0) tinggal jumlahin angka yang ada di baris sebelumnya, nyari F(x,1) tinggal jumlahin angka angka F(x-1,1) dan F(x-2,0) (yang sudah terisi sebelumnya) (btw tadi kan kita udh tau bahwa apabila panjang string = 5, maka jawabannya 21, dan dapat diliat F(5,1) + F(5,0) =21)

Contoh lain
Pak Dengklek memiliki 6 buah pot bunga yang disusun berjajar dan siap ditanami 3 (tiga) jenis bunga yaitu melati, mawar, dan anggrek di pekarangan rumahnya. Ada berapa banyak cara pengisian 6 pot bunga tersebut sehingga pada 3 buah pot yang bersebelahan yang manapun, tidak ada 3 jenis bunga yang ketiganya berbeda?” (OSP 2016)
Solusi

Seperti biasa, jenis bunga kita nomor 1,2,3. Dengan mencoba merumuskan 1 parameter, akan disadari bakal gagal seperti soal pertama tadi. Tapi untungnya menggunakan 2 parameter, merumuskan masalah ini tidak sulit. Misal F(n,last) -> banyaknya cara untuk n buah pot, dengan DUA pot terakhir adalah last (untuk 1 pot terakhir, silahkan dicoba dicari, aku sih ngerasa ngerumusin untuk dua pot terakhir lebih mudah :).

Disini maksud 12 artinya bunga terakhir dan kedua terakhir itu 1 dan 2 beruturut turut). Maka jawabannya F(6,11) + F(6,12) + F(6,13) + F(6,21) + F(6,22) + F(6,23) + F(6,31) + F(6,32) + F(6,33). Tinggal dirumuskan saja (cara merumuskan diserahkan sebagai latihan)

F(n,11) = F(n-1,11) + F(n-1,12) + F(n-1,13)

F(n,12) = F(n-1,21) + F(n-1,22)

F(n,13) = F(n-1,31) + F(n-1,33)

F(n,21) = F(n-1,11) + F(n-1,12)

F(n,22) = F(n-1,21) + F(n-1,22) + F(n-1,23)

F(n,23) = F(n-1,32) + F(n-1,33)

F(n,31) = F(n-1,13) + F(n-1,33)

F(n,32) = F(n-1,22) + F(n-1,23)

F(n,33) = F(n-1,31) + F(n-1,32) + F(n-1,33)

Kasus dasarnya F(2,berapapun) = 1 Buat deh tabelnya Langsung aja diisi ya, kalau mau ngisi sendiri tutupin dulu :v
n\last
11
12
13
21
22
23
31
32
33
2
1
1
1
1
1
1
1
1
1
3
3
2
2
2
3
2
2
2
3
4
7
5
5
5
7
5
5
5
7
5
17
12
12
12
17
12
12
12
17
6
41
29
29
29
41
29
29
29
41
Jawabannya baris terbawah tinggal dijumlahin aja, jadi dapet jawabannya 3x41 + 6x29 = 297.

Ngisi tabelnya berat? Sebenernya saat ngisi kalau jeli bisa dapet suatu observasi yaitu tiap baris cuman perlu ngitung 2 cell doang. Hal ini karena adanya simetrisme dari jawabannya, contoh F(3,31) = F(3,32)=F(3,12) = F(3,13) = F(3,21) = F(3,23). Jadi kita hanya perlu nyari F(3,31), sisanya akan ketemu untuk baris tersebut.

 Oiya dengan memanfaatkan simetrisme tersebut, sebenernya kita merumuskan rekursinya dengan cara lain (untuk menghemat tempat tabel). Jadi F(n,last) -> last = XX (2 angka terakhir sama), atau XY (2 angka terakhir berbeda).

Jadi tabelnya cuman 5x2 = 10. Coba sebagai latihan dirumuskan.

Awalnya mungkin bakal sedikit bingung, tetapi nanti bakal sadar kalau kadang walau rekursi 1 parameter udh cukup, ngerumusin dalam dua parameter jauh lebih mudah (karena 1 parameter perlu manipulasi dan kreatifitas). Terkadang juga dengan merumuskan dalam dua parameter, rumus 1 parameter dapat ditentukan.

Contohnya: 1. sebuah grid berukuran 1x10 akan diwarnai dengan pilihan 3 buah warna, dimana petak yang bersebelahan (memiliki sebuah sisi yang sama) tidak boleh berwarna sama. Maka maksimal banyaknya pewarnaan adalah? (PCS 2017)
Solusi

Kita misalkan ada 2 fungsi. F(n) -> banyaknya cara mewarnai dengan petak 1xn. Dan f(n,last) -> banyaknya cara mewarnai petak 1xn, dengan petak ke n berwarna last. Jadi kita kodekan saja warnanya, misal warna warna tersebut adalah 1,2,3.

beberapa rekurens dapat dengan mudah dirumuskan:
 F(n) = f(n,1) + f(n,2) + f(n,3)
f(n+1,1) = f(n,2) + f(n,3) //apabila petak ke n+1 berwarna 1, maka petak sebelumnya hanya boleh berwarna 2 atau 3

f(n+1,2) = f(n,1) + f(n,3) f(n+1,3) = f(n,1) + f(n,2)

maka dengan substitusi
 F(n+1) = f(n+1,1) + f(n+1,2) + f(n+1,3)          
             = f(n,2) + f(n,3) + f(n,1) + f(n,3) + f(n,1) + f(n,2)          
             = 2(f(n,1) + f(n,2) + f(n,3))          
             = 2F(n) Maka F(n)
             = 2F(n-1)
 dengan F(1) = 3

 F(2) = 6

 F(3) = 12

 …
karena bentuk rekursinya, maka dapat dibuat rumus tertutup yaitu F(n) = 3 x 2^(n-1). Maka F(10) = 3 x 512 = 1536.

2. kalau banyaknya cara yang diminta itu dalam petak 2x5?
Solusi

Sama aja, misal F(n) -> banyaknya cara, dalam petak 2xn. Dan f(n,last) -> banyaknya cara dalam petak 2xn, dimana baris terakhir itu diwarnai dengan cara last.

Rekurens rekurens:

F(n) = f(n,12) + f(n,13) + f(n,21) + f(n,23) + f(n,31) + f(n,32) …pers 1

f(n,12) = f(n-1,21) + f(n-1,23) + f(n-1,31) … pers 2

f(n,13) = f(n-1,21) + f(n-1,31) + f(n-1,32) … pers 3

f(n,21) = f(n-1,12) + f(n-1,13) + f(n-1,32) … pers 4

f(n,23) = f(n-1,12) + f(n-1,31) + f(n-1,32) … pers 4

f(n,31) = f(n-1,12) + f(n-1,13) + f(n-1,23) … pers 5

f(n,32) = f(n-1,13) + f(n-1,21) + f(n-1,23) … pers 6

substitusi persamaan 2-6 ke pers 1.

Diperoleh F(n) = 3(f(n-1,12) + f(n-1,13) + f(n-1,21) + f(n-1,23) + f(n-1,31) + f(n-1,32))
                         = 3F(n-1)

 Jadi sebenernya F(n) = 3F(n-1) (dengan F(1) = 6) Jadi bisa dibuat rumus tertutup yaitu F(n) = 6.3^(n-1) . Maka F(5) = 6 x 81 = 486.

3. Suatu hari di negara Rusai, seorang pemiliki toko ingin mendekorasi atapnya dengan dekorasi N garis berwarna warni, dari warna putih, biru dan merah. Terdapat aturan berikut : -Warna yang bersebelahan tidak boleh sama -Warna biru hanya boleh diletakkan diantara warna merah dan putih Sebagai contoh untuk N=3, terdapat 4 kemungkinan.
 Jika N=8, berapa kemungkinan, berapa banyak dekorasi yang dapat dibuat? (soal kak Mamat)
Solusi

Seperti biasa, F(n) -> banyaknya kemungkinan untuk n garis. dan f(n,last) -> banyaknya kemungkinan untuk n garis, dimana warna terakhirnya last (M=merah, P=putih, tidak mungkin warna terakhir biru).

rekurens yang mudah dirumuskan: F(n) = f(n,M) + f(n,P)

mencari f(n,M), perhatikan bahwa hanya ada 2 kemungkinan untuk posisi n-1. yaitu warna putih dengan banyaknya cara f(n-1,P) atau biru dengan banyaknya cara f(n-2,P) (karena warna ke n-2 haruslah putih).

jadi f(n,M) = f(n-1,P) + f(n-2,P)
maka f(n,P) = f(n-1,M) + f(n-2,M)

substitusi ke persamaan awal
 F(n) = (f(n-1,P) + f(n-1,M)) + (f(n-2,P) + f(n-2,M))
        = F(n-1) + F(n-2)

kuli
F(1) = 2  (M,P).
F(2) = 2 (MP,PM).

maka F(8) dapat dicari.
F(3) = 4
F(4) = 6
F(5) = 10
F(6) = 16
F(7) = 26
F(8) = 42

jadi kalau 2 parameter, ngisinya pake tabel. Kalau 3 parameter apakah ngisinya di balok?.

Bisa diakali dengan membuat lapisan lapisan baloknya, dengan kata lain misal ada F(a,b,c). maka buat C buah tabel ukuran axb.

Tapi soal yang memerlukan 3 parameter setahuku tidak pernah muncul jadi usah dibahas secara mendalam. Setidaknya kalau terpaksa pakai 3 parameter, taulah caranya.

Untuk soal latihan, bisa coba kerjain OSP tahun tahun sebelumnya. Kalau sudah ngerti sampai bagian ini, rasanya semua soal tipe ini sudah bisa dijawab :).

 Catatan tambahan: kalau sudah masuk ke programming, ada tipe soal yang harus dikerjakan menggunakan teknik ini, namanya soal DP. Kalau disana, sangat jarang sekali parameternya cuman 1. Yang 1 parameter itu biasanya soal super mudah atau optimisasi. Jadi kalau sudah programming ya harus biasa pake 2 parameter.

Jangan maksa memakai rekursi


tadi menganjurkan rekursi, sekarang kok bilang jangan pake rekursi?. Maksudnya apabila kelihatannya pake rekursi juga bakal ngitung berat, mungkin coba cari alternative lain seperti kombin, greedy, dll. Beberapa contoh soal

1. Pak dengklek ingin menukar uang 98 dolar dengan uang pecahan 1,5,10 dolar. Maka banyaknya pecahan minimum yang diperlukan?

2. sebuah kontraktor ingin membangun jembatan dengan panjang 1802 m. apabila hanya tersedia kayu berukuran 53 m dan 17 m, maka banyaknya cara membuat jembatan tersebut adalah? 53-53-17 dianggap berbeda dengan 17-53-53

3. Terdapat 5 orang petualang dan mereka semua lapar. Di tengah perjalanan mereka memutuskan untuk makan siang di TOKI Fried Kitchen. Berikut adalah menu yang ditawarkan TOKI Fried Kitchen dengan harga dalam ribuan rupiah.
Nasi 4
Burger 5
Paket Lauk 2
Es Cendol 1
 Secara kolektif mereka semua hanya memiliki 30 ribu rupiah untuk makan siang. Jika setiap orang harus memesan makanan dengan criteria berikut: - Memesan nasi dan paket lauk, atau burger - Dapat memesan es cendol, maksimal 1 per orang. Apabila semua uang tidak harus dibelanjakan, maka banyaknya cara mereka makan adalah? (OSK 2015)


Nomor 1

solusi rekursi: misal F(n) -> minimum uang yang diperlukan untuk menukar n dolar.

Maka F(n) dapat dirumuskan F(n) = min(F(n-1),F(n-5),F(n-10)) + 1.

Dengan F(1)=F(5)=F(10)=1. Setelah dicoba buat… harus cari 98 baris ._.

Ternyata solusi ini bisa dikerjakan secara greedy (rakus).

Ambil sebanyak banyaknya koin 10, (ada 9). Maka uang sisa 8. Ambil sebanyaknya koin 5 (uang sisa 4). Sisanya ditukar dengan uang 1. Total banyaknya cara 9+1+4 = 14


Nomor 2

mungkin mau nyoba F(n) -> banyaknya cara dengan target n meter? F(n) = F(n-53) + F(n-17).

Alasanya hampir sama dengan soal diatas,bedanya disini tabelnya mengerikan untuk dibuat. Jadi kita coba cari cara menghitung langsung, pertama coba cari nilai nilai x,y yang memenuhi 53x+17y = 901.

Ternyata nilai (x,y) yang memenuhi hanya (17,0) dan (0,53). Jadi pilihannya hanyalah semua dengan panjang 17 m, atau semua dengan panjang 53m. banyak cara = 2.


Nomor 3

dimisalkan F(n,uang) -> banyaknya cara memakan,

dengan n orang dan TEPAT ‘uang’ uang (kenapa tidak “maksimal” ‘uang’ uang? Diserahkan sebagai latihan).

 Untuk orang ke X ada pilihan: burger, burger + cendol, nasi+paketlauk, nasi+paket lauk + cendol.

Maka rekurensnya: F(n,uang) = F(n-1,uang-5) + 2F(n-1,uang-6) + F(n-1,uang-7).

 Dengan F(1,5)=F(1,7)=1 dan F(1,6)=2. Jawabannya F(5,25) + F(5,26) + F(5,27) + F(5,28) + F(5,29) + F(5,30) (karena minimal uang yang dibutuhkan 25, untuk 5 burger)

Tinggal diisi aja tabelnya. Eh tapi perhatikan ukuran tabelnya bakal 5x30 = 150. Dan tidak ada simetrisme di soal ini. Jadi kamu bener bener ngisi 150 data berbeda. Dan buat tabelnya juga tidak mudah (30 kolom lho).

Sebenernya ini gk separah 2 soal diatas, tapi ada alternatif yang lebih baik. Dihitung pake kombin bagi kasus aja :). Kasus kasus:
 -Semua beli 5 nasi + paketlauk (1 cara)

 -4 beli nasi + paket lauk, 1 beli burger: ·
    Tidak ada yang membeli cendol (5 cara) ·
    1 orang membeli cendol : C(5,1) * 5 = 25

-3 beli nasi + paket lauk, 2 beli burger: ·
    Tidak ada yang membeli cendol (10 cara) ·
    1 orang membeli cendol: C(5,1) * 10 = 50 cara ·
    2 orang membeli cendol: C(5,2) * 10 = 100 cara

-2 beli nasi + paket lauk, 3 beli burger: ·
    Tidak ada yang membeli cendol (10 cara) ·
    1 orang membeli cendol: C(5,1) * 10 = 50 ·
    2 orang membeli cendol: C(5,2) * 10 = 100 ·
    3 orang membeli cendol: C(5,3) * 10 = 100
-1 beli nasi + paket lauk, 4 beli burger: ·
    Tidak ada yang membeli cendol (5 cara) ·
    1 orang membeli cendol: C(5,1) * 5 = 25 ·
    2 orang membeli cendol: C(5,2) * 5 = 50 ·
    3 orang membeli cendol: C(5,3) * 5 = 50 ·
    4 orang membeli cendol: C(5,4) * 5 = 25
 -beli 5 burger ·
    Tidak ada yang membeli cendol (1 cara) · 1
    orang membeli cendol: C(5,1) * 1 = 5 ·
    2 orang membeli cendol: C(5,2) * 1 = 10 ·
    3 orang membeli cendol: C(5,3) * 1 = 10 ·
    4 orang membeli cendol: C(5,4) * 1 = 5 ·
    5 orang membeli cendol: C(5,5) * 1 = 1

Kalau semua cara dijumlahin, didapat 638 cara.

Memang kelihatan banyak case, tapi casenya teratur ini jauh lebih baik dari buat tabel 5x30 :). Jadi kapan menurutku rekursi baik dipakai kalau buat tabelnya sedikit, sedikit itu berbeda beda untuk setiap orang. kalau memang intended soalnya diselesaikan pake rekursi, pasti kok dikasi nilai yang lumayan kecil (seperti n<=15). Kalau batasan gede, berarti harus cari cara lain, atau soalnya time waster :).

 masih ada beberapa teknik rekursi yang tidak dikover disini, karena kelangkaannya, tapi diharapkan dengan menguasai teknik teknik diatas, kalau teknik rekursi tersebut muncul, dapat diselesaikan. soal soal tipe rekursi modern kadang disembunyiin agar susah disadari bahwa ini adalah soal rekursi, maka semakin sering latihan soal rekursi, semakin baik. kata,

aku mohon maaf apabila ada penjelasan yang kurang jelas, atau kesalahan kata,kurang rapi atau kalau pembahasannya  ada yang salah dan semoga ini bermanfaat :) .

Comments

Post a Comment

Popular posts from this blog

Intern Semester 1: AI Engineer di GDP Labs

Intern atau magang, suatu kegiatan untuk merasakan suasana kantor. Daripada tidur-tiduran ngewibu gajelas selama sebulan, lebih baik ngoding 8 jam sehari di kantor kan?
Pertama tahu GDP Labs dari lomba BNPCHS 2017. Waktu penutupan, Pak On Lee, CEO GDP Labs, bawa seminar. Terus kan di akhir acara aku kenalan dan dikasih kartu nama :D
Aku awalnya berminat mau magang semester 2, namun temenku Rania semester 0 udah magang di GDP Labs. Aku jadinya daftar magang winter sebagai AI Engineer dan keterima :) Aku ditaro di bagian GLAIR (GDP Labs Artificial Intelligence Research).
Bagian-bagian dari blog ini: - Tentang GDP Labs - Kosa Kata Machine Learning - Onboarding (19 Desember 2018) - Minggu Pertama (26 - 28 Desember 2018) - Minggu Kedua (2 - 4 Januari 2018) - Minggu Ketiga (7 - 11 Januari 2018) - Minggu Keempat (14 - 18 Januari 2018) - Minggu Kelima (21 - 25 Januari 2018) - Minggu Keenam (28 - 31 Januari 2018)
- Penutup
Iklan Sejenak Tentang GDP Labs
GDP Labs itu bagian dari GDP Venture. GDP…

Pelatnas 3 TOKI 2018 Minggu 3: Odd Future

I keep my ideals alive, when destiny calls
Everything is like a rust escaping me
And we're livin in a darker history
Every single excuse i've ever made
I just gotta learn to throw them all away
And i think i remember all my lies
I was always living with dead eyes
And now i gotta live everyday, more alive!

Aku merasa lirik dari anime boku no hero ini sangat bisa dikaitkan dengan perasaanku dalam minggu terakhir ini.
(Lirik B.Ing biar ga full wibu: https://www.youtube.com/watch?v=WJxWIsI0DNc)

Senin, 21 Mei 2018

Minggu terakhir di pelatnas, pokoknya minggu ini aku gamau mikir banyak selain belajar. Gaada lagi ke acara random ke detos untuk beli baju (walaupun baju rumahanku cuman 2). Aku udah blokir youtube di hpku juga.

Hari ini ada pengajar baru, yaitu Kak Sergio. Aku inget dulu waktu masih kelas 11 ikut compfest terus nyapa Kak Sergio di toilet dan dia menghindar, jadi aku termotivasi untuk melakukan sesuatu yang membuat Kak Sergio notice aku :) dan sekarang aku bakal diajarin Kak Ser…

Mengikuti ICPC 2018

ah, ICPC. Singkatan dari International Collegiate Programming Contest. Perlombaan paling bergengsi untuk anak kuliahan. UI sendiri cukup aktif mengikuti perlombaan ini. Aku sebagai Maba dapat kesempatan untuk mengikuti lomba ini dan dapat keluar negeri juga. hehe. Berikut cerita ICPCku tahun ini. Selamat menikmati.

Pembentukan Tim


Di UI ada seleksi untuk pembentukan tim ICPC yang nantinya akan mewakili UI ke regional yang ke luar negeri. Seleksi ini dibuka untuk seluruh UI, kating-kating sampai maba boleh daftar, bahkan untuk non fasilkom pun boleh (Pak Denny bilang pernah ada anak FMIPA lolos :O).

Seleksi ini cukup singkat. Ada 3 kontes. 2 kontes pendek dan 1 kontes panjang.

Kontes pendek itu durasinya 2.5 jam dan ngerjain di lab. Dapet poin berdasarkan ranknya yaitu max(18-rank,2). Kontesnya di Vjudge.

Kontes panjang itu durasinya 1 minggu dan dapet poin cuma berdasarkan jumlah solve. kontesnya dari selasa - selasa depannya.

Ini aku ada kendala di laptop. Jadi laptopku saat itu (ROG…