Tower Hanoi Rekursif dan Iteratif di C dan Python

Tower Hanoi adalah puzzle dan game matematis yang biasa dijadikan soal dalam implementasi algoritma

Aku baca-baca ada sejarah/mitos/apalah yang unik dari tower hanoi. Tapi aku males nulis disini, jadi mending kalian cari sendiri aja. Serius, keren ceritanya

Game tower hanoi terdiri dari 3 batang yang akan kita sebut sebagai tower A, B dan C dan n buah cakram yang pada awalnya semuanya diletakkan di batang A. Kurang lebih diilustrasikan seperti gambar berikut

Tujuan dari game/puzzle ini adalah memindahkan semua cakram dari tower A ke tower C, gampang? Well, ada twistnya… tidak boleh meletakkan cakram yang lebih besar diatas cakram yang lebih kecil

Jadi gimana caranya tuh? Well, kita harus menggunakan tower B sebagai bantuan. Jadi misalnya solusi penyelesaian Tower Hanoi dengan 3 cakram adalah sebagai berikut

  1. Pindahkan cakram 1 dari A ke C
  2. Pindahkan cakram 2 dari A ke B
  3. Pindahkan cakram 1 dari C ke B
  4. Pindahkan cakram 3 dari A ke C
  5. Pindahkan cakram 1 dari B ke A
  6. Pindahkan cakram 2 dari B ke C
  7. Pindahkan cakram 1 dari A ke C

Jadi untuk penyelesaiannya, secara general bisa dilakukan dalam 2^{n}-1 langkah, jadi untuk 3 cakram bisa diselesaikan dalam 7 langkah.

Ada dua metode untuk menyelesaikan ini, kuambil dari laporan praktikum kating aowkwkwk 🙃, yaitu metode rekursif dan metode iteratif

UPDATE 12 May 2020, aku bikin versi interaktifnya di P5.js buat bantuin temenku… maybe bermanfaat untuk kalian

Rekursif

Untuk metode rekursif aku bikin video, becuz why not, yang dapat kalian tonton di

Untuk kodenya di C/C++

#include <stdio.h>

void hanoiRecur(int num, char src, char helper, char goal)
{
    if (num == 1)
    {
        printf("Pindahkan cakram 1 dari %c ke %c\n", src, goal);
    }
    else
    {
        // A ke B
        hanoiRecur(num - 1, src, goal, helper);
        // A ke C
        printf("Pindahkan cakram %d dari %c ke %c\n", num, src, goal);
        // B ke C
        hanoiRecur(num - 1, helper, src, goal);
    }
}

int main(int argc, char const *argv[])
{
    int nCakram;
    printf("Masukkan jumlah cakram? ");
    scanf("%d", &nCakram);

    hanoiRecur(nCakram, 'A', 'B', 'C');
    return 0;
}

Dan untuk di Python

nCakram = 10

def hanoiRecur(num, src, helper, goal):
    if num == 1:
        print("Pindahkan cakram 1 dari " + src + " ke " + goal)
    else:
        hanoiRecur(num - 1, src, goal, helper)
        print("Pindahkan cakram " + str(num) + " dari " + src + " ke " + goal)
        hanoiRecur(num - 1, helper, src, goal)

    
hanoiRecur(nCakram, 'A', 'B', 'C')

Iteratif

Untuk metode iteratifnya belum kubuatin video, dan baru dalam bahasa C aja, nanti kutambahin bahasa Python dan video kalau sudah sempat

UPDATE 12 May 2020, ada sedikit masalah, ketika jumlah cakram genap maka mereka malah dikumpulkan di tower B

#include <stdio.h>
#include <math.h>
#include <string.h>

char _hanoiHelper(int x, char src, char helper, char goal)
{
    if (x == 0)
    {
        return src;
    }
    else if (x == 1)
    {
        return helper;
    }
    else if (x == 2)
    {
        return goal;
    }
    else
    {
        printf("%d tidak antara 0 hingga 2", x);
        return -1;
    }
}

void hanoiIterate(int n, char src, char helper, char goal)
{
    int numIteration = pow(2, n) - 1;
    char str[4] = {src, helper, goal};

    for (int i = 1; i <= numIteration; i++)
    {
        int from = (i & i - 1) % 3;
        int to = ((i | i - 1) + 1) % 3;

        printf("Pindahkan piringan dari %c ke %c\n", _hanoiHelper(from, src, helper, goal), _hanoiHelper(to, src, helper, goal));
    }
}

int main()
{
    int nCakram;
    printf("Masukkan jumlah cakram? ");
    scanf("%d", &nCakram);
    hanoiIterate(nCakram, 'A', 'B', 'C');
}

Add a Comment

Your email address will not be published. Required fields are marked *