MAKALAH MENARA HANOI
Minggu, 23 November 2014
0
komentar
A. MENARA
HANOI
Menara Hanoi adalah sebuah permainan matematis atau teka-teki. Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana
saja. Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya
dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga
membentuk
kerucut.
Tujuan dari teka-teki ini adalah untuk memindahkan seluruh tumpukan ke tiang yang lain, mengikuti aturan
berikut:
·
Hanya satu
cakram yang
boleh dipindahkan dalam satu
waktu.
·
Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya
ke tiang lain, di
atas cakram
lain yang mungkin
sudah
ada
di tiang tersebut.
·
Tidak boleh meletakkan cakram di atas cakram
lain yang lebih
kecil.
B. ALGORIMA MENARA HANOI
Misalka
n adalah jumlah piringan dan n = 1,maka perpindahannya adalah dari A ke C,
apabila n=2, maka langkah perpindahannya adalah A ke B, A ke C,dan B ke C, dan
seterusnya.
Contoh Program menara Hanoi
dengan c++ :
#include<iostream>
using namespace std;
void MenaraHanoi(int
N, char asal, char bantu, char tujuan);
int main()
{
int
piringan;
cout<<
"\nPROGRAM MENARA HANOI\n";
cout<<
"--------------------\n\n";
cout<<
"Banyaknya piringan: ";
cin
>> piringan;
cout<<
endl;
MenaraHanoi(piringan,'A','B','C');
return
0;
}
void MenaraHanoi(int
N, char asal, char bantu, char tujuan)
{
if(N
== 1)
cout<<"Piringan
1 dari "<<asal<< " ke " << tujuan
<<endl;
else
{
MenaraHanoi(N-1,asal,tujuan,
bantu);
cout<<"Piringan
" << N <<" dari " << asal << " ke
" << tujuan<<endl;
MenaraHanoi(N-1,
bantu, asal, tujuan);
}
}
C. PERHITUNGAN MENARA HANOI
Menentukan Banyaknya Langkah minimum pada Kepingan Menara Hanoi adalah sebagai
berikut:
Banyak
Keping
(n)
|
Banyak Langkah
|
JUMLAH
|
||||||||||
K1
|
K2
|
K3
|
K4
|
K5
|
K6
|
K7
|
K8
|
K9
|
…
|
Kn
|
||
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
1
|
2
|
2
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
3
|
3
|
4
|
2
|
1
|
7
|
||||||||
4
|
8
|
4
|
2
|
1
|
15
|
|||||||
5
|
16
|
8
|
4
|
2
|
1
|
31
|
||||||
6
|
32
|
16
|
8
|
4
|
2
|
1
|
63
|
|||||
7
|
64
|
32
|
16
|
8
|
4
|
2
|
1
|
127
|
||||
8
|
128
|
64
|
32
|
16
|
8
|
4
|
2
|
1
|
255
|
|||
9
|
256
|
128
|
64
|
32
|
16
|
8
|
4
|
2
|
1
|
511
|
||
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
݊
|
2݊ −1
|
2݊ −2
|
2݊ −3
|
2݊ −4
|
2݊ −5
|
2݊ −6
|
2݊ −7
|
2݊ −8
|
1
|
|||
Berdasarkan table diatas dapat
dirumuskan dengan 2^n-1
PERHITUNGAN
TABEL DIATAS
·
n
adalah jumlah lempeng
·
k
adalah perhitungan tiap langkah
perhitungannya :
a.
<=>n=1
<=>rumus 2^n-1 => 2^1-1=1
b.
<=>n=2
<=>rumus 2^n-1 => 2^2-1=3
c.
<=>n=3
<=>rumus 2^n-1 => 2^3-1=7
d.
<=>n=4
<=>rumus 2^n-1 => 2^4-1=15
e.
<=>n=5
<=>rumus 2^n-1 => 2^5-1=31
f.
<=>n=6
<=>rumus 2^n-1 => 2^6-1=63
g.
<=>n=7
<=>rumus 2^n-1 => 2^7-1=127
D.
PENJABARAN
MENARA HANOI 7 LEMPENG
Berdasarkan tabel perhitungan
diatas jumlah langkah yang harus dilalui adalah 127 perpindahan, penjabarannya
seperti gambar dibawah ini :
Gambar 1
Gambar 2
gambar 3
Gambar 4
gambar 5
Sumber :
http://rusdyana.wordpress.com/2009/11/12/algoritma-menara-hanoi/Baca Selengkapnya ....
Categories:
