Selamat datang, Kali ini kita akan berbagi tentang Contoh Barisan Rekursif. Silahkan dibaca baik-baik tentang Contoh Barisan Rekursif ini ya.
Rekursi adalah salah satu ide penting dalam ilmu komputer. Untuk menyelesaikan suatu masalah secara rekursif, kita harus memecah masalah tersebut menjadi beberapa submasalah yang masing-masing memiliki bentuk yang sama dengan masalah awal. Untuk melakukan hal ini, kita harus menemukan suatu cara sedemikian sehingga ketika proses diulang beberapa kali, submasalah terakhir menjadi mudah diselesaikan dan solusi dari submasalah-submasalah yang terbentuk dapat dihimpun bersama untuk membentuk solusi dari masalah aslinya.
Mungkin bagian tersulit dalam memecahkan masalah secara rekursif adalah ketika pada tahap menentukan bagaimana mengetahui solusi dari submasalah-submasalah tersebut akan memberikan solusi pada masalah asli secara keseluruhan. Andaikan kita tahu solusi dari submasalahnya, bagaimana kita menggunakan solusi tersebut untuk menyelesaikan permasalahan yang lebih luas merupakan hal yang tidak mudah. Anggapan bahwa submasalah yang sudah terselesaikan ini biasa disebut sebagai anggapan perulangan rekursif. Anggapan perulangan rekursif ini serupa dengan hipotesis induksi pada pembuktian dengan induksi matematika.
Contoh 1: Menara Hanoi
Pada tahun 1883 seorang matematikawan berkebangsaan Prancis, Édouard Lucas, menemukan suatu permainan yang disebut Menara Hanoi (La Tour D’Hanoï). Permainan ini memiliki 8 cakram kayu dengan lubang di tengahnya, yang disusun dari ukuran terkecil ke terbesar pada salah satu tiang dari total 3 tiang yang ada. Jiplakan sampul dari kotak Menara Hanoi waktu itu dapat dilihat pada gambar berikut.
Pemain dari permainan ini diminta untuk memindahkan semua cakram dari tiang satu ke tiang lainnya, dengan tidak menempatkan cakram yang lebih besar di atas cakram yang lebih kecil. Aturan dari permainan ini didasarkan pada legenda di India:
Pada tangga dari altar kuil di Benares, selama bertahun-tahun lamanya, Brahmana telah memindahkan menara 64 cakram emas dari satu tiang ke tiang lainnya; satu demi satu, dan tidak pernah sama sekali menempatkan cakram yang lebih besar di atas cakram yang lebih kecil. Ketika semua cakram tersebut sudah dipindahkan, maka Brahmana akan jatuh, dan itu merupakan akhir dari dunia.
Pada waktu itu, permainan ini menawarkan hadiah sebesar 10 ribu franc (atau sekitar 13 juta rupiah) kepada siapa saja yang dapat memindahkan 64 cakram dengan menggunakan tangan dan dengan mengikuti aturan permainan ini. Andaikan kamu memindahkan cakram-cakram tersebut dengan langkah-langkah yang seefisien mungkin, berapa langkah yang kamu butuhkan untuk memenangkan hadiah tersebut?
Pembahasan Untuk menyelesaikan permasalahan menara Hanoi di atas, sebaiknya kita perumum permasalahannya untuk n adalah banyaknya cakram yang akan dipindahkan. Untuk memindahkan semua cakram dari satu tiang ke tiang lainnya, perhatikan ilustrasi berikut.
Pada gambar (i), terdapat n cakram yang harus dipindahkan ke tiang yang lainnya. Misalkan, banyaknya langkah yang harus dilakukan untuk memindahkan n cakram tersebut kita simbolkan dengan mn. Pertama, kita harus memindahkan sejumlah n – 1 cakram teratas ke tiang lainnya, misalkan tiang C. Sehingga, banyaknya langkah yang harus kita lakukan adalah mn – 1 (gambar (ii)). Selanjutnya, kita pindah satu cakram yang tersisa ke tiang B (tiang yang masih kosong). Untuk memindahkan satu cakram tersebut, kita melakukan 1 langkah. Dan terakhir, kita pindahkan sejumlah n – 1 cakram pada tiang C ke tiang B. Proses ini membutuhkan mn – 1 langkah. Sehingga, banyaknya langkah yang diperlukan untuk memindahkan n cakram dapat dirumuskan sebagai berikut.
Untuk menentukan kondisi awalnya, kita perhatikan kembali definisi dari barisan tersebut. Karena hanya 1 langkah yang diperlukan untuk memindahkan 1 cakram dari satu tiang ke tiang lainnya, maka
Sehingga, barisan m1, m2, m3, …, dapat didefinisikan secara rekursif sebagai berikut: Untuk semua bilangan bulat n ≥ 2
Berikut ini perhitungan dari 5 suku selanjutnya.
Kembali kepada legenda India, misalkan kita memindahkan cakram-cakram tersebut dengan kecapatan 1 langkah setiap detik. Maka waktu yang diperlukan dari awal penciptaan sampai akhir dunia adalah m64 detik. Untuk menentukan m64, kita dapat menggunakan kalkulator untuk melanjutkan proses di atas. Nilai dari m64 adalah sekitar,
Dan tahukah kamu, nilai di atas, 584,5 miliar tahun, mendekati usia semesta kita yang yang diperoleh dengan menggunakan kajian ilmiah!
No comments:
Post a Comment