Cara Membuat Program Menara Hanoi dengan Pemrograman C++

Menara Hanoi adalah salah satu teka-teki terkenal dalam dunia pemrograman dan matematika. Tantangannya adalah memindahkan semua cakram dari satu tiang ke tiang lainnya dengan aturan tertentu:

1. Hanya satu cakram yang dapat dipindahkan dalam satu waktu.
2. Cakram yang lebih besar tidak boleh diletakkan di atas cakram yang lebih kecil.
3. Harus menggunakan tiang perantara untuk proses pemindahan.

Teka-teki ini sering digunakan untuk memahami konsep rekursi dalam pemrograman. Pada artikel ini, kita akan membuat program untuk menyelesaikan Menara Hanoi menggunakan bahasa pemrograman C++.

1. Konsep Dasar Menara Hanoi

Aturan Permainan

• Ada tiga tiang: Asal (A), Perantara (B), dan Tujuan (C).
• Semua cakram awalnya berada di tiang Asal (A).
• Tujuan permainan adalah memindahkan semua cakram ke tiang Tujuan (C) dengan mematuhi aturan.

Strategi Rekursi

1. Pindahkan n-1 cakram dari tiang Asal ke tiang Perantara.
2. Pindahkan cakram terbesar ke tiang Tujuan.
3. Pindahkan n-1 cakram dari tiang Perantara ke tiang Tujuan.

2. Langkah-Langkah Program

Input:

• Jumlah cakram yang ingin dipindahkan.

Proses:

• Menggunakan fungsi rekursi untuk menentukan langkah-langkah pemindahan cakram.

Output:

• Menampilkan langkah-langkah pemindahan cakram.

3. Kode Program

Berikut adalah kode lengkap untuk program Menara Hanoi menggunakan rekursi di C++:

#include <iostream>
using namespace std;

// Fungsi rekursif untuk Menara Hanoi
void hanoi(int n, char asal, char tujuan, char perantara) {
    if (n == 1) {
        // Basis rekursi: hanya satu cakram
        cout << "Pindahkan cakram 1 dari " << asal << " ke " << tujuan << endl;
        return;
    }

    // Rekursi: Pindahkan n-1 cakram ke tiang perantara
    hanoi(n - 1, asal, perantara, tujuan);

    // Pindahkan cakram terakhir ke tiang tujuan
    cout << "Pindahkan cakram " << n << " dari " << asal << " ke " << tujuan << endl;

    // Pindahkan n-1 cakram dari tiang perantara ke tiang tujuan
    hanoi(n - 1, perantara, tujuan, asal);
}

int main() {
    int cakram;

    // Meminta input jumlah cakram
    cout << "Masukkan jumlah cakram: ";
    cin >> cakram;

    // Memulai proses Menara Hanoi
    cout << "Langkah-langkah pemindahan cakram:" << endl;
    hanoi(cakram, 'A', 'C', 'B'); // Tiang A = Asal, C = Tujuan, B = Perantara

    return 0;
}

4. Penjelasan Kode

1. Fungsi Rekursif hanoi:
   • Fungsi menerima empat parameter:
     • n: Jumlah cakram yang akan dipindahkan.
     • asal: Tiang asal.
     • tujuan: Tiang tujuan.
     • perantara: Tiang perantara.
   • Jika hanya ada satu cakram (n == 1), langsung pindahkan cakram tersebut.
   • Untuk lebih dari satu cakram, gunakan rekursi:
     1. Pindahkan n-1 cakram dari tiang Asal ke tiang Perantara.
     2. Pindahkan cakram terakhir dari tiang Asal ke tiang Tujuan.
     3. Pindahkan n-1 cakram dari tiang Perantara ke tiang Tujuan.
2. Fungsi main:
   • Meminta pengguna memasukkan jumlah cakram.
   • Memanggil fungsi rekursif hanoi untuk menyelesaikan teka-teki.

5. Contoh Output Program

Input:

Masukkan jumlah cakram: 3

Output:

Langkah-langkah pemindahan cakram:
Pindahkan cakram 1 dari A ke C
Pindahkan cakram 2 dari A ke B
Pindahkan cakram 1 dari C ke B
Pindahkan cakram 3 dari A ke C
Pindahkan cakram 1 dari B ke A
Pindahkan cakram 2 dari B ke C
Pindahkan cakram 1 dari A ke C

6. Kompleksitas dan Analisis

Kompleksitas Waktu

• Kompleksitas waktu untuk Menara Hanoi adalah O(2ⁿ - 1), di mana n adalah jumlah cakram.

Jumlah Langkah

• Total langkah yang dibutuhkan untuk memindahkan n cakram: Langkah=2n−1\text{Langkah} = 2^n - 1

Contoh:

• Untuk 3 cakram: 23−1=72^3 - 1 = 7 langkah.
• Untuk 4 cakram: 24−1=152^4 - 1 = 15 langkah.

7. Pengembangan Program

1. Visualisasi Proses:
   • Tambahkan fitur untuk memvisualisasikan pergerakan cakram antar tiang.
2. Validasi Input:
   • Pastikan input adalah angka positif untuk mencegah error.
3. Interaktif:
   • Tambahkan opsi bagi pengguna untuk memilih tiang awal dan tujuan.

8. Kesimpulan

Program Menara Hanoi adalah cara yang efektif untuk mempelajari rekursi dalam pemrograman. Dengan memahami logika dasar dan implementasi rekursi, kamu dapat menyelesaikan teka-teki ini untuk jumlah cakram berapa pun.