Algoritma Menara Hanoi: Python, C++ Code

⚡ Ringkasan Cerdas

Algoritma Menara Hanoi adalah teka-teki rekursif klasik yang memindahkan tumpukan cakram di antara tiga pasak tanpa pernah menempatkan cakram yang lebih besar di atas cakram yang lebih kecil, yang menggambarkan prinsip bagi-dan-taklukkan dengan jelas.

🗼 Pengaturan Puzzle: Tiga pasak dan n cakram ditumpuk dengan ukuran yang semakin mengecil pada pasak sumber, menunggu untuk dipindahkan ke pasak tujuan melalui pasak pembantu.
📜 Aturan: Hanya satu cakram yang bergerak pada satu waktu, hanya cakram teratas dari setiap pasak yang dapat bergerak, dan cakram yang lebih besar tidak dapat bertumpu pada cakram yang lebih kecil.
🔁 Ide Rekursif: Pindahkan n-1 keping keping bantu, pindahkan keping terbesar ke keping tujuan, lalu pindahkan n-1 keping dari keping bantu ke keping tujuan.
️ Kompleksitas Waktu: Menyelesaikan n cakram membutuhkan 2^n – 1 gerakan, memberikan kompleksitas waktu eksponensial O(2^n) yang tumbuh sangat cepat seiring bertambahnya n.
🧠 Kompleksitas Ruang: Tumpukan rekursi dapat menampung hingga n frame sekaligus, sehingga kompleksitas ruang dari solusi rekursif adalah O(n).
️ aplikasi: Mengajarkan rekursi, skema rotasi cadangan, pergerakan data berbasis tumpukan, pengurutan robotika, dan pemahaman desain algoritma bagi-dan-taklukkan.

Baca Selengkapnya

Apa itu Menara Hanoi?

Menara Hanoi adalah teka-teki matematika yang terdiri dari tiga batang dan tumpukan cakram dengan ukuran yang semakin mengecil yang diletakkan satu di atas yang lain. Teka-teki ini juga dikenal sebagai Menara Brahma atau Menara Lucas, karena matematikawan Prancis Edouard Lucas memperkenalkannya pada tahun 1883. Teka-teki ini didasarkan pada legenda tentang memindahkan cakram emas di antara tiga batang.

Teka-teki ini memiliki tiga batang dan sejumlah cakram bertumpuk yang jumlahnya bervariasi. Batang-batang tersebut disusun sebagai menara siklik, sehingga cakram yang lebih besar ditumpuk di bagian bawah dan cakram yang lebih kecil ditumpuk di bagian atas.

Awalnya, kita diberikan tiga pasak atau batang. Salah satunya (pasak A dalam contoh) memiliki semua cakram yang ditumpuk. Tujuannya adalah untuk memindahkan seluruh tumpukan dari satu batang (A) ke batang lainnya (C) sambil mematuhi beberapa aturan tertentu.

Berikut adalah pengaturan awal teka-teki ini:

Masalah Menara Hanoi

Dan inilah tujuan akhirnya:

Aturan Menara Hanoi

Berikut adalah aturan-aturan penting untuk Menara Hanoi:

Pada tahap awal teka-teki, semua cakram ditumpuk di batang pertama.
Pada tahap akhir, semua cakram dari batang satu ditumpuk di batang dua atau batang tiga.
Hanya satu cakram yang dapat berpindah dari satu batang ke batang lainnya pada waktu tertentu.
Hanya cakram paling atas pada batang yang dapat digerakkan.
Sebuah disk tidak dapat diletakkan di atas disk yang lebih kecil.

Legenda aslinya adalah tentang memindahkan 64 keping. Para pendeta dapat memindahkan satu keping pada satu waktu sesuai aturan. Menurut legenda, ada ramalan bahwa dunia akan berakhir jika mereka dapat menyelesaikan tindakan tersebut. Pada bagian kompleksitas waktu, kita akan menunjukkan bahwa pengaturan Menara Hanoi dengan n keping membutuhkan 2^n – 1 gerakan.

Jadi, jika para pendeta membutuhkan 1 detik untuk memindahkan satu cakram, total waktu untuk memecahkan teka-teki tersebut adalah 2^64 – 1 detik, atau sekitar 584,942,417,356 tahun, 26 hari, 7 jam, dan 15 detik.

