- Se completează
- Citită
- Răspuns
Problema restului
Având câteva tipuri de monede, cum plătiți o sumă exactă cu cât mai puține monede și în câte moduri se poate face asta? Răspunsul greedy, cea mai mare monedă mai întâi, funcționează pentru banii reali, dar dă greș pentru unele seturi de monede. Un tabel care construiește fiecare sumă din sume mai mici găsește mereu răspunsul corect. Atingeți o monedă din tavă pentru a o pune pe tejghea și atingeți o monedă de pe tejghea pentru a o lua înapoi. Indicatorul se umple până la sumă: formați-o exact, cu cât mai puține monede. Cele mai puține monede arată cel mai bun răspuns, iar Greedy arată ce se obține luând mereu cea mai mare monedă care încape, ceea ce nu dă întotdeauna cele mai puține monede. Schimbați monedele (în cenți) și suma în panou. Vizualizarea Tabel arată cum găsește programarea dinamică cele mai puține monede sau cum numără modurile de a obține suma: apăsați Redare pentru a vedea cum se umple tabelul, sau Pas și Înapoi pentru a merge câte un pas, și trageți de cursorul pașilor pentru a sări oriunde. Fiecare monedă poate fi folosită de câte ori doriți. Cu tabelul selectat, tastele săgeți avansează câte un pas, bara de spațiu pornește și întrerupe redarea, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Atingeți monedele din tavă ca să formați exact suma și urmăriți cum se umple indicatorul în cenți.
- Încercați să folosiți cât mai puține monede, apoi apăsați Cele mai puține monede sau Greedy ca să comparați.
- Deschideți vizualizarea Tabel și apăsați Redare ca să vedeți cum fiecare celulă citește suma mai mică de care depinde.
Cele mai puține monede
Suma 0 nu necesită monede. Pentru fiecare sumă mai mare, încercați fiecare monedă care nu este mai mare decât ea: ce rămâne după acea monedă este o sumă mai mică, aflată deja în tabel, deci încă o monedă dă un candidat. Cel mai mic candidat intră în celulă, iar moneda care l-a dat este păstrată în rândul de dedesubt. Când tabelul este plin, monedele se citesc înapoi pornind de la țintă: luați ultima ei monedă, treceți la suma rămasă și repetați până la 0.
Număr de moduri
Pentru a număra combinații, nu ordini, tabelul adaugă câte o monedă pe rând. O celulă numără modurile de a obține suma ei cu monedele de până la rândul ei: modurile fără cea mai nouă monedă, adică celula de deasupra, plus modurile care folosesc cea mai nouă monedă cel puțin o dată, adică celula aflată cu tot atâtea coloane mai la stânga pe același rând. Deoarece monedele sunt adăugate într-o ordine fixă, 1 + 2 și 2 + 1 sunt același mod și se numără o singură dată.
Întrebări frecvente
De ce dă greș metoda greedy?
Algoritmul greedy ia mereu cea mai mare monedă care încape și nu revine niciodată asupra alegerii. Cu monedele 1, 3 și 4 și suma 6, ia 4, apoi 1 și 1: trei monede, când ar ajunge două de 3. Pentru sisteme de monede precum euro sau dolarul american, greedy se întâmplă să fie optim; astfel de sisteme se numesc canonice.
Care este diferența dintre a număra moduri și a număra ordini?
Modurile tratează 1 + 2 și 2 + 1 ca aceeași combinație; ordinile le numără separat. Aplicația numără moduri, adăugând monedele câte un rând pe rând. Pentru a număra în schimb ordinile, se parcurg sumele și se încearcă fiecare monedă pentru fiecare sumă.
Cât de rapid este algoritmul pentru problema restului?
Ambele tabele necesită un număr de pași egal cu numărul de tipuri de monede înmulțit cu suma. Este rapid pentru sume de ordinul miilor, dar o sumă poate fi un număr uriaș, așa că, măsurată după numărul de cifre, problema este în general NP-dificilă.
Ce se întâmplă dacă o sumă nu poate fi formată?
Celula ei rămâne la ∞, de exemplu sumele 1 și 3 cu monedele 2 și 5. În modul Număr de moduri, rezultatul ei este pur și simplu 0.
Se trimite ceva undeva?
Nu. Totul este calculat în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor