Menara Hanoi

Apa itu teka-teki Menara Hanoi?

Menara Hanoi adalah teka-teki dengan tiga tiang dan tumpukan cakram berukuran berbeda, dan tugasnya memindahkan seluruh tumpukan ke tiang lain dengan mengikuti dua aturan. Pada awalnya cakram berada di tiang pertama, yang terbesar di dasar dan yang terkecil di atas, seperti kerucut. Aturannya

1. pindahkan satu cakram sekali waktu, cakram teratas sebuah tiang; dan
2. jangan pernah menaruh cakram yang lebih besar di atas yang lebih kecil.

Tujuannya menara yang sama di tiang yang berbeda. Dengan 3 cakram diperlukan 7 langkah. Sebut tiangnya A, B, dan C, dan cakramnya 1 (terkecil), 2, dan 3, memindahkan dari A ke C:

Lihat tabelnya: cakram terbesar bergerak sekali, di tengah, dan cakram terkecil bergerak setiap dua langkah. Kedua fakta itu ternyata berlaku umum.

Posisi. Karena sebuah tiang memegang cakramnya terurut menurut ukuran, sebuah posisi sepenuhnya dijelaskan dengan menyebut tiang tempat setiap cakram berada. Pilihan apa pun sah, sehingga dengan n cakram ada tepat 3^n posisi: 27 untuk tiga cakram, 243 untuk lima.

Mainkan di bawah dengan tiga sampai tujuh cakram. Klik sebuah tiang (atau pakai tombolnya) untuk mengambil cakram teratas, lalu klik tiang tempat menaruhnya. Tombol petunjuk selalu melakukan langkah terbaik berikutnya dari posisi mana pun yang sedang kamu tempati.

Bagaimana solusi rekursif bekerja?

Untuk memindahkan n cakram dari A ke C, pindahkan dulu n-1 cakram teratas ke B, lalu pindahkan cakram terbesar ke C, lalu pindahkan n-1 cakram itu dari B ke atas C. Cakram terbesar tidak dapat bergerak sebelum semua yang di atasnya menyingkir, dan ia hanya dapat pergi ke tiang yang kosong atau berisi cakram yang lebih besar, yaitu tiang yang tidak memiliki cakram lebih kecil. Jadi semua n-1 cakram lain harus berada di tiang ketiga pada saat itu. Itulah seluruh gagasannya, dan dua kali pemindahan n-1 cakram adalah teka-teki yang sama lagi, dengan menara yang lebih kecil dan dengan tiang yang berperan berbeda:

• pindahkan n-1 cakram dari asal ke tiang cadangan, memakai tujuan sebagai cadangan;
• pindahkan cakram terbesar dari asal ke tujuan;
• pindahkan n-1 cakram dari tiang cadangan ke tujuan, memakai asal sebagai cadangan.

Rekursi berhenti pada 0 cakram, yang tidak ada yang dikerjakan. Untuk tiga cakram resep itu terurai menjadi tujuh langkah pada tabel: pindahkan 2 cakram A→ B (tiga langkah: 1 ke C, 2 ke B, 1 ke atas B), pindahkan cakram 3 ke C, pindahkan 2 cakram B→ C (tiga lagi).

Menghitung langkahnya. Misalkan T(n) banyaknya langkah solusi ini. Kedua sub-solusi masing-masing T(n-1) dan cakram terbesar satu langkah, sehingga T(0)=0, T(n)=2 T(n-1)+1. Tambahkan 1 ke kedua ruas: T(n)+1=2 (T(n-1)+1), sehingga T(n)+1 berlipat dua pada setiap langkah, dimulai dari T(0)+1=1. Jadi T(n)+1=2^n, T(n)=2^n-1. Periksa: T(1)=1, T(2)=3, T(3)=7, T(4)=15, T(5)=31, T(10)=1023. Cara lain melihatnya: cakram nomor k (yang terkecil 1) bergerak 2^n-k kali, dan 1+2+4+…+2^n-1=2^n-1 adalah deret geometri.

Apa yang dilakukan komputer. Fungsi itu memanggil dirinya dua kali, sehingga ia membuat 2^n+1-1 panggilan seluruhnya, tetapi kedalaman rekursinya hanya n: pada setiap saat tumpukan panggilan memuat satu panggilan untuk setiap ukuran dari n turun ke yang sekarang. Jadi program dapat menyelesaikan 25 cakram (33 juta langkah) tanpa kehabisan tumpukan, walau akan memakan waktu. Ini berbeda dari rekursi naif untuk bilangan Fibonacci, yang dapat diselamatkan dengan mengingat nilai: di sini jawabannya sendiri memuat 2^n-1 langkah, sehingga tidak ada program yang bisa lebih cepat daripada itu.

Mengapa tidak ada solusi yang memakai langkah lebih sedikit?

Solusi rekursif bukan sekadar baik, ia yang terbaik: tidak ada solusi yang memiliki kurang dari 2^n-1 langkah, dan tidak ada solusi lain yang memiliki tepat sebanyak itu. Buktinya memakai cakram terbesar, seperti pada konstruksinya. Misalkan M(n) banyaknya langkah paling sedikit dari solusi sah mana pun dengan n cakram.

Lihat sebuah solusi dan cakram terbesarnya. Ia harus bergerak sedikitnya sekali. Pada saat gerakan pertamanya, ia pergi dari tiang pertama ke tiang lain, dan agar itu diizinkan setiap cakram lain harus berada di tiang ketiga. Jadi sebelum saat itu n-1 cakram yang lebih kecil sudah dipindahkan dari tiang pertama ke tiang ketiga, yaitu teka-teki yang sama dengan n-1 cakram, dan memerlukan sedikitnya M(n-1) langkah. Setelah gerakan terakhir cakram terbesar ia berada di tiang tujuan, dan n-1 cakram yang lebih kecil, yang berada di tiang lain, masih harus dipindahkan ke atasnya: sedikitnya M(n-1) langkah lagi. Ditambah gerakan cakram terbesar itu sendiri, M(n)\ge2 M(n-1)+1, M(1)=1. Jadi M(n)\ge2^n-1, yang dicapai oleh solusi rekursif. Solusi terbaik memiliki tepat 2^n-1 langkah.

Ia tunggal. Jika sebuah solusi memiliki tepat 2^n-1 langkah, setiap ketaksamaan di atas harus berupa kesamaan: cakram terbesar bergerak tepat sekali (jika tidak akan ada langkah ekstra), dan langkah sebelum dan sesudahnya masing-masing adalah solusi terpendek untuk n-1 cakram. Dengan induksi pada n hanya ada satu solusi seperti itu: yang rekursif. Solusi terpendek sama sekali tidak memerlukan pilihan, yang juga menjelaskan mengapa tombol petunjuk pada teka-teki tidak pernah harus memilih di antara dua langkah terbaik.

Dari posisi mana pun. Gagasan yang sama menyelesaikan teka-teki dari posisi mana pun, bukan hanya dari menara penuh. Cari cakram terbesar yang belum berada di tempat seharusnya; pindahkan cakram yang lebih kecil ke tiang ketiga, pindahkan cakram itu, dan bangun menara sempurna di atasnya. Banyaknya langkah sesedikit mungkin, dan jarak terbesar antara dua posisi n cakram adalah 2^n-1, di antara dua dari tiga posisi "sudut" dengan semuanya di satu tiang.

Berapa lama menara 64 cakram?

Jauh lebih lama daripada keberadaan alam semesta: pada satu langkah per detik, 2^64-1 langkah memerlukan sekitar 5,85×10^11 tahun. Dalam cerita yang dituturkan selebaran Lucas pada 1883, dan diceritakan ulang majalah sains Prancis pada 1884, para biksu di sebuah kuil di Benares memindahkan 64 cakram emas di antara tiga jarum berlian, satu langkah sekali waktu, dan ketika mereka selesai dunia akan berakhir. Banyaknya langkah adalah 2^64-1=18 446 744 073 709 551 615. Pada satu langkah per detik itu 585 miliar tahun, sekitar 42 kali usia alam semesta (13,8 miliar tahun). Penggandaannya yang menyakitkan: setiap cakram tambahan melipatduakan waktunya. Pada satu langkah per detik 10 cakram memerlukan 17 menit, 20 cakram 12 hari, 30 cakram 34 tahun, dan 40 cakram 34 800 tahun. Bahkan komputer yang membuat semiliar langkah per detik memerlukan 585 tahun untuk 64 cakram.

Ini gambaran baku pertumbuhan eksponensial (lihat notasi Big-O untuk kelas pertumbuhan): menambah satu cakram mengalikan kerja dengan 2, sedangkan untuk biaya polinomial seperti n^2 ia hanya menambah sedikit. Itu juga sebabnya legenda hanyalah legenda. Geser penggeser di bawah untuk melihat waktu untuk sembarang banyak cakram, dan seberapa sering tiap cakram bergerak.

Bagaimana Menara Hanoi berhubungan dengan bilangan biner?

Cakram yang bergerak pada langkah nomor m dibaca dari bentuk biner m: ia adalah posisi bit 1 terendah. Beri nomor langkah 1,2,3,…,2^n-1 dan cakram 1 (terkecil) sampai n. Maka langkah m memindahkan cakram v+1, dengan 2^v pangkat dua terbesar yang membagi m (banyaknya nol di ujung kanan m dalam biner). Barisan cakramnya adalah barisan penggaris 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,… Langkah ganjil (m berakhir 1) memindahkan cakram 1; langkah 2,6,10,… memindahkan cakram 2; langkah 8 memindahkan cakram 4; langkah 2^n-1 memindahkan cakram terbesar n, sekali, di tengah. Banyaknya langkah tiap cakram, 2^n-k untuk cakram k, adalah banyaknya bilangan sampai 2^n-1 yang memiliki tepat k-1 nol di ujung.

Solusi tanpa rekursi. Karena itu, solusinya dapat dijalankan sebagai perulangan:

1. Pada langkah ganjil, pindahkan cakram terkecil satu tiang ke depan, selalu dengan arah yang sama mengelilingi tiga tiang: A→ C→ B→ A→… jika n ganjil, A→ B→ C→ A→… jika n genap.
2. Pada langkah genap, lakukan satu-satunya langkah sah yang tidak melibatkan cakram terkecil.

Ini membuat langkah yang persis sama dengan rekursi. Ia juga memungkinkan program menuliskan langkah nomor m menara 64 cakram dalam beberapa langkah, tanpa membuat m-1 langkah sebelumnya.

Posisi setelah m langkah. Rekursi dapat diurai sekali per cakram, dari yang terbesar ke bawah. Jika m di bawah 2^n-1 cakram terbesar belum bergerak, dan cakram yang lebih kecil sedang menuju tiang cadangan; jika tidak ia berada di tujuan, 2^n-1 dikurangkan dari m, dan cakram yang lebih kecil sedang menuju tujuan dari tiang cadangan. Hasilnya memberi tiang setiap dari n cakram setelah sembarang banyak langkah dalam n langkah, seperti yang dilakukan widget di bawah untuk sampai 64 cakram.

Kode Gray. Tulis setiap m sebagai kode Gray biner berpantulnya m⊕\lfloor m/2\rfloor (xor m dengan dirinya yang digeser ke kanan). Kode Gray berurutan berbeda tepat satu bit, dan bit yang berubah pada langkah m adalah bit nomor v, barisan penggaris yang sama. Jadi bit k kode Gray m bernilai 1 bila cakram k+1 sudah bergerak sebanyak ganjil kali sejauh ini. Frank Gray memakai kode yang sama dalam paten untuk sinyal telegraf (diajukan 1947); kode Gray dipakai pada sensor posisi, yang hanya boleh berubah satu bit sekali waktu.

Ketik nomor langkah mana pun di bawah, atau telusuri langkah-langkahnya.

Seperti apa graf semua posisi?

Gambar setiap posisi sebagai titik dan hubungkan dua titik dengan garis bila satu langkah mengubah satu posisi menjadi yang lain, dan kamu mendapatkan segitiga Sierpiński. Untuk satu cakram grafnya segitiga: cakram dapat berada di A, B, atau C, dan dapat berpindah di antara dua tiang mana pun. Untuk n cakram, bagi posisi menurut tiang cakram terbesar: tiga kelompok, masing-masing salinan graf untuk n-1 cakram (dengan cakram besar tetap, yang lebih kecil bergerak seperti sebelumnya). Ketiga salinan dihubungkan hanya oleh tiga garis, satu untuk setiap gerakan cakram terbesar, yang hanya dapat terjadi bila semua cakram yang lebih kecil berada di tiang ketiga. Mengulang ini memberi segitiga dari segitiga dari segitiga.

Graf itu memiliki sifat-sifat ini, yang dapat kamu periksa dengan mata lewat widget: - 3^n titik, semua posisi; - (3^n+1-3)/(2) garis, karena setiap posisi mengizinkan tiga langkah kecuali tiga posisi sudut, yang semua cakramnya di satu tiang dan hanya cakram teratas yang dapat bergerak, ke salah satu dari dua tiang: 39 garis untuk 3 cakram; - tiga sudut: semua cakram di A, di B, atau di C; - solusi terbaik adalah jalur di sepanjang satu sisi segitiga besar, dari sudut atas ke sudut kanan bawah, dengan 2^n-1 langkah, dan ia satu-satunya jalur terpendek di antara kedua sudut itu: banyaknya langkah tidak dapat dipersingkat karena tidak ada yang lebih pendek untuk diambil; - jarak antara dua posisi adalah panjang jalur terpendek, dan jarak terbesar dalam graf adalah 2^n-1.

Ini menjelaskan keserupaan-diri rekursi. Ia juga menghubungkan teka-teki ini dengan segitiga Sierpiński dan segitiga Pascal mod 2, sebagai pola yang sama dalam samaran berbeda. Pilih banyak cakram di bawah dan klik titik mana pun untuk melihat posisinya dan jaraknya dari menara selesai di setiap tiang.

Bagaimana jika ada empat tiang atau lebih?

Dengan tiang keempat teka-teki menjadi jauh lebih mudah, dan banyaknya langkah terbaik diberikan oleh rekurensi Frame dan Stewart yang baru terbukti optimal untuk empat tiang pada 2014. Gagasannya: pindahkan k cakram teratas ke tiang cadangan dengan memakai keempat tiang, lalu pindahkan n-k cakram sisanya ke tujuan hanya dengan tiga tiang (satu ditempati k cakram kecil), lalu pindahkan k cakram itu ke tujuan, memakai keempat tiang lagi. Jika F(n,p) adalah banyaknya langkah dengan p tiang, F(n,3)=2^n-1, F(n,p)=\min_1\le k<n\Bigl(2 F(k,p)+F(n-k,p-1)\Bigr). Untuk empat tiang ini memberi 1,3,5,9,13,17,25,33,41,49,… untuk n=1,2,3,…: selisihnya 2,2,4,4,4,8,8,8,8,…, setiap pangkat dua berulang satu kali lebih banyak daripada yang sebelumnya. Bandingkan tiga tiang: 1,3,7,15,31,…. Untuk sepuluh cakram itu 49 langkah, bukan 1023, dan untuk 20 cakram 289, bukan 1 048 575.

Penghematannya bertambah cepat. Untuk 64 cakram, empat tiang memerlukan 18 433 langkah, lima tiang 1535, dan enam tiang 673, dibandingkan 18 446 744 073 709 551 615 untuk tiga tiang: pada satu langkah per detik menara empat tiang memerlukan sekitar 5 jam, dan menara lima tiang sekitar 26 menit.

Apa yang diketahui. Henry Dudeney menerbitkan versi empat tiang, "Reve's puzzle", pada 1907. Pada 1941 J. S. Frame dan B. M. Stewart memberikan rekurensi di atas, secara terpisah. Apakah ia optimal adalah masalah terbuka lebih dari tujuh puluh tahun: Thierry Bousch membuktikannya untuk empat tiang pada 2014. Untuk lima tiang atau lebih bilangan Frame–Stewart hanya diduga terbaik (pencarian atas semua posisi memastikannya untuk kasus kecil). Pilih banyak tiang dan cakram di bawah.

Bagaimana menyelesaikan Menara Hanoi di Python, JavaScript, dan C++?