Algoritma untuk Menara Hanoi

Cara paling umum untuk menyelesaikan Menara Hanoi adalah dengan algoritma rekursif. Pertama, kita memilih dua batang sebagai sumber dan tujuan; pasak cadangan bertindak sebagai alat bantu.

Berikut langkah-langkah memecahkan teka-teki Menara Hanoi:

Pindahkan disk n-1 teratas dari pasak sumber ke pasak pembantu.
Pindahkan cakram ke-n dari pasak sumber ke pasak tujuan.
Pindahkan n-1 keping yang tersisa dari pasak bantu ke pasak tujuan.

Catatan: Jika kita hanya memiliki satu disk, kita dapat memindahkannya langsung dari sumber ke tujuan.

Bagaimana memecahkan Puzzle Menara Hanoi

Mari kita ilustrasikan algoritma untuk tiga cakram. Anggap pasak A sebagai sumber, pasak B sebagai pembantu, dan pasak C sebagai tujuan.

Langkah 1) Awalnya, semua cakram ditumpuk di pasak A.

Pada tahap 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, langkah ini mengurangi masalah 3 disk kita menjadi masalah 2 disk, yang ditangani oleh panggilan rekursif.

Langkah 2) Saat kita melakukan panggilan rekursif dari pasak A dengan pasak B sebagai tujuan, kita menggunakan pasak C sebagai pembantu.

Perhatikan bahwa kita kembali ke tahap pertama untuk masalah Menara Hanoi yang sama, tetapi sekarang untuk dua cakram. Kita memindahkan n-1 (yaitu, satu) cakram dari sumber ke pembantu, yang memindahkan cakram terkecil dari pasak A ke pasak C.

Pada tahap ini: Sumber = pasak A, Tujuan = pasak B, Pembantu = pasak C.

Langkah 3) Menurut algoritma, disk ke-n (ke-2) sekarang ditransfer ke tujuan, pasak B.

Pada tahap ini: Sumber = pasak A, Tujuan = pasak B, Pembantu = pasak C.

Langkah 4) Sekarang, kita memindahkan disk n-1 (disk satu) dari pasak bantu C ke pasak tujuan B, mengikuti tahap ketiga dari algoritma.

Pada tahap ini: Sumber = pasak A, Tujuan = pasak B, Pembantu = pasak C.

Langkah 5) Setelah menyelesaikan panggilan rekursif, kita kembali ke pengaturan sebelumnya pada tahap pertama algoritma.

Langkah 6) Pada tahap kedua, kita memindahkan disk 3 dari pasak sumber A ke pasak tujuan C.

Pada tahap ini: Sumber = pasak A, Tujuan = pasak C, Pembantu = pasak B.

Langkah 7) Tugas selanjutnya adalah memindahkan cakram yang tersisa dari penolong (pasak B) ke tujuan (pasak C). Kali ini kita akan menggunakan sumber asli (pasak A) sebagai penolong.

Langkah 8) Karena kita tidak dapat memindahkan dua disk sekaligus, kita melakukan panggilan rekursif untuk disk 1. Menurut algoritma, tujuan pada langkah ini adalah pasak A.

Pada tahap ini: Sumber = pasak B, Tujuan = pasak A, Pembantu = pasak C.

Langkah 9) Panggilan rekursif kita telah selesai. Sekarang kita memindahkan disk 2 dari sumbernya ke tujuannya.

Pada tahap ini: Sumber = pasak B, Tujuan = pasak C, Pembantu = pasak A.

Langkah 10) Kita akhiri dengan memindahkan n-1 disk yang tersisa (disk 1) dari helper ke tujuan.

Pada tahap ini: Sumber = pasak A, Tujuan = pasak C, Pembantu = pasak B.

Pseudo Code 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 menilik kembali algoritma tersebut, kita melakukan panggilan rekursif untuk (n-1) disk dua kali per panggilan. Setiap (n-1) rekursi dipecah menjadi ((n-1)-1) rekursi, dan seterusnya, hingga kita mencapai kasus dasar satu disk.

Untuk tiga cakram:

Disk 3 memanggil fungsi rekursif untuk disk 2 sebanyak dua kali.
Disk 2 memanggil fungsi rekursif untuk disk 1 sebanyak dua kali.
Disk 1 bergerak dengan waktu konstan, memberikan waktu untuk menyelesaikan teka-teki tiga disk.

