Meydan okuma 1
- Algoritmalar kursu
- İleri seviye
- Ders 53/56
- 4 dk
DP ile Fibonacci hesaplayıp yazdırırsın.
Meydan okuma 1: LCS
Bu meydan okumada en uzun ortak alt dizi (LCS) problemini dinamik programlama ile çözeceksin. İki dizi arasındaki en uzun ortak alt diziyi bulacaksın.
Diziler s1 = 'AGGTAB' ve s2 = 'GXTXAYB'. LCS uzunluğu 4'tür. DP tablosu kurarak bu sonucu üret.
Uygulama lcs_length fonksiyonu
lcs_length(s1, s2) yaz. DP tablosu kur, LCS uzunluğunu döndür. print(lcs_length('AGGTAB', 'GXTXAYB')) ile 4 yazdır.
Başlangıç kodu
def lcs_length(s1, s2):
# LCS uzunluğunu DP ile bulÖrnek çözüm
def lcs_length(s1, s2):
# LCS uzunluğunu DP ile bul
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[len(s1)][len(s2)]
print(lcs_length('AGGTAB', 'GXTXAYB'))Beklenen çıktı
4
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 LCS hangi dizileri kullanır?
- İki dizi Doğru cevap
- Üç dizi
- Tek dizi
- Boş dizi
Açıklama: LCS iki diziyi karşılaştırır.
2 DP bağıntısı
Soru
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][____-1] + 1
Cevap
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1Açıklama: j doğru.
3 Meydan okuma 1: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
s1 |
AGGTAB |
s2 |
GXTXAYB |
LCS |
GTAB |
uzunluk |
4 |