Özet - Divide and conquer
- Algoritmalar kursu
- Orta seviye
- Ders 68/80
- 4 dk
Bir problemi bölerek çözen mini görev yaparsın.
Özet - Divide and conquer
Böl ve yönet; böl, recursive yönet ve birleştir adımlarıyla problemleri çözer. Merge sort, quick sort ve binary search bu yaklaşımla çalışır.
Bu mini görevde böl ve yönet ile sayma yapacaksın; tüm adımları birleştir.
Yaklaşım, paralel donanımlarda da verimli çalışır; alt problemler bağımsızdır.
Uygulama Böl say
dc_count(arr, target) yaz. Diziyi ikiye böl, her yarında target'ın kaç kez geçtiğini recursive say, topla. print(dc_count([1, 2, 1, 3, 1], 1)) ile 3 yazdır.
Başlangıç kodu
def dc_count(arr, target):
# Böl ve sayÖrnek çözüm
def dc_count(arr, target):
# Böl ve say
if len(arr) == 0:
return 0
if len(arr) == 1:
return 1 if arr[0] == target else 0
mid = len(arr) // 2
return dc_count(arr[:mid], target) + dc_count(arr[mid:], target)
print(dc_count([1, 2, 1, 3, 1], 1))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - Divide and conquer: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
divide |
Böl |
conquer |
Yönet |
combine |
Birleştir |
base case |
Durdur |
2 Orta bul
Soru
mid = len(arr) ____ 2
Cevap
mid = len(arr) // 2Açıklama: // doğru.
3 Böl ve yönet hangi algoritmalarda kullanılır?
- Linear search
- Merge sort, quick sort Doğru cevap
- Bubble sort
- Heap only
Açıklama: Merge sort, quick sort.