Tugas Struktur Data 2 Juni 2021

 Tower of Hanoi

    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:

• 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.

Ide penyelesaian Tower of Hanoi secara rekursif:

1. Pindahkan N-1 disk teratas dari source ke auxiliary menggunakan destination sebagai tempat sementara
2. Pindahkan disk terbawah dari source ke destination
3. Pindahkan seluruh disk dari auxiliary ke destination menggunakan source sebagai tempat sementara.
4. Bila N=0, pemanggilan rekursif berhenti

Berikut kode implementasi penyelesaian Tower of Hanoi.

Berikut hasil run kode tersebut.