Materi Teori Menara Hanoi ( Algoritma dan Pemrograman )

MENARA HANOI

Dasar teori sebagai berikut :

" Tokoh yang menemukan teka - teki  ini adalah Édouard Lucas, ahli matematika Perancis di tahun 1883. Ada sebuah legenda tentang candi Indian yang berisi ruang besar dengan tiga
tiang yang dikelilingi 64 cakram emas. Pendeta Brahma, melaksanakan tugas dari peramal di masa lalu, sesuai dengan aturan teka-teki ini. Menurut legenda ini, bila teka-teki ini diselesaikan, dunia akan kiamat. Tidak jelas benar apakah Lucas menemukan legenda ini atau terinspirasi olehnya.           Tapi tahukah teman - teman ??? ..... Bila legenda ini benar, dan pendeta itu bisa memindahkan satu cakram tiap detik, menggunakan pemindahan paling sedikit, maka akan memakan waktu 2⁶⁴−1 detik atau kurang lebih 584,582 milyar tahun. " 
 Menara Hanoi ini adalah sebuah permainan matematis atau teka-teki.
Pada dasarnya sebuah permainan anak kecil dimana sejumlah piringan dipindahkan dari tiang satu ke tiang lainnya dan dapat menggunakan tiang bantuan.

Caranya semua piringan di tiang A akan dipindahkan ke tiang C secara satu persatu dan piringan yang besar tidak boleh diletakkan di atas piringan yang kecil.
Untuk lebih jelasnya soal prosesnya bisa lihat gambar di bawah ini :




Untuk menyelesaikan puzzle di atas, kita dapat menggunakan teknik rekursif. Rekursif  sendiri adalah fungsi atau prosedure yang dapat memanggil dirinya sendiri.
Sehingga algoritmanya adalah :

Kalau N = 1 maka

N dipindahkan dari A ke C secara langsung

Tapi kalau N > 1 maka

pindahkan N-1 dari A ke B

pindahkan N dari A ke C

pindahkan N-1 dari B ke C

catatan :

N = banyaknya piringan



Sekarang dalam prateknya coding dengan c++ sebagai berikut :

01	#include<iostream>

02

03	using namespace std;

04

05	void MenaraHanoi(int N, char asal, char bantu, char tujuan);

06

07	int main()

08

09

{

10

11	int piringan;

12

13	cout<< "\nPROGRAM MENARA HANOI\n";

14

15	cout<< "--------------------\n\n";

16

17	cout<< "Banyaknya piringan: ";

18

19	cin >> piringan;

20

21	cout<< endl;

22

23	MenaraHanoi(piringan,'A','B','C');

24

25

return 0;

26

27

}

28

29	void MenaraHanoi(int N, char asal, char bantu, char tujuan)

30

31

{

32

33	if(N == 1)

34

35	cout<<"Piringan 1 dari "<<asal<< " ke " << tujuan <<endl;

36

37

else

38

39

{

40

41	MenaraHanoi(N-1,asal,tujuan, bantu);

42

43	cout<<"Piringan " << N <<" dari " << asal << " ke " << tujuan<<endl;

44

45	MenaraHanoi(N-1, bantu, asal, tujuan);

46

47

}

48

49

}

Maka hasil outputnya setelah kita jalankan adalah sebagai berikut :




Nah di atas adalah pengertian kecilnya dan sebagian prateknya. Untuk lebih jelasnya tentang Menara Hanoi sebagai berikut :




Tujuan dari teka-teki / permainan 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.