Bozuk para
- Algoritmalar kursu
- Orta seviye
- Ders 62/80
- 4 dk
Greedy ile bozuk para verme örneğini öğrenirsin.
Bozuk para
Greedy bozuk para: verilmiş para birimleriyle bir tutarı olabildiğince az parayla ver. Her adımda en büyük parayı al.
Sistem 1, 5, 10, 25 gibi standartsa greedy en iyiyi verir; aksi halde DP gerekir.
Bu yüzden gerçek hayatta bozuk para makineleri greedy kullanır; hızlı ve standart sistemlerde optimim.
Adım adım
Her yinelemede kalan tutardan en büyük parayı düşür; sayacı bir artır. Kalan sıfıra inince dur.
Bu, klasik greedy döngüsüdür; her adımda bir para azaltılır.
Döngü, kalan tutar sıfır olana kadar sürer; tüm paralar sırayla işlenir.
Uygulama Greedy bozuk para
greedy_coins(coins, amount) yaz. En az para sayısını döndür. print(greedy_coins([25, 10, 5, 1], 63)) ile 6 yazdır.
Başlangıç kodu
def greedy_coins(coins, amount):
# En az para sayısıÖrnek çözüm
def greedy_coins(coins, amount):
# En az para sayısı
coins.sort(reverse=True)
count = 0
for coin in coins:
count += amount // coin
amount = amount % coin
return count
print(greedy_coins([25, 10, 5, 1], 63))Beklenen çıktı
6
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kalan güncelleme
amount ____ coinamount -= coinAçıklama: -= doğru.
2 Bozuk para: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
coin |
Para |
amount |
Tutar |
remainder |
Kalan |
counter |
Sayaç |
3 63 tutarını [25,10,5,1] ile greedy çözümü kaç para verir?
- 4
- 5
- 6 Doğru cevap
- 7
Açıklama: 6 (2×25 + 1×10 + 3×1).