Meydan okuma 3
- Algoritmalar kursu
- Uzman seviye
- Ders 39/41
- 4 dk
Dışbükey zarfı yazdırırsın.
Meydan okuma 3 - Dışbükey zarf
Üçüncü meydan okuma, dışbükey zarf algoritmasını yoklar. Andrew monoton zincir yöntemiyle nokta kümesinin zarfını hesaplar.
count_doublings ve kmp_search fonksiyonları yukarıda hazırdır; sen convex_hull yazacaksın. Önce noktaları sırala, sonra alt ve üst zarfı kur.
Bu meydan okuma, birikimli zincirin üçüncü halkasıdır.
Uygulama convex_hull fonksiyonu
convex_hull(points) yaz. Nokta listesinin dışbükey zarfını saat yönünün tersine döndür. print(convex_hull([(0,0), (4,0), (4,3), (0,3), (2,1)])) ile [(0, 0), (4, 0), (4, 3), (0, 3)] yazdır. count_doublings ve kmp_search yukarıda hazırdır.
Başlangıç kodu
def count_doublings(n):
count = 0
size = 1
last = 0
for i in range(n):
if last == size:
size *= 2
count += 1
last += 1
return count
def kmp_search(text, pattern):
n, m = len(text), len(pattern)
lps = [0] * m
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
i = j = 0
while i < n:
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
return i - j
elif j != 0:
j = lps[j - 1]
else:
i += 1
return -1
def convex_hull(points):
# Dışbükey zarfı döndürÖrnek çözüm
def convex_hull(points):
pts = sorted(set(points))
if len(pts) <= 1:
return pts
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
lower = []
for p in pts:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
upper = []
for p in reversed(pts):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
print(convex_hull([(0,0), (4,0), (4,3), (0,3), (2,1)]))Beklenen çıktı
[(0, 0), (4, 0), (4, 3), (0, 3)]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Convex hull kavramları
| Kavram | Anlamı |
|---|---|
monoton zincir |
Andrew yöntemi |
sıralama |
İlk adım |
alt zarf |
Soldan sağa |
üst zarf |
Sağdan sola |
2 çapraz çarpım
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[____]) * (b[0] - o[0])return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])Açıklama: a[1] - o[1] y bileşenidir.
3 Dışbükey zarf hangi yöntemle kurulur?
- Sıralı tarama
- DFS
- Monoton zincir Doğru cevap
- Greedy
Açıklama: Monoton zincir (Andrew) yöntemi kullanılır.