Dinyatakan sebagai pengulangan:

= 2 × (Waktu untuk menyelesaikan dua cakram) + waktu konstan untuk memindahkan cakram 3

= 2 × (2 × waktu untuk menyelesaikan satu cakram + waktu konstan untuk memindahkan cakram 2) + waktu konstan untuk memindahkan cakram 3

= (2 × 2) × waktu konstan untuk memindahkan cakram 1 + 2 × waktu konstan untuk memindahkan cakram 2 + waktu konstan untuk memindahkan cakram 3

Untuk n cakram, ini menjadi:

2^n-1 × waktu konstan untuk memindahkan cakram 1 + 2^n-2 × waktu konstan untuk memindahkan cakram 2 + ….

Deret geometri ini berjumlah O(2ⁿ – 1), yang disederhanakan menjadi O (2ⁿ), kompleksitas waktu eksponensial.

2) Kompleksitas ruang:

Kompleksitas ruang Menara Hanoi adalah O(n). Rekursi menggunakan tumpukan panggilan, dan kedalaman maksimum tumpukan sama dengan n, yaitu jumlah disk. Itulah sebabnya kompleksitas ruangnya adalah O(n).

Pertanyaan Umum Demo Slot

Algoritma Menara Hanoi adalah prosedur rekursif yang memindahkan n cakram dari pasak sumber ke pasak tujuan menggunakan satu pasak pembantu, tanpa pernah menempatkan cakram yang lebih besar di atas cakram yang lebih kecil.

Jumlah langkah minimum untuk n keping adalah 2^n – 1. Tiga keping membutuhkan 7 langkah, empat keping membutuhkan 15 langkah, dan sepuluh keping membutuhkan 1,023 langkah.

Kompleksitas waktu adalah O(2^n) karena setiap penambahan disk menggandakan pekerjaan. Persamaan rekursif T(n) = 2T(n-1) + 1 menghasilkan 2^n – 1, yang merupakan kompleksitas eksponensial.

Kompleksitas ruangnya adalah O(n) karena tumpukan panggilan rekursi menyimpan satu frame untuk setiap disk yang diproses. Kedalaman rekursi maksimum mencapai n, sehingga memori tambahan yang dibutuhkan bersifat linier terhadap jumlah disk.

Ya. Solusi iteratif menggunakan perulangan dengan pola tetap: pada langkah ganjil, tukar cakram terkecil secara siklik di antara pasak, dan pada langkah genap, lakukan satu-satunya langkah yang sah selain langkah terkecil.

Algoritma ini mengajarkan rekursi, memodelkan skema rotasi cadangan untuk penyimpanan, memandu urutan lengan robot, dan muncul dalam tes neuropsikologi yang mengukur kemampuan perencanaan.

Agen pembelajaran penguatan (reinforcement learning) memecahkan teka-teki Menara Hanoi dengan memperlakukan setiap konfigurasi cakram sebagai suatu keadaan dan setiap gerakan sebagai suatu tindakan. Ini adalah tolok ukur umum untuk perencanaan dan pembelajaran kebijakan hierarkis.

Ya. GitHub Copilot, ChatGPT, dan Gemini menghasilkan solusi Menara Hanoi rekursif di Python, C++, dan JavaPengembang tetap harus memverifikasi kasus dasar dan urutan argumen.

Algoritma Menara Hanoi: Python, C++ Code

Apa itu Menara Hanoi?

Aturan Menara Hanoi

Algoritma untuk Menara Hanoi

Bagaimana memecahkan Puzzle Menara Hanoi

Pseudo Code untuk Menara Hanoi

Kode program masuk C++

Kode program masuk Python

Kompleksitas Menara Hanoi

Pertanyaan Umum Demo Slot

Ringkaslah postingan ini dengan:

Mendaftar untuk buletin

Apa itu Menara Hanoi?

Aturan Menara Hanoi

Algoritma untuk Menara Hanoi

Bagaimana memecahkan Puzzle Menara Hanoi

ARTIKEL TERKAIT

Pseudo Code untuk Menara Hanoi

Kode program masuk C++

Kode program masuk Python

Kompleksitas Menara Hanoi

Pertanyaan Umum Demo Slot

Ringkaslah postingan ini dengan:

Mendaftar untuk buletin