Contoh Hubungan Rekurensi: Menara Hanoi
Sebelumnya telah dijelaskan mengenai arti dari hubungan rekurensi. Juga sudah dipaparkan pola permodelan matematika relasi rekurensi Kelinci dan Bilangan Fibonacci. Berikutnya ini yaitu pola aplikasi model matematika hubungan rekurensi dengan nama Problem Menara Hanoi.
Kasus:
Jenis Puzzle ini dikenalkan oleh spesialis matematika di simpulan masa ke-19 yang berasal dari Perancis yaitu Edouard Lucas. Problem ini dikenal dengan nama Menara Hanoi. Permasalahannya menyerupai berikut,
Puzzle menara hanoi ini terdiri dari tiga tiang yang diletakkan di atas papan bersama dengan piringan yang ukurannya berbeda. Pada kondisi awal piringan ini diletakan pada tiang pertama dalam urutan menurut ukuran, dengan piringan terbesar berada paling bawah. Aturannya adalah, piringan boleh dipindahkan dari tiang satu ke tiang lainnya sepanjang piringan yang lebih besar tidak diletakkan di atas piringan yang lebih kecil. Tujuan dari puzzle ini yaitu memindahkan semua piringan dari tiang pertama ke tiang kedua dalam urutan menurut ukuran dengan syarat piringan paling besar ada di urutan paling bawah.
Misal $H_n$ dinotasikan sebagai banyaknya langkah minimal yang diharapkan untuk menuntaskan permasalahan menara hanoi dengan n piringan. Tentukanlah hubungan rekurensi untuk barisan ($H_n$)
Solusi
Penyelesaian dimulai dengan n piringan pada tiang pertama. Lalu dapat dipindahkan n-1 piringan dari yang paling atas. Berdasarkan hukum main, dilanjutkan pada tiang ketiga dengan jumlah $H_{n-1}$ langkah.
Piringan terbesar pada tiang pertama dipindahkan pada tiang ke-dua dengan 1 langkah. Selanjutnya pindahkan piringan ketiga dengan memakai $H_{n-1}$ langkah ke tiang ke dua dengan menaruh piringan di atas piringan yang lebih besar yang diletakkan sebelumnya.
Bentuk umumnya dapat dituliskan,
$H_n= 2 H_{n-1}+1$ , syarat Awal $H_1=1$ lantaran 1 piringan dapat dipindahkan dari tiang pertama ke tiang kedua dengan 1 langkah.
Penjabaran berikutnya, akan dibentuk bentuk iterasi (pengulangan) dan disederhanakan sebagai berikut,
$\begin{align*} H_n &= 2H_{n-1} + 1\\ &=2(2H_{n-2} + 1) + 1\\ &= 2^2(2H_{n-3} + 1) + 2 + 1 = 2^3H_{n-3} + 2^2 + 2 + 1\\ &\vdots\\ &=2^{n-1}H_1 + 2^{n-2} + 2^{n-3} + \ldots + 2 + 1\\ &=2^{n-1}+ 2^{n-2} + 2^{n-3} + \ldots + 2 + 1\\ &=2^n - 1 \end{align*}$
Sebagai tambahan, misalkan akan dipindahkan menara Hanoi dengan 5 piringan. Secara hitungan akan dibutuhkan
$2^n-1 = 2^5-1 =32$ gerakan. Perhatikan pembuktiannya pada ilustrasi video menara Hanoi di bawah ini,
Berikutnya:Contoh Relasi Rekurensi Codeword
Kasus:
Jenis Puzzle ini dikenalkan oleh spesialis matematika di simpulan masa ke-19 yang berasal dari Perancis yaitu Edouard Lucas. Problem ini dikenal dengan nama Menara Hanoi. Permasalahannya menyerupai berikut,
Misal $H_n$ dinotasikan sebagai banyaknya langkah minimal yang diharapkan untuk menuntaskan permasalahan menara hanoi dengan n piringan. Tentukanlah hubungan rekurensi untuk barisan ($H_n$)
Solusi
Penyelesaian dimulai dengan n piringan pada tiang pertama. Lalu dapat dipindahkan n-1 piringan dari yang paling atas. Berdasarkan hukum main, dilanjutkan pada tiang ketiga dengan jumlah $H_{n-1}$ langkah.
Piringan terbesar pada tiang pertama dipindahkan pada tiang ke-dua dengan 1 langkah. Selanjutnya pindahkan piringan ketiga dengan memakai $H_{n-1}$ langkah ke tiang ke dua dengan menaruh piringan di atas piringan yang lebih besar yang diletakkan sebelumnya.
Bentuk umumnya dapat dituliskan,
$H_n= 2 H_{n-1}+1$ , syarat Awal $H_1=1$ lantaran 1 piringan dapat dipindahkan dari tiang pertama ke tiang kedua dengan 1 langkah.
Penjabaran berikutnya, akan dibentuk bentuk iterasi (pengulangan) dan disederhanakan sebagai berikut,
$\begin{align*} H_n &= 2H_{n-1} + 1\\ &=2(2H_{n-2} + 1) + 1\\ &= 2^2(2H_{n-3} + 1) + 2 + 1 = 2^3H_{n-3} + 2^2 + 2 + 1\\ &\vdots\\ &=2^{n-1}H_1 + 2^{n-2} + 2^{n-3} + \ldots + 2 + 1\\ &=2^{n-1}+ 2^{n-2} + 2^{n-3} + \ldots + 2 + 1\\ &=2^n - 1 \end{align*}$
Sebagai tambahan, misalkan akan dipindahkan menara Hanoi dengan 5 piringan. Secara hitungan akan dibutuhkan
$2^n-1 = 2^5-1 =32$ gerakan. Perhatikan pembuktiannya pada ilustrasi video menara Hanoi di bawah ini,
Posting Komentar untuk "Contoh Hubungan Rekurensi: Menara Hanoi"