Tabulation nedir?
- Algoritmalar kursu
- İleri seviye
- Ders 5/56
- 4 dk
Alt problemleri bir tabloya doldurarak çözmeyi öğrenirsin.
Tabulation nedir?
Tabulation, alt problemleri bir tabloya alttan yukarı (bottom-up) doldurarak çözer.
Recursion yerine döngü kullanılır; her hücre bir alt problemin sonucudur.
Tabulation, memoization'ın alttan yukarı (bottom-up) karşılığıdır; stack overflow riski yoktur.
Bottom-up yaklaşım
Tabulation önce en küçük alt problemleri çözer, sonra bunları kullanarak büyük olanları kurar.
Hiçbir recursion yoktur; tüm hesap bir döngü içinde yapılır.
Bu yaklaşım, derin recursion'larda stack taşmasını önler; büyük n değerleri için uygundur.
Uygulama Fibonacci tabulation
fib_tab(n) yaz. Tabloyla Fibonacci hesapla. print(fib_tab(10)) ile 55 yazdır.
Başlangıç kodu
def fib_tab(n):
# Fibonacci tabulationÖrnek çözüm
def fib_tab(n):
# Fibonacci tabulation
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fib_tab(10))Beklenen çıktı
55
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Tabulation hangi yönde çalışır?
- Top-down
- Bottom-up Doğru cevap
- Yanlardan
- Rastgele
Açıklama: Bottom-up.
2 Tablo yapısı
dp = [0] * (____ + 1)dp = [0] * (n + 1)Açıklama: n doğru.
3 Tabulation nedir: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
tabulation |
Bottom-up |
table |
Tablo |
loop |
Döngü |
no recursion |
Recursion yok |