RekursiMenengahFase D–FE1E5

Tower of Hanoi

Tower of Hanoi memindahkan tumpukan enam cakram dari tiang A ke tiang C dengan aturan cakram besar tidak boleh di atas cakram kecil. Algoritma memecah masalah secara rekursif: pindahkan n-1 cakram ke tiang bantu, pindahkan cakram terbesar ke tujuan, lalu pindahkan n-1 cakram ke atasnya. Visualisasi menunjukkan tiga tiang dengan cakram bergerak satu per satu hingga selesai dalam 63 langkah rekursif.

Contoh kasus

Menghitung urutan langkah minimal pada teka-teki pemindahan barang atau backup data berjenjang yang harus dipindah tanpa melewati batas kapasitas.

Silabus

Tower of Hanoi memindahkan tumpukan cakram antar tiang dengan aturan cakram besar tak boleh di atas cakram kecil, diselesaikan secara rekursif.

Tujuan Belajar

·Memahami aturan pemindahan cakram besar dan kecil
·Menjelaskan pemecahan rekursif jadi tiga langkah
·Menerapkan rumus 2^n - 1 untuk menghitung langkah minimum

Cara Kerja

·Untuk memindahkan n cakram, selesaikan dalam tiga tahap
·Pindahkan n-1 cakram teratas ke tiang bantu (rekursif)
·Pindahkan cakram terbesar langsung ke tiang tujuan
·Pindahkan n-1 cakram tadi dari tiang bantu ke tiang tujuan
·Total langkah minimum selalu 2^n - 1

Prasyarat

·Rekursi

Contoh Nyata

·Teka-teki pemindahan barang bertingkat tanpa melewati batas kapasitas
·Strategi rotasi backup data berjenjang di komputer
·Latihan klasik memahami cara berpikir rekursif

Kompleksitas O(2^n) langkah untuk n cakram