Struktur Data & Algoritma - Menara Hanoi

Tower of Hanoi, adalah teka-teki matematika yang terdiri dari tiga menara (pasak) dan lebih dari satu cincin seperti yang digambarkan -

Cincin ini memiliki ukuran yang berbeda dan ditumpuk dalam urutan menaik, yaitu cincin yang lebih kecil diletakkan di atas cincin yang lebih besar. Ada variasi lain dari teka-teki di mana jumlah cakram bertambah, tetapi jumlah menara tetap sama.

Aturan

Misinya adalah memindahkan semua disk ke menara lain tanpa melanggar urutan pengaturan. Beberapa aturan yang harus diikuti untuk Tower of Hanoi adalah -

  • Hanya satu disk yang dapat dipindahkan di antara menara pada waktu tertentu.
  • Hanya disk "atas" yang dapat dihapus.
  • Tidak ada disk besar yang dapat menempati disk kecil.

Berikut ini adalah representasi animasi dari memecahkan teka-teki Menara Hanoi dengan tiga disk.

Teka-teki Tower of Hanoi dengan n disk dapat diselesaikan minimal 2n−1Langkah. Presentasi ini menunjukkan bahwa puzzle dengan 3 disk telah diambil23 - 1 = 7 Langkah.

Algoritma

Untuk menulis algoritme Menara Hanoi, pertama-tama kita perlu mempelajari cara menyelesaikan masalah ini dengan jumlah disk yang lebih sedikit, misalnya → 1 atau 2. Kami menandai tiga menara dengan nama, source, destination dan aux(hanya untuk membantu memindahkan disk). Jika kita hanya memiliki satu disk, maka dengan mudah dapat dipindahkan dari sumber ke pasak tujuan.

Jika kami memiliki 2 disk -

  • Pertama, kami memindahkan disk yang lebih kecil (atas) ke peg aux.
  • Kemudian, kami memindahkan disk yang lebih besar (bawah) ke pasak tujuan.
  • Dan terakhir, kami memindahkan disk yang lebih kecil dari aux ke pasak tujuan.

Jadi sekarang, kami berada dalam posisi untuk merancang algoritme untuk Tower of Hanoi dengan lebih dari dua disk. Kami membagi tumpukan disk menjadi dua bagian. Disk terbesar (disk ke n ) ada di satu bagian dan semua disk lainnya (n-1) ada di bagian kedua.

Tujuan utama kami adalah untuk memindahkan disk ndari sumber ke tujuan dan kemudian meletakkan semua disk (n1) lainnya ke dalamnya. Kita dapat membayangkan untuk menerapkan hal yang sama secara rekursif untuk semua kumpulan disk yang diberikan.

Langkah-langkah yang harus diikuti adalah -

Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Algoritme rekursif untuk Tower of Hanoi dapat dijalankan sebagai berikut -

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Untuk memeriksa implementasi dalam pemrograman C, klik di sini .