Sel terisi
Penjumlahan
Panggilan tanpa tabel

  • Sedang diisi
  • Dibaca
  • Jawaban

Selengkapnya tentang Fibonacci dengan pemrograman dinamis

Fibonacci dengan pemrograman dinamis

Bilangan Fibonacci adalah contoh pertama klasik pemrograman dinamis. Rekursi biasa meminta suku yang sama berulang-ulang, tetapi dengan tabel yang mengingat setiap suku, pekerjaannya hanya bertambah sebanding dengan n. Pilih suku, pilih bawah ke atas atau atas ke bawah, lalu jalankan langkah demi langkah untuk melihat setiap sel diisi tepat satu kali. Tekan Putar untuk melihat tabel terisi, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Pilih n, suku yang ingin dihitung, dan metodenya: bawah ke atas mengisi tabel dari kiri, atas ke bawah tetap memakai rekursi tetapi memeriksa tabel lebih dulu, dan baris di bawah tabel lalu menjadi tumpukan panggilan yang masih terbuka. Contoh baru memilih n lain. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Ketik n, suku yang ingin dihitung, di kolom Suku n, lalu pilih Bawah ke atas atau Atas ke bawah.
  2. Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja.
  3. Perhatikan setiap sel membaca dua sel sebelumnya. Pada atas ke bawah, baris di bawah tabel adalah tumpukan panggilan yang masih terbuka.

Bawah ke atas dan atas ke bawah

Bawah ke atas (bottom-up), yang juga disebut tabulasi, dimulai dengan F(0) = 0 dan F(1) = 1 lalu mengisi tabel dari kiri ke kanan: setiap sel baru adalah jumlah dua sel sebelumnya. Atas ke bawah (top-down), yang juga disebut memoisasi, tetap memakai definisi rekursif: untuk mencari F(n), minta F(n − 1) dan F(n − 2). Bedanya dengan rekursi biasa, setiap panggilan memeriksa tabel lebih dulu dan hanya menghitung suku jika selnya masih kosong. Keduanya mengisi setiap sel satu kali dan memakai n − 1 penjumlahan.

Mengapa rekursi biasa begitu lambat

Tanpa tabel, F(n) memanggil F(n − 1) dan F(n − 2), keduanya memanggil F(n − 3), dan seterusnya: panggilan-panggilan itu membentuk pohon tempat suku yang sama muncul berulang-ulang. Jumlah panggilannya 2·F(n + 1) − 1, yang tumbuh secepat bilangan Fibonacci itu sendiri: 177 panggilan untuk F(10), 21.891 untuk F(20), dan lebih dari 331 juta untuk F(40). Submasalah yang tumpang tindih seperti inilah yang menjadi tujuan pemrograman dinamis.

Pertanyaan yang sering diajukan

Apa itu pemrograman dinamis?

Cara menyelesaikan masalah dengan memecahnya menjadi masalah-masalah lebih kecil yang saling tumpang tindih, menyelesaikan setiap masalah kecil satu kali, dan menyimpan jawabannya dalam tabel. Bilangan Fibonacci adalah contoh paling sederhana: setiap suku dibentuk dari dua suku sebelumnya.

Apa perbedaan memoisasi dan tabulasi?

Memoisasi tetap memakai kode rekursif dan menyimpan setiap jawaban saat pertama kali dihitung, sehingga panggilan berikutnya cukup membacanya. Tabulasi mengisi tabel dalam urutan yang menjamin setiap jawaban yang dibutuhkan sebuah sel sudah tersedia. Keduanya melakukan penjumlahan yang sama; tabulasi tidak memerlukan tumpukan panggilan, sedangkan memoisasi hanya menghitung sel yang benar-benar dibutuhkan.

Berapa penjumlahan yang diperlukan F(n)?

n − 1 dengan tabel: satu untuk setiap suku dari F(2) sampai F(n). Hanya dua suku terakhir yang pernah dibaca, jadi program juga bisa menyimpan dua angka saja alih-alih seluruh tabel.

Mengapa aplikasi berhenti di n = 40?

F(40) = 102.334.155 masih muat dengan mudah di layar, dan rekursi biasa sudah memerlukan 331.160.281 panggilan untuk menghitungnya. Suku yang lebih besar tumbuh dengan cepat: F(78) adalah suku terbesar yang dapat disimpan tepat oleh angka JavaScript.

Apakah ada data yang dikirim ke mana pun?

Tidak. Semuanya dihitung di browser Anda, dan pengaturan terakhir Anda tetap tersimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor