Kapan akhir dunia?

Beberapa hari yang lalu seorang teman saya mengatakan kepada saya:

Akhir dunia dan umat manusia akan terjadi ketika masalah Menara Hanoi dapat diselesaikan dengan 64 cakram.

Ini adalah pendekatan yang menarik dan lelucon yang bagus untuk menjelaskan topik ini. Tapi sungguh, apa ini? apa arti dari kalimat ini?

Yah, pertama-tama untuk menjelaskannya, masalah Hanoi sendiri perlu dijelaskan.

Towers of Hanoi adalah teka-teki matematika di mana kita memiliki tiga batang ( A , B , dan C ) dan N disk. Awalnya, semua piringan ditumpuk dalam nilai diameter yang menurun yaitu piringan terkecil diletakkan di atas dan berada di batang A . Tujuan dari teka-teki ini adalah untuk memindahkan seluruh tumpukan ke batang lain (di sini dianggap C ), dengan mengikuti aturan sederhana berikut:

• Hanya satu disk yang dapat dipindahkan dalam satu waktu.
• Setiap gerakan terdiri dari pengambilan disk bagian atas dari salah satu tumpukan dan menempatkannya di atas tumpukan lainnya, yaitu disk hanya dapat dipindahkan jika merupakan disk paling atas di tumpukan.
• Tidak ada disk yang dapat ditempatkan di atas disk yang lebih kecil.

Pada gambar di atas, diperlihatkan tiga buah batang (A, B, C) dan diperlukan untuk menggerakkan empat buah piringan. Jadi, kita dapat mengatakan bahwa An adalah masalah memindahkan semua disk dari A ke C, di mana n adalah jumlah total disk (dalam hal ini empat). Gagasan utamanya adalah:

• Ambil n — 1 disk dari A (n — 1 disk pertama) dan pindahkan ke B (menggunakan batang bantu).
• Ambil sisa disk di A dan pindahkan ke C.
• Selesaikan masalah memindahkan n — 1 cakram di B (titik 1) ke C (menggunakan batang bantu).

Jadi, rumus ini menyatakan bahwa jika Anda ingin mengetahui berapa banyak langkah yang diperlukan untuk menyelesaikan Hanoi dengan n disk, kami hanya bergantung pada kasus dasar dan iterasi terakhir.

Pada akhirnya, ungkapan sebenarnya untuk menyelesaikan berapa banyak langkah yang dibutuhkan adalah (ini bisa menjadi latihan yang bagus):

Dan ini buktinya:

Nah, kembali ke titik awal tulisan ini, dan dengan menggunakan rumus ini:

Hanya untuk membuat ide jika kita dapat memindahkan disk dengan kecepatan 1 per detik, akan memakan waktu sekitar 584 miliar tahun untuk menyelesaikannya, yaitu sekitar 44 kali usia alam semesta saat ini; jadi mengikuti ide teman saya kita tidak perlu khawatir. :)

#hanoi #recursion #math #joke