Fungsi rekursifnya lima baris di bahasa apa pun: selesaikan n-1, pindahkan cakram terbesar, selesaikan n-1 lagi, dengan peran tiang diputar. Program Python di bawah mengembalikan daftar langkah, memeriksa bahwa versi perulangan membuat langkah yang persis sama, mencari cakram langkah m dari bit set terendah, dan menghitung posisi setelah m langkah menara 64 cakram tanpa melakukannya. Program JavaScript dan C++ mengulang rekursi dan barisan penggaris.

def hanoi(n, source="A", target="C", spare="B", moves=None):
    """Moves (disc, from, to) of the best solution; disc 1 is the smallest."""
    if moves is None:
        moves = []
    if n == 0:
        return moves
    hanoi(n - 1, source, spare, target, moves)      # clear the n - 1 smaller discs onto the spare peg
    moves.append((n, source, target))               # the largest disc goes straight to its place
    hanoi(n - 1, spare, target, source, moves)      # and the smaller discs are rebuilt on top of it
    return moves


def hanoi_iterative(n):
    """The same moves without recursion: the smallest disc always goes round the pegs the same way."""
    pegs = {"A": list(range(n, 0, -1)), "B": [], "C": []}
    cycle = ["A", "C", "B"] if n % 2 else ["A", "B", "C"]
    where, moves = 0, []
    for step in range(1, 2 ** n):
        if step % 2:                                 # odd moves: the smallest disc
            src, dst = cycle[where], cycle[(where + 1) % 3]
            where = (where + 1) % 3
        else:                                        # even moves: the only legal move of the other two pegs
            a, b = [p for p in "ABC" if p != cycle[where]]
            if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
                a, b = b, a
            src, dst = a, b
        disc = pegs[src].pop()
        pegs[dst].append(disc)
        moves.append((disc, src, dst))
    return moves


def disc_at_move(m):
    """Which disc moves at move m (1, 2, 3, ...): the position of the lowest 1 bit of m."""
    return (m & -m).bit_length()


def position_after(n, m):
    """The peg of each disc after m moves, computed from the bits of m without making the moves."""
    source, target, spare = "A", "C", "B"
    where = {}
    for k in range(n, 0, -1):
        half = 2 ** (k - 1)
        if m < half:
            where[k] = source
            target, spare = spare, target
        else:
            where[k] = target
            m -= half
            source, spare = spare, source
    return where


print(hanoi(3))
print(len(hanoi(10)), hanoi_iterative(10) == hanoi(10), 2 ** 10 - 1)
print([disc_at_move(m) for m in range(1, 16)])
print(position_after(5, 15), position_after(5, 16))
print(2 ** 64 - 1, round((2 ** 64 - 1) / (365.25 * 24 * 3600) / 1e9), "billion years at one move a second")
print(position_after(64, 10 ** 18)[64], position_after(64, 10 ** 18)[1])
# [(1, 'A', 'C'), (2, 'A', 'B'), (1, 'C', 'B'), (3, 'A', 'C'), (1, 'B', 'A'), (2, 'B', 'C'), (1, 'A', 'C')]
# 1023 True 1023
# [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]
# {5: 'A', 4: 'B', 3: 'B', 2: 'B', 1: 'B'} {5: 'C', 4: 'B', 3: 'B', 2: 'B', 1: 'B'}
# 18446744073709551615 585 billion years at one move a second
# A C

const hanoi = (n, from = 'A', to = 'C', via = 'B', moves = []) => {
  if (n === 0) return moves
  hanoi(n - 1, from, via, to, moves)
  moves.push([n, from, to])
  hanoi(n - 1, via, to, from, moves)
  return moves
}
hanoi(3).map(([d, a, b]) => d + ':' + a + b).join(' ')   // '1:AC 2:AB 1:CB 3:AC 1:BA 2:BC 1:AC'
hanoi(10).length                                           // 1023

// the disc of move m is the position of the lowest set bit: m & -m keeps only that bit
const disc = (m) => Math.log2(m & -m) + 1
Array.from({ length: 15 }, (_, i) => disc(i + 1))          // [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]

2n ** 64n - 1n                                             // 18446744073709551615n: BigInt, since a double would round it
Number(2n ** 64n - 1n) / 1e9 / (365.25 * 24 * 3600)        // 584.54...: years at a billion moves a second

// the stack only holds n calls at a time, although 2^n - 1 moves are made
let count = 0
const go = (n) => { if (n === 0) return; go(n - 1); count++; go(n - 1) }
go(20)
count                                                      // 1048575

#include <iostream>
#include <cstdio>
using namespace std;

int moves = 0;
int show = 1;

void hanoi(int n, char from, char to, char via) {
  if (n == 0) return;
  hanoi(n - 1, from, via, to);
  moves++;
  if (show) printf("disc %d: %c -> %c\n", n, from, to);
  hanoi(n - 1, via, to, from);
}

int main() {
  hanoi(3, 'A', 'C', 'B');

  show = 0;
  moves = 0;
  hanoi(12, 'A', 'C', 'B');
  printf("%d\n", moves);                                // 2^12 - 1

  for (int m = 1; m <= 15; m++) {                       // the disc of move m: trailing zeros of m, plus one
    int d = 1, x = m;
    while (x % 2 == 0) {
      x = x / 2;
      d++;
    }
    printf("%d%c", d, m == 15 ? '\n' : ',');
  }
  return 0;
}

/* output:
disc 1: A -> C
disc 2: A -> B
disc 1: C -> B
disc 3: A -> C
disc 1: B -> A
disc 2: B -> C
disc 1: A -> C
4095
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
*/

Dari mana Menara Hanoi berasal?

Menara Hanoi adalah penemuan Prancis tahun 1883, terbungkus legenda yang merupakan bagian dari penemuan itu sendiri.

• 1883. Matematikawan Édouard Lucas menjual teka-teki ini sebagai La Tour d'Hanoï, véritable casse-tête annamite ("Menara Hanoi, teka-teki Vietnam sejati"), dengan delapan cakram, dengan nama rekaan N. Claus (de Siam), mandarin dari perguruan Li-Sou-Stian. Nama-nama itu anagram: N. Claus de Siam adalah Lucas d'Amiens (ia berasal dari Amiens) dan Li-Sou-Stian adalah Saint-Louis, sekolah tempatnya mengajar. Selebarannya memuat legenda kuil di Benares dan akhir dunia.
• 1884. Henri de Parville menceritakan ulang kisah itu di majalah La Nature dan membantu penyebarannya; Mathematical Recreations and Essays karya W. W. Rouse Ball membawanya ke dalam bahasa Inggris.
• 1907. Henry Dudeney menerbitkan versi empat tiang, "Reve's puzzle", dalam The Canterbury Puzzles.
• 1939–1941. Sebuah soal dalam American Mathematical Monthly tentang empat tiang membawa J. S. Frame dan B. M. Stewart pada rekurensi yang memakai nama mereka.
• 1950-an. Kode Gray Frank Gray (dipatenkan 1953) ternyata menjelaskan barisan cakramnya.
• 1970-an. Psikolog, di antaranya Herbert Simon, memakai teka-teki ini untuk mempelajari bagaimana orang merencanakan dan memecahkan masalah; versinya dipakai dalam tes kemampuan merencanakan.
• 1989–1990-an. Andreas Hinz dan lainnya mempelajari graf posisi dan hubungannya dengan segitiga Sierpiński, dan jarak rata-rata antarposisi.
• 2014. Thierry Bousch membuktikan bahwa bilangan Frame–Stewart optimal untuk empat tiang.

Kesalahan apa yang sering terjadi pada Menara Hanoi?

Kesalahan paling umum pada Menara Hanoi adalah sembilan hal berikut, masing-masing dengan pernyataan yang benar.

Latihan: uji pemahamanmu

Soal-soal ini mencampur semua yang dibahas di atas. Jika jawabanmu belum tepat, perhatikan petunjuk yang tersedia, lalu coba kembali.

Ringkasan: Menara Hanoi sekilas

