- Dolduruluyor
- Okunan
- Cevap
Para üstü problemi
Birkaç çeşit madeni para verildiğinde, tam bir tutarı olabildiğince az parayla nasıl ödersiniz ve bu toplamda kaç farklı şekilde yapılabilir? Önce en büyük parayı alan açgözlü cevap gerçek paralarda işe yarar, ama bazı para kümelerinde başarısız olur. Her tutarı daha küçük tutarlardan kuran bir tablo ise her zaman doğru sonucu verir. Tepsideki bir madeni paraya dokunarak onu tezgâha ekleyin, tezgâhtaki bir madeni paraya dokunarak geri alın. Gösterge tutara doğru dolar: tutarı tam olarak, olabildiğince az madeni parayla oluşturun. En az madeni para en iyi cevabı gösterir; Açgözlü ise her zaman sığan en büyük parayı alınca ne elde edildiğini gösterir, bu her zaman en az sayı değildir. Paneldeki madeni paraları (sent olarak) ve tutarı değiştirin. Tablo görünümü, dinamik programlamanın en az madeni parayı nasıl bulduğunu ya da tutarı oluşturmanın yollarını nasıl saydığını gösterir: tablonun dolmasını izlemek için Oynat'a, adım adım ilerlemek için Adım ve Geri'ye basın; istediğiniz yere atlamak için adım kaydırıcısını sürükleyin. Her madeni para istediğiniz kadar kullanılabilir. Tablo seçiliyken ok tuşları adım adım ilerletir, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- Tutarı tam oluşturmak için tepsideki paralara dokunun ve göstergenin sent cinsinden dolduğunu izleyin.
- Olabildiğince az para kullanmaya çalışın, ardından karşılaştırmak için En az madeni para ya da Açgözlü düğmesine basın.
- Tablo görünümünü açın ve her hücrenin bağlı olduğu daha küçük tutarı nasıl okuduğunu izlemek için Oynat'a basın.
En az madeni para
0 tutarı hiç madeni para gerektirmez. Daha büyük her tutar için, ondan büyük olmayan her madeni parayı deneyin: o paradan sonra kalan, tabloda zaten bulunan daha küçük bir tutardır; bu yüzden bir madeni para daha bir aday verir. En küçük aday hücreye yazılır ve onu veren para alttaki satırda saklanır. Tablo dolunca paralar hedeften geriye doğru okunur: hedefin son madeni parasını alın, kalan tutara gidin ve 0'a ulaşana kadar tekrarlayın.
Yol sayısı
Sıralamaları değil kombinasyonları saymak için tablo her satırda bir madeni para ekler. Bir hücre, kendi tutarını o satıra kadarki paralarla oluşturmanın yollarını sayar: en yeni para olmadan kurulan yollar, yani üstteki hücre, artı en yeni parayı en az bir kez kullanan yollar, yani aynı satırda o paranın değeri kadar sütun soldaki hücre. Paralar sabit bir sırayla eklendiği için 1 + 2 ve 2 + 1 aynı yoldur ve bir kez sayılır.
Sık sorulan sorular
Açgözlü yöntem neden başarısız olur?
Açgözlü yöntem her zaman sığan en büyük parayı alır ve kararını asla yeniden gözden geçirmez. 1, 3 ve 4 değerindeki paralar ve 6 tutarıyla önce 4'ü, sonra 1 ve 1'i alır: iki tane 3 yeterliyken üç madeni para. Euro veya ABD doları gibi para sistemlerinde açgözlü yöntem tesadüfen en iyi sonucu verir; bu tür sistemlere kanonik denir.
Yolları saymakla sıralamaları saymak arasındaki fark nedir?
Yollarda 1 + 2 ile 2 + 1 aynı kombinasyon sayılır; sıralamalarda ise ayrı ayrı sayılır. Uygulama, paraları satır satır ekleyerek yolları sayar. Sıralamaları saymak içinse tutarlar sırayla gezilir ve her biri için her para denenir.
Para üstü algoritması ne kadar hızlıdır?
Her iki tablo da para çeşidi sayısı çarpı tutar kadar adım sürer. Binlerle ifade edilen tutarlar için bu hızlıdır, ancak bir tutar çok büyük bir sayı olabilir; bu nedenle basamak sayısına göre ölçüldüğünde problem genel olarak NP-zordur.
Bir tutar oluşturulamazsa ne olur?
Hücresi ∞ olarak kalır; örneğin 2 ve 5 değerindeki paralarla 1 ve 3 tutarları. Yol sayısı modunda sayısı basitçe 0'dır.
Herhangi bir yere veri gönderiliyor mu?
Hayır. Her şey tarayıcınızda hesaplanır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git