Latihan 1: Memoization & Dynamic Programming — Algoritma

Latihan 1 dari materi Memoization & Dynamic Programming di Algoritma — praktek dengan editor kode interaktif, test case otomatis, dan hint terpandu. Langsung jalan di browser.

Lengkapi fibMemo(n, memo = {}) supaya mengembalikan angka ke-n deret Fibonacci (0, 1, 1, 2, 3, 5, 8, ...) dengan memoization:

Base case: kalau n <= 1, kembalikan n.
Kalau hasil untuk n sudah ada di memo, kembalikan memo[n].
Kalau belum, hitung dari dua angka Fibonacci sebelumnya: panggil lagi fibMemo untuk n - 1 dan untuk n - 2, teruskan memo yang sama ke kedua panggilan itu, lalu jumlahkan hasilnya. Simpan jumlahnya ke memo[n], lalu kembalikan.

Simpan dan baca catatannya lewat object memo (misalnya memo[n]), dan kirim memo ke tiap panggilan, supaya angka besar selesai dalam sekejap.

console.log di starter jangan diubah. Output-nya harus tiga baris ini, berurutan:

55 (dari fibMemo(10))
6765 (dari fibMemo(20))
102334155 (dari fibMemo(40))

Function-nya juga dicek dengan fibMemo(78), yang harus cepat mengembalikan 8944394323791464.

Hint

Memo adalah catatan hasil yang sudah dihitung. Sebelum menghitung fib(n), lihat dulu apa jawabannya sudah ada di catatan.
Tiga langkah: base case n <= 1, lalu cek memo[n] !== undefined, lalu hitung dan simpan di memo[n]. Kirim memo sebagai argumen kedua di tiap panggilan rekursif.
if (n <= 1) return n; if (memo[n] !== undefined) return memo[n]; memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); return memo[n];

</> { } .css => #id fn()

Versi baru

HyperSheets

bagian dari BelajarWeb.dev

Membuka gerbang…

Latihan 1: Memoization & Dynamic Programming — Algoritma

Hint

Memperbarui Aplikasi