Teknik Rekursi untuk Menjawab Soal di Kertas

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 -… tapi, 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. Misalkan juga kita punya F(n) dan F(n-1), maka kita bisa mendapat F(n+1) sebagai berikut:

F(n) tidak mungkin memiliki 2 angka 1 yang berdampingan. Maka, jika didepan setiap kemungkinan F(n) dapat ditempeli 0 akan menjadi string dengan panjang n+1 yang pasti memenuhi syarat.

Untuk angka 1, kita tidak bisa nempel sembarangan didepan string F(n). Karena, pasti ada F(n) yang memiliki digit terdepan 1 yang memproduksi string invalid apabila ditempel 1. 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 _ _ …), 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 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 menyelsaikan soal dengan 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 kaya 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. Jawabannya adalah F(X). 

Contoh: banyaknya string biner dengan panjang n adalah? 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).

Dengan kuli youdontsay didapat 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 seperti apa.

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 udah 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 juga 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, banyaknya cara sisa adalah F(n-5).

Jadi permasalahan bisa dirumuskan F(n) = F(n-2) + F(n-5).

contoh, anggaplah sudah ditemukan F(4) = 1, F(7) =2) sebagai berikut:
F(4) = 200-200
F(7) = 200-500    500-200

Mau nyari F(9). Kita bisa nempel 500 di semua solusi F(4): 200-200-500 dan juga bisa nempel 200 di semua solusi F(7): 200-500-200 500-200-200

Jadi F(9) = F(4) + F(7) = 3

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 yaitu masing-masing kehilangan salah satu sisi ditambah ditengahnya. 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. Rumus terakhirnya: 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, tunggu dulu! Kan ada aja string yang depannya BC, trus karena ditempeli A jadi string invalid. Jadi, kita tinggal kurangi kasus ABC__. Banyaknya 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: 1__ (F(n-1))
- Depannya 0:  0__ (F(n-1))
Total cara: 2F(n-1).

Karena string dengan depan 01 akan menjadi invalid, kurangi 101__F(n-3) jadi banyaknya cara adalah 2F(n-1) – F(n-3).


Dengan kuli, didapat F(1) =2, F(2)=4, F(3) = 7. Lalu dapat dihitung:
- 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 
sumber: https://ideone.com/n5yzu7

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

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

F(2): 00 01 10 11 
(gapake program inimah)

Kita gabungin 0 ke semua F(4) untuk mencari F(5), didapat string-string:
00000 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 karena mengandung 101.

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, kita juga ngurangin string ekstra dari jawaban yaitu 10101! Yah, kita mengurangi ekstra, 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 ABC 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, dapat dilihat bahwa mengurangi dengan F(n-3) tidak akan mengurangi ekstra.  Kapan suatu pengurangan dikatakan mengurangi ekstra? diserahkan sebagai latihan.

Rekursi gabisa, balik kuli dong? Tidak!

Memang benar, rumusan rekursi 1 parameter tidak dapat digunakan untuk merumuskan masalah tersebut. Oh, buat yang bingung dengan terminologi, ini contoh parameter:
- F(N) memiliki satu parameter, N. Biasa untuk panjang string atau susunan.
- F(x,y) memiliki dua parameter, x dan y. Biasa menyatakan grid.

Apakah soal-soal yang menanyakan string atau susunan hanya boleh dirumuskan dengan 1 parameter? Tidak!

Kembali ke soal. Misalkan F(x,last): banyaknya string yang memenuhi kriteria tersebut, dengan digit terakhir adalah last. Jawabannya adalah F(6,0) + F(6,1).

Kita rumuskan:
- Menaruh nol didepan: F(x, 0) = F(x-1,0) + F(x-1,1). Ini bisa karena menaruh 0 didepan akan tetap membuat valid semua solusi.
- Menaruh satu didepan: Apabila menaruh 1 didepan, ada 2 kemungkinan: diikuti 1, atau diikuti 0:

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

Jadi, F(x,1) = F(x-1,1) + F(x-2,0).

Kalau udah 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).

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 dengan menggunakan 2 parameter, merumuskan masalah ini tidak sulit.

Misal F(n,last): banyaknya cara untuk n buah pot, dengan DUA pot terakhir adalah last. Mungkin saja ada rumus 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. Jadi, jawaban yang diminta soal adalah 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 tabel dan langsung diisi ya! kalau mau ngisi sendiri, tutupin dulu tabel dibawah :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 adalah  jumlahan dari baris terbawah. Jadi jawabannya 3x41 + 6x29 = 297.

Ngisi tabelnya berat? Kalau jeli kita bisa dapet suatu observasi yaitu tiap baris cuman perlu ngitung 2 sel 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, last hanya memiliki dua kemugnkinan yaitu XX jika 2 angka terakhir sama, atau XY jika 2 angka terakhir berbeda.

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

Awalnya mungkin bingung. Tetapi, lama-lama bakal ngerasa 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 kelihatan pola, didapat rumus tertutup 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

Mirip. 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. Didapat juga rumus tertutupnya 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, ada 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. Ket: 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)
dan  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).

Yes! 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). Buat C buah tabel ukuran a x b. Tapi, soal yang memerlukan 3 parameter setahuku tidak pernah muncul jadi tidak perlu 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 Yang 1 parameter itu biasanya soal super mudah, optimisasi, atau soal super sulit. Jadi, kalau sudah programming ya harus biasa pake 2 parameter :(

Jangan maksa memakai rekursi

Apaan? Tadi menganjurkan rekursi, sekarang kok bilang jangan pake rekursi? Maksudnya apabila kelihatannya pake rekursi juga bakal ngitung berat, mungkin coba cari alternatif lain seperti kombin, greedy, dan sebagainya. 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. 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. You mad bro?

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.

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. Jawaban dari soal ini adalah F(5,25) + F(5,26) + F(5,27) + F(5,28) + F(5,29) + F(5,30). Karena, minimal harus beli 5 burger.

Tinggal diisi aja tabelnya. Eh, tapi ukuran tabelnya bakal 5x30 = 150. Dan, tidak ada simetrisme di soal ini :(. Jadi kamu bener-bener ngisi 150 data berbeda. Buat tabelnya juga tidak mudah, 30 kolom!

Sebenernya ini ga 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 kasus. Tapi, kasusnya teratur.  Ini menurutku jauh lebih baik dari buat tabel 5x30 :).

Menurutku, rekursi baik dipakai kalau buat tabelnya sedikit. Sedikit itu berbeda-beda untuk setiap orang. Kalau memang intended soalnya diselesaikan pake rekursi, pasti bakal 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 cukup untuk menyelesaikan sebagian besar soal-soal. Zaman now, soal rekursi modern kadang disembunyiin agar susah disadari bahwa ini adalah soal rekursi. Dengan seringnya latihan soal rekursi, semakin baik!

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