8. Ochko‘z algoritmlar
Fikr
Ochko‘z (greedy) algoritm har qadamda shu paytdagi eng yaxshi
tanlovni qiladi va orqaga qaytmaydi.
Klassik misol: tadbirlarni tanlash
Boshlanish va tugash vaqti berilgan tadbirlardan eng ko‘pini tanlash
kerak (ular kesishmasin).
To‘g‘ri strategiya — eng erta tugaydiganini olish:
tadbirlar.sort(key=lambda t: t[1]) # tugash vaqti bo‘yicha
oxiri = -10**18
soni = 0
for boshi, tugashi in tadbirlar:
if boshi >= oxiri:
soni += 1
oxiri = tugashi
print(soni)«Eng qisqasini» yoki «eng erta boshlanadiganini» olish esa noto‘g‘ri
javob beradi.
Qachon ishlaydi
Ochko‘z usul faqat masala ochko‘z tanlov xossasiga ega bo‘lganda
to‘g‘ri: mahalliy eng yaxshi tanlov global eng yaxshi javobga olib
borishi kerak.
Buni his qilishning amaliy yo‘li — qarshi misol izlash. Topa
olmasangiz va isbot topsangiz, ochko‘z ishlaydi.
Tipik qarshi misol: tanga
Tangalar 1, 3, 4 va 6 so‘m yig‘ish kerak. Ochko‘z: 4 + 1 + 1 = uchta
tanga. To‘g‘ri javob: 3 + 3 = ikkita. Demak bu masalada ochko‘z
xato — u yerda dinamik dasturlash kerak.
Lekin odatdagi pul tizimida (1, 5, 10, 25) ochko‘z to‘g‘ri ishlaydi.
Ko‘p uchraydigan ochko‘z naqshlar
- saralab, ketma-ket olish;
- eng katta / eng kichikni olish (
heapqbilan); - juftlashtirish: eng kattani eng kichigi bilan;
- oraliqlarni tugash vaqti bo‘yicha saralash.
Deyarli barchasi saralashdan boshlanadi.
Misol
tadbirlar = sorted(tadbirlar, key=lambda t: t[1])
oxiri = float('-inf')
soni = 0
for boshi, tugashi in tadbirlar:
if boshi >= oxiri:
soni += 1
oxiri = tugashi
print(soni)Mashq masalalari
| ✓ | Kod | Masala | Qiyinlik |
|---|---|---|---|
| AL08-1 | Tangalar | Boshlang‘ich | |
| AL08-2 | Tadbirlar | Oson | |
| AL08-3 | Qayiqlar | O‘rta | |
| AL08-4 | Eng katta son | Qiyin | |
| AL08-5 | Navbatda kutish | Oson |