Lanjut50 XPUnit 9: Fungsi dan Rekursi, soal 3 dari 9
Fibonacci Cepat
Hitung bilangan Fibonacci ke-N dengan rekursi yang mengingat hasilnya.
Deret Fibonacci dimulai dari 0 dan 1, lalu setiap bilangan adalah jumlah dua bilangan sebelumnya: 0, 1, 1, 2, 3, 5, 8, dan seterusnya. Rekursi biasa untuk deret ini sangat lambat, karena bilangan yang sama dihitung berulang-ulang.
Masukan
Satu bilangan bulat N dari 0 sampai 78. F(0) = 0 dan F(1) = 1.
Keluaran
Nilai F(N).
Contoh masukan dan keluaran
Contoh 1
Masukan
10
Keluaran
55
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Coba hitung berapa kali F(2) dipanggil saat menghitung F(6) dengan rekursi biasa. Jumlahnya berlipat cepat sekali.
Petunjuk 2
Simpan hasil yang sudah dihitung di dictionary. Sebelum menghitung, periksa dulu apakah jawabannya sudah ada.