• Document: Karena relasi rekurens menyatakan definisi barisan secara rekursif, maka kondisi awal merupakan langkah basis pada definisi rekursif tersebut.
  • Size: 448.34 KB
  • Uploaded: 2019-03-24 04:26:41
  • Status: Successfully converted


Some snippets from your converted document:

Relasi Rekurens 1 Relasi Rekurens  Barisan (sequence) a0, a1, a2, …, an dilambangkan dengan {an}  Elemen barisan ke-n, yaitu an, dapat ditentukan dari suatu persamaan.  Bila persamaan yang mengekspresikan an dinyatakan secara rekursif dalam satu atau lebih term elemen sebelumnya, yaitu a0, a1, a2, …, an–1, maka persamaan tersebut dinamakan relasi rekurens. Contoh: an = 2an–1 + 1 an = an–1 + 2an–2 an = 2an–1 – an–2 2  Kondisi awal (initial conditions) suatu barisan adalah satu atau lebih nilai yang diperlukan untuk memulai menghitung elemen-elemen selanjutnya. Contoh: an = 2an–1 + 1; a0 = 1 an = an–1 + 2an–2 ; a0 = 1 dan a1 = 2  Karena relasi rekurens menyatakan definisi barisan secara rekursif, maka kondisi awal merupakan langkah basis pada definisi rekursif tersebut.  Contoh 8. Barisan Fibonacci 0, 1, 1, 2, 3, 5, 8, 13, … dapat dinyatakan dengan relasi rekurens fn = fn–1 + fn–2 ; f0 = 0 dan f1 = 1  Kondisi awal secara unik menentukan elemen-elemen barisan. Kondisi awal yang berbeda akan menghasilkan elemen-elemen barisan yang berbeda pula. 3  Solusi dari sebuah relasi rekurens adalah sebuah formula yang tidak melibatkan lagi term rekursif. Formula tersebut memenuhi relasi rekurens yang dimaksud.  Contoh 9: Misalkan {an} adalah barisan yang memenuhi relasi rekurens berikut: an = 2an–1 – an–2 ; a0 = 0 dan a1 = 3 Periksa apakah an = 3n merupakan solusi relasi rekurens tersebut. Penyelesaian: 2an–1 – an–2 = 2[3(n – 1)] – 3(n – 2) = 6n – 6 – 3n + 6 = 3n = an Jadi, an = 3n merupakan solusi dari relasi rekurens tersebut. 4  Apakah an = 2n merupakan solusi relasi rekurens an = 2an–1 – an–2 ; a0 = 1 dan a1 = 2? Penyelesaian: 2an–1 – an–2 = 22n–1 – 2n–2 = 2n–1 + 1 – 2n–2 = 2n – 2n–2  2n Jadi, an = 2n bukan merupakan solusi relasi rekurens tsb. Cara lain: Karena a0 = 1 dan a1 = 2, maka dapat dihitung a2 = 2a1 – a0 = 22 – 1 = 3 Dari rumus an = 2n dapat dihitung a0 = 20 = 1, a1 = 21 = 2, dan a2 = 22 = 4 Karena 3  4, maka an = 2n bukan merupakan solusi dari relasi rekurens tsb. 5 Pemodelan dengan Relasi Rekurens 1. Bunga majemuk. Contoh 10. Misalkan uang sebanyak Rp10.000 disimpan di bank dengan sistem bunga berbunga dengan besar bunga 11% per tahun. Berapa banyak uang setelah 30 tahun? Misalkan Pn menyatakan nilai uang setalah n tahun. Nilai uang setelah n tahun sama dengan nilai uang tahun sebelumnya ditambah dengan bunga uang: Pn = Pn–1 + 0,11 Pn–1 ; P0 = 10.000 6  Solusi relasi rekurens Pn = Pn–1 + 0,11 Pn–1 ; P0 = 10.000 dapat dipecahkan sebagai berikut: Pn = Pn–1 + 0,11 Pn–1 = (1,11) Pn–1 = (1,11) [(1,11)Pn–2] = (1,11)2Pn–2 = (1,11)2 [(1,11) Pn–3] = (1,11)3Pn–3 =… = (1,11)nP0 Jadi, Pn = (1,11)n P0 = 10.000 (1,11)n Setelah 30 tahun, banyaknya uang adalah P30 = 10.000 (1,11)30 = Rp228.922,97 7 2. Menara Hanoi (The Tower of Hanoi) Contoh 11. Menara Hanoi adalah sebuah puzzle yang terkenal pada akhir abad 19. Puzzle ini ditemukan oleh matematikawan Perancis, Edouard Lucas. Dikisahkan bahwa di kota Hanoi, Vietnam, terdapat tiga buah tiang tegak setinggi 5 meter dan 64 buah piringan (disk) dari berbagai ukuran. Tiap piringan mempunyai lubang di tengahnya yang memungkinkannya untuk dimasukkan ke dalam tiang. Pada mulanya piringan tersebut tersusun pada sebuah tiang sedemikian rupa sehingga piringan yang di bawah mempunyai ukuran lebih besar daripada ukuran piringan di atasnya. Pendeta Budha memberi pertanyaan kepada murid-muridnyanya: bagaimana memindahkan seluruh piringan tersebut ke sebuah tiang yang lain; setiap kali hanya satu piringan yang boleh dipindahkan, tetapi tidak boleh ada piringan besar di atas piringan kecil. Tiang yang satu lagi dapat dipakai sebagai tempat peralihan dengan tetap memegang aturan yang telah disebutkan. Menurut legenda pendeta Budha, bila pemindahan seluruh piringan itu berhasil dilakukan, maka dunia akan kiamat! 8 9 Pemodelan: 10  Kasus untuk n = 3 piringan 11  Secara umum, untuk n piringan, penyelesaian dengan cara berpikir rekursif adalah sebagai berikut: Kita harus memindahkan piringan paling bawah terlebih dahulu ke tiang B sebagai alas bagi piringan yang lain. Untuk mencapai maksud demikian, berpikirlah secara rekursif: pindahkan n – 1 piringan teratas dari A ke C,

Recently converted files (publicly available):