. .

TUGAS & LATIHAN:  Bahasa Pemrograman JAVA Netbeans IDE Algoritma Rekursi Tower Of Hanoi 

Posted by CHRISTIANTO D,WIBOWO | D3MI-2016 STMIK BUMI GORA On Senin, Desember 12, 2016 No comments

Pernah tahu permainan anak-anak TOWER OF HANOI ? mungkin ada yang tahu, ada juga yang belum tahu, itu adalah permainan anak-anak balita yang memindahkan "donat-donat" berwarna dari satu tiang tumpukan ke tiang tumpukan lainnya tetapi tidak merubah susunan besar ke kecilnya. Permainan anak-anak ini sederhana dengan warna warni yang menarik bagi anak-anak, tetapi juga sangat baik untuk merangsang tumbuh kembang otak anak dan fungsi motorik dan logika berfikirnya.

TOWER OF 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:

  1. Hanya satu cakram yang boleh dipindahkan dalam satu waktu.
  2. 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.
  3. Tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil.

Teka-teki ini ditemukan Édouard Lucas, ahli matematika Perancis pada tahun 1883. Ada sebuah legenda tentang candi India yang berisi ruang besar dengan tiga tiang yang dikelilingi 64 cakram emas. Pendeta Brahma, melaksanakan tugas dari peramal pada 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.
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 miliar tahun.
Permainan TOWER OF HANOI sering digunakan dalam penelitian psikologis dalam hal pemecahan masalah. Selain itu, juga sering digunakan dalam pengajaran algorima rekursif bagi pelajar pemrograman. Permainan ini juga digunakan sebagai ujian ingatan oleh ahli psikolog syaraf dalam berupaya mengevaluasi amnesia.
⏏ Maka TUGAS DAN LATIHAN kali ini, adalah membuat Java Program dengan Netbeans IDE berdasarkan teori permainan diatas ; TOWER OF HANOI .
TOWER OF HANOI adalah masalah klasik yang digunakan untuk menggambarkan kekuatan rekursi. Pada ilustrasi algoritma ini, kita menggunakan Cakram/Disc sebagai ganti "donat-donat berwarna" dalam permainan anak-anak diatas. Sebuah teka-teki ( PUZZLE) yang berjalan sebagai berikut :
MAU LIHAT GAME ONLINENYA : CLICK DISINI !!!
Ada 3 tiang dan 64 disc ukuran yang berbeda. Awalnya, semua disc ditempatkan pada tiang pertama dengan disc terbesar di bagian bawah dan yang terkecil di bagian atas. Kita perlu untuk memindahkan semua disc dari tiang pertama ke tiang ketiga, dengan disc terkecil di bagian atas dan yang terbesar di bagian bawah. Kita bisa hanya diperbolehkan memindahkan satu disk pada waktu (yang seharusnya menjadi disc paling atas) dan pada setiap titik waktu, disk yang lebih besar tidak boleh ditempatkan di atas disk yang lebih kecil, yaitu semua disc pada tiang harus ditempatkan sedemikian rupa sehingga terkecil adalah di bagian atas dan terbesar di bagian bawah. Kedua tiang dapat digunakan sebagai tiang menengah untuk membantu kita dalam mentransfer disc.
Teka-teki ini dapat diselesaikan dengan menggunakan rekursi. Untuk sesaat, menganggap bahwa hanya ada dua disc (disc 1 dan 2; disc 2 menjadi yang lebih besar) pada tiang pertama. Solusi ini terdiri dari tiga langkah.
Step 1: Pindahkan disc 1 dari tiang 1 ke tiang 2.
Step 2: Pindahkan disc 2 dari tiang 1 ke tiang 3.
Step 3: Pindahkan disc 1 dari tiang 1 ke tiang 3.
............. Lihat Ilustrasi GIF animasi diatas.
Sekarang, asumsikan bahwa disc 1 tidak satu disk tapi terdiri dari beberapa disc - koleksi disc. Prosedur adalah sama dengan solusi 3 Step diatas,, tapi langkah 1 dan 3 akan menjadi koleksi langkah. Langkah 1 akan memindahkan disc n-1 (dengan asumsi bahwa ada total n disc) dari tiang-1 ke tiang-2. Untuk memindahkan disc (n -1), kita lagi mengikuti strategi yang sama dengan mempertimbangkan semua disc sebagai 1 disc ditambah satu set n-2 disc. Langkah 3 juga akan sama. Dan hal ini memberi kita solusi rekursif.
Algoritma rekursif
Solusi rekursif untuk memindahkan n disc dari tiang awal ke tiang akhir menggunakan tiang tambahan diberikan di bawah ini.
  • Kasus Dasar - Ketika n = 1
  • Pindahkan disk dari awal pole untuk mengakhiri pole
Rekursif Kasus - Ketika n> 1
  • Step 1: Pindahkan (n-1) disc dari tiang awal ke tiang tambahan.
  • Step 2: Pindahkan disc terakhir dari awal pole untuk mengakhiri tiang.
  • Step 3: Pindahkan (n-1) disc dari tiang tambahan untuk mengakhiri tiang.
Langkah 1 dan 3 adalah permintaan rekursif dari prosedur yang sama. Maka Java Program rekursif untuk teka-teki (PUZZLE) TOWER OF HANOI adalah :
//@uthor Christianto "GEMBLONG" Dharma Wibowo
package towerofhanoi;
import java.util.Scanner;
public class TowerOfHanoi {
    public void solve(int n, String start, String auxiliary, String end) {
       if (n == 1) {
           System.out.println(start + " -> " + end);
       } else {
           solve(n - 1, start, end, auxiliary);
           System.out.println(start + " -> " + end);
           solve(n - 1, auxiliary, start, end);
       }
   }
   public static void main(String[] args) {
       System.out.println("TOWER OF HANOI");
       System.out.println("--------------");
       TowerOfHanoi towersOfHanoi = new TowerOfHanoi();
       System.out.print("Masukkan Jumlah Disc : ");
       Scanner scanner = new Scanner(System.in);
       int discs = scanner.nextInt();
       towersOfHanoi.solve(discs, "A", "B", "C");
    }   
}
method solve() mengambil empat argumen:
  1. n - jumlah disc di teka-teki
  2. start,
  3. auxiliary,
  4. end - nama dari ke tiga (A, B, C) tiang yang akan digunakan untuk mencetak solusi.
Kita pertama kali memeriksa apakah jumlah tiang, n =1. Jika "YA", maka solusi kasus dasar (Ketika n = 1) akan digunakan yang digunakan memindahkan disk dari awal tiang ke tiang akhir. Jika tidak, solusi rekursif digunakan yang terdiri dari dua panggilan rekursif untuk prosedur yang sama solve(). Ketika kita perlu bergerak n-1 disc dari tiang awal sampai tiang tambahan, tiang tambahan menjadi tiang akhir dan tiang akhir menjadi tiang tambahan. Itulah sebabnya kita menulis baris kodenya seperti ini :
solve(n - 1, start, end, auxiliary)
dan bukan :
solve(n - 1, start, auxiliary, end)
Selanjutnya kita mencetak ' start -> end ' yang sesuai dengan memindahkan disk terbesar dari tiang awal di bagian bawah ke tiang akhir.
Akhirnya, kita membuat permintaan rekursif solve(). Di sini, tiang tambahan menjadi awal tiang dan tiang awal menjadi tiang tambahan (lihat gambar output diatas untuk lebih jelas ilustrasinya). Coba masukkan jumlah disc yang lebih besar dan lihat hasilnya.
Terimakasih Pada Sumber Pembelajaran ini :

  1. Menara Hanoi - https://id.wikipedia.org/wiki/Menara_Hanoi
  2. Tower of Hanoi - https://en.wikipedia.org/wiki/Tower_of_Hanoi
  3. Towers of Hanoi  - http://www.javawithus.com/programs/towers-of-hanoi
Dianjurkan sangat bagi kita untuk membaca artikel tautan sumber yang sangat bermanfaat dan lebih detail  Tower of Hanoi - https://en.wikipedia.org/wiki/Tower_of_Hanoi  disini, kita bisa lebih jelas mendapatkan penggambarannnya, karena yang ditulis dalam TUGAS dan LATIHAN ini merupakan ringkasan dari ke-3 sumber tersebut, dan mungkin ada bagian-bagian penting yang terlewat harap dimaklumi.

0 komentar:

Posting Komentar