• Aturan: tiga tiang, satu cakram sekali waktu, tidak pernah cakram besar di atas yang kecil; 3^n posisi.
• Rekursi: selesaikan n-1 ke tiang cadangan, pindahkan yang terbesar, selesaikan n-1 ke atasnya; T(n)=2T(n-1)+1, sehingga T(n)=2^n-1.
• Optimal dan tunggal: cakram terbesar harus bergerak, dengan semua yang lain di tiang ketiga sebelumnya dan kerja yang sama lagi sesudahnya: M(n)\ge2M(n-1)+1.
• Waktu: 64 cakram, 2^64-1 langkah, 585 miliar tahun pada satu langkah per detik; rekursinya sedalam n.
• Biner: langkah m memindahkan cakram v+1 untuk bit set terendah 2^v dari m; cakram k bergerak 2^n-k kali; versi perulangan menggerakkan cakram terkecil searah setiap dua langkah; kode Gray.
• Graf: 3^n posisi membentuk segitiga Sierpiński, dan solusi terbaik adalah satu sisinya.
• Lebih banyak tiang: Frame–Stewart F(n,p)=\min(2F(k,p)+F(n-k,p-1)), optimal untuk p=4 (2014): 64 cakram dalam 18 433 langkah.
• Sejarah: Lucas 1883, Dudeney 1907, Frame dan Stewart 1941, Bousch 2014.

Glosarium: istilah penting

Menara Hanoi

Teka-teki memindahkan tumpukan cakram di antara tiga tiang, satu cakram sekali waktu, tanpa pernah menaruh cakram yang lebih besar di atas yang lebih kecil.

Rekursi

Cara menyelesaikan masalah dengan menyelesaikan salinan masalah yang sama yang lebih kecil dan menggabungkan hasilnya.

Relasi rekurensi langkah

Persamaan T(n) = 2T(n−1) + 1 untuk banyaknya langkah solusi terbaik dengan n cakram.

Pertumbuhan eksponensial

Pertumbuhan yang setiap satuan masukan tambahan mengalikan biaya dengan konstanta, seperti setiap cakram tambahan melipatduakan banyak langkah.

Barisan penggaris

Barisan 1, 2, 1, 3, 1, 2, 1, 4, … yang suku pada posisi m adalah satu ditambah banyaknya nol di ujung m dalam biner.

Kode Gray

Penomoran biner yang bilangan berurutannya berbeda tepat satu bit.

Segitiga Sierpiński

Fraktal yang terdiri dari tiga salinan dirinya setengah ukuran yang ditempatkan di sudut-sudut segitiga; graf posisi Menara Hanoi berbentuk seperti ini.

Bilangan Frame–Stewart

Banyaknya langkah solusi terbaik yang diketahui untuk Menara Hanoi dengan empat tiang atau lebih, ditemukan dengan membagi menara di tempat terbaik.

Pertanyaan yang sering diajukan

Referensi

1. Andreas M. Hinz, Sandi Klavžar, Ciril Petr (2018). The Tower of Hanoi – Myths and Maths (2nd ed.). Birkhäuser.
2. Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1994). Concrete Mathematics (2nd ed.), section 1.1: The Tower of Hanoi. Addison-Wesley.
3. N. Claus (de Siam) [Édouard Lucas] (1883). La Tour d'Hanoï, véritable casse-tête annamite. Paris, Paul Bousrez.
4. Thierry Bousch (2014). La quatrième tour de Hanoï. Bulletin of the Belgian Mathematical Society – Simon Stevin 21.
5. J. S. Frame and B. M. Stewart (1941). Solution to Advanced Problem 3918. The American Mathematical Monthly 48.
6. Henry E. Dudeney (1907). The Canterbury Puzzles. Heinemann, London.

Artikel terkait

• Notasi Big-O: Notasi Big-O dijelaskan: definisi, laju pertumbuhan dari O(1) sampai O(n!), menghitung langkah dalam kode, kasus terbaik dan terburuk, rekurensi, dan teorema Master.
• Bilangan Biner: Konversi, Operasi, Bit, dan Komplemen Dua: Bilangan biner: bit dan nilai tempat, konversi ke desimal dan heksadesimal, aritmetika biner, komplemen dua, operator bitwise, dan pecahan biner.
• Barisan dan Deret Geometri: Rasio, Jumlah, dan Pertumbuhan: Barisan dan deret geometri: rasio, rumus suku ke-n, jumlah berhingga dan tak hingga, rata-rata geometri, bunga majemuk, dan peluruhan, dengan latihan.
• Bilangan Fibonacci: Bilangan Fibonacci dijelaskan: rekurensi, rumus Binet, identitas, penggandaan cepat, jumlah Zeckendorf, periode Pisano, dan rasio emas, lengkap dengan kode.