Algoritma Menara Hanoi: Python, C++ Kode
Sarah Chen
Apa itu Menara Hanoi?
Menara Hanoi adalah teka-teki matematika yang terdiri dari tiga batang dan banyak cakram yang ditempatkan satu di atas yang lain. Menara ini juga dikenal sebagai Menara Brahma atau Menara Lucas, sebagaimana diperkenalkan oleh ahli matematika Prancis Edouard Lucas pada tahun 1883. Teka-teki ini didasarkan pada legenda tentang memindahkan piringan emas di antara tiga batang.
Teka-teki ini memiliki tiga batang dan sejumlah cakram bertumpuk. Batang-batang tersebut dirancang sebagai menara siklik. Jadi, piringan yang berdiameter lebih besar ditumpuk di bagian bawah, dan piringan yang lebih kecil ditumpuk di atas.
Awalnya kita diberikan tiga buah pasak atau batang. Dan salah satunya (A, ditunjukkan pada contoh) memiliki semua disk yang ditumpuk. Kami bertujuan untuk memindahkan seluruh tumpukan disk dari satu batang (A) ke batang lainnya (C) dengan mematuhi beberapa aturan tertentu.
Berikut adalah pengaturan awal teka-teki-
Dan ini adalah tujuan akhir-
Aturan Menara Hanoi
Berikut beberapa aturan penting untuk Menara Hanoi:
- Keadaan awal teka-teki ini, semua disk akan ditumpuk di batang satu.
- Keadaan terakhir adalah semua disk dari batang satu akan ditumpuk pada batang dua atau batang tiga.
- Kita dapat memindahkan sebuah on-disk dari satu batang ke batang lainnya pada waktu tertentu.
- Kita hanya bisa memindahkan piringan paling atas dari batangnya.
- Sebuah disk tidak dapat ditempatkan di atas disk lain, yang lebih kecil.
Legenda aslinya adalah tentang memindahkan 64 cakram. Para pendeta dapat memindahkan satu cakram pada satu waktu sesuai aturan. Menurut legenda, ada ramalan bahwa dunia akan kiamat jika mereka dapat menyelesaikan aksinya. Di bagian kompleksitas waktu, kami akan menunjukkan bahwa susunan n cakram di Menara Hanoi akan menghabiskan biaya 2^n – 1 gerakan.
Jadi, apabila para pendeta membutuhkan waktu 1 detik untuk menggerakkan cakram-cakram tersebut, total waktu yang mereka perlukan untuk memecahkan teka-teki tersebut adalah 2^64 – 1 detik atau 584,942,417,356 tahun, 26 hari, 7 jam, dan 15 detik.
Algoritma untuk Menara Hanoi
Salah satu cara umum untuk menyelesaikan Menara Hanoi adalah algoritma rekursif. Pertama, kita perlu menentukan dua batang atau pasak sebagai sumber dan tujuan, dan pasak cadangan akan menjadi pembantu atau penolong.
Berikut langkah-langkah memecahkan teka-teki Menara Hanoi:
- Pindahkan disk n-1 teratas dari pasak sumber ke pasak pembantu.
- Setelah itu, pindahkan disk ke-n dari pasak sumber ke pasak tujuan.
- Terakhir, pindahkan sisa n-1 disk dari pasak pembantu ke pasak tujuan.
Note: Jika kita mempunyai satu disk, kita dapat langsung memindahkannya dari sumber ke tujuan.
Bagaimana memecahkan Puzzle Menara Hanoi
Mari kita ilustrasikan algoritma untuk tiga disk dan pertimbangkan pasak A sebagai sumber, pasak B sebagai pembantu, dan pasak C sebagai tujuan.
Langkah 1) Awalnya, semua disk akan ditumpuk di pasak A.
Di panggung ini:
Sumber = Pasak A
Tujuan = Pasak C
Pembantu = Pasak B
Sekarang, kita perlu memindahkan disk n-1 teratas dari sumber ke helper.
Catatan: Meskipun kita hanya dapat memindahkan satu disk dalam satu waktu, hal ini akan memecah masalah kita dari masalah 3 disk menjadi masalah 2 disk, yang merupakan panggilan rekursif.
Langkah 2) Saat kita memanggil panggilan rekursif dari pasak A dan tujuannya adalah pasak B, kita akan menggunakan pasak C sebagai pembantu.
Perhatikan bahwa kita berada pada tahap pertama lagi untuk masalah menara Hanoi yang sama untuk dua disk.
Sekarang kita perlu memindahkan n-1 atau satu disk dari sumber ke helper, memindahkan disk terkecil dari pasak A ke pasak C.
Di panggung ini:
Sumber = pasak A
Tujuan = pasak B
Pembantu = pasak C
Langkah 3) Kemudian, menurut algoritma kami, kebutuhan disk ke-n atau ke-2 harus ditransfer ke tujuan atau pasak B.
Di panggung ini:
Sumber = pasak A
Tujuan = pasak B
Pembantu = pasak C
Langkah 4) Sekarang, kita akan memindahkan n-1 disk atau disk satu dari helper atau pasak C ke tujuan atau pasak B sesuai dengan tahap ketiga dari algoritma kita.
Di panggung ini:
Sumber = pasak A
Tujuan = pasak B
Pembantu = pasak C
Langkah 5) Setelah menyelesaikan panggilan rekursif, kita akan kembali ke pengaturan sebelumnya saat tahap pertama algoritma.
Langkah 6) Nah pada tahap kedua kita akan memindahkan sumber kita ke tujuan kita yaitu memindahkan disk 3 ke pasak C dari pasak A.
Di panggung ini:
Sumber = pasak A
Tujuan = pasak C
Pembantu = pasak B
Langkah 7) Sekarang kita bisa melihatnya
d adalah memindahkan sisa disk dari helper (pasak B) ke tujuan (pasak C). Kita akan menggunakan sumber awal atau pasak A sebagai pembantu dalam kasus ini.
Langkah 8) Karena kita tidak dapat memindahkan dua disk secara bersamaan, kita akan memanggil panggilan rekursif untuk disk 1. Menurut langkah terakhir dan algoritma, tujuan pada langkah ini adalah pasak A.
Di panggung ini:
Sumber = pasak B
Tujuan = pasak A
Pembantu = pasak C
Langkah 9) Panggilan rekursif kami selesai sekarang. Kemudian kita pindahkan disk 2 dari sumbernya ke tujuannya.
Di panggung ini:
Sumber = pasak B
Tujuan = pasak C
Pembantu = pasak A
Langkah 10) Kemudian kita pindahkan sisa n-1 atau disk 1 dari helper ke tujuan.
Di panggung ini:
Sumber = pasak A
Tujuan = pasak C
Pembantu = pasak B
Kode Pseudo untuk Menara Hanoi
START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
IF disk == 1, THEN
move disk from source to dest
ELSE
Tower_Of_Hanoi (disk - 1, source, helper, dest)
move disk from source to dest
Tower_Of_Hanoi (disk - 1, helper, dest, source)
END IF
END Procedure
Kode program masuk C++
#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
if (num == 1) {
cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
return;
}
tower_of_hanoi(num - 1, source, helper, dest);
cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
int num;
cin >> num;
printf("The sequence of moves :\n");
tower_of_hanoi(num, "I", "III", "II");
return 0;
}
Keluaran
3 The sequence of moves : Move disk 1 from tower I to tower III Move disk 2 from tower I to tower II Move disk 1 from tower III to tower II Move disk 3 from tower I to tower III Move disk 1 from tower II to tower I Move disk 2 from tower II to tower III Move disk 1 from tower I to tower III
Kode program masuk Python
def tower_of_hanoi(n, source, destination, helper):
if n==1:
print ("Move disk 1 from peg", source," to peg", destination)
return
tower_of_hanoi(n-1, source, helper, destination)
print ("Move disk",n," from peg", source," to peg", destination)
tower_of_hanoi(n-1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')
Keluaran:
Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B
Kompleksitas Menara Hanoi
Berikut adalah Kompleksitas Waktu dan Ruang Menara Hanoi:
1) Kompleksitas waktu:
Jika kita melihat kembali algoritma kita, kita dapat melihat bahwa kita memperkenalkan panggilan rekursif untuk disk (n-1) sebanyak dua kali. Panggilan rekursif untuk disk (n-1) tersebut dapat dipecah menjadi disk lain ((n-1)-1) dan seterusnya hingga kita hanya mendapatkan satu disk untuk dipindahkan.
Untuk tiga disk-
- Disk 3 memanggil fungsi rekursif untuk disk dua dua kali.
- Disk 2 memanggil fungsi rekursif untuk disk satu dua kali.
- Disk 1 dapat bergerak dalam Waktu yang konstan, dan Waktu untuk menyelesaikan tiga disk.
= 2*(Waktu untuk menyelesaikan dua disk) + konstan Waktu untuk memindahkan disk 3
= 2*(2*waktu untuk menyelesaikan satu disk + konstan Waktu untuk memindahkan disk 2) + konstan Waktu untuk memindahkan disk 3
= (2*2) (waktu konstan untuk memindahkan disk 1) + 2*waktu konstan untuk memindahkan disk 2 + waktu konstan untuk memindahkan disk 3
Untuk n disk, dapat ditulis sebagai –
(2n-1 * waktu konstan untuk memindahkan disk 1 + 2n-2 *waktu konstan untuk memindahkan disk 2+….
Perkembangan geometri ini akan menghasilkan O(2n-1) atau O (2n), yang bersifat eksponensial.
2) Kompleksitas ruang
Kompleksitas ruang Menara Hanoi adalah 0(n). Itu karena kita perlu menyimpan urutan pelat. Saat kita menggunakan rekursi, kita menggunakan tumpukan. Dan ukuran maksimum tumpukan bisa menjadi "n." Itulah sebabnya kompleksitas ruang menjadi O(n).
