Użyte monety
Uzyskana kwota
Minimalna liczba

    Monety (¢)

      Więcej o problemie wydawania reszty

      Problem wydawania reszty

      Jak przy kilku rodzajach monet zapłacić dokładną kwotę jak najmniejszą liczbą monet i na ile sposobów w ogóle da się to zrobić? Zachłanna odpowiedź, najpierw największa moneta, działa dla prawdziwych pieniędzy, ale zawodzi dla niektórych zestawów monet. Tabela, która buduje każdą kwotę z mniejszych, zawsze daje dobry wynik. Dotknij monety na tacce, aby położyć ją na ladzie, i dotknij monety na ladzie, aby ją zabrać z powrotem. Wskaźnik napełnia się aż do kwoty: uzyskaj ją dokładnie, używając jak najmniej monet. Najmniej monet pokazuje najlepszą odpowiedź, a Zachłanny pokazuje, co wychodzi, gdy zawsze bierze się największą monetę, która się mieści, co nie zawsze daje najmniej monet. Zmień monety (w centach) i kwotę w panelu. Widok Tabela pokazuje, jak programowanie dynamiczne znajduje najmniejszą liczbę monet albo liczy sposoby uzyskania kwoty: naciśnij Odtwórz, aby zobaczyć, jak tabela się wypełnia, albo Krok i Wstecz, aby przechodzić krok po kroku, i przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Każdej monety można używać dowolnie wiele razy. Gdy tabela jest zaznaczona, strzałki przechodzą o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.

      Jak to działa

      1. Stukaj monety na tacy, aby ułożyć dokładnie tę kwotę, i patrz, jak wskaźnik wypełnia się w centach.
      2. Spróbuj użyć jak najmniej monet, a potem naciśnij Najmniej monet lub Zachłanny, aby porównać.
      3. Otwórz widok Tabela i naciśnij Odtwórz, aby zobaczyć, jak każda komórka odczytuje mniejszą kwotę, od której zależy.

      Najmniej monet

      Kwota 0 nie wymaga monet. Dla każdej większej kwoty wypróbuj każdą monetę, która nie jest od niej większa: to, co zostaje po tej monecie, jest mniejszą kwotą, już obecną w tabeli, więc jedna moneta więcej daje kandydata. Najmniejszy kandydat trafia do komórki, a moneta, która go dała, jest zapisywana w wierszu poniżej. Gdy tabela jest pełna, monety odczytuje się wstecz od kwoty docelowej: weź jej ostatnią monetę, przejdź do kwoty, która zostaje, i powtarzaj aż do 0.

      Liczba sposobów

      Aby liczyć kombinacje, a nie kolejności, tabela dodaje jedną monetę na wiersz. Komórka liczy sposoby uzyskania swojej kwoty monetami aż do swojego wiersza: sposoby bez najnowszej monety, czyli komórkę powyżej, plus sposoby, które używają najnowszej monety co najmniej raz, czyli komórkę o tyle kolumn w lewo w tym samym wierszu. Ponieważ monety są dodawane w stałej kolejności, 1 + 2 i 2 + 1 to ten sam sposób i jest liczony raz.

      Często zadawane pytania

      Dlaczego metoda zachłanna zawodzi?

      Algorytm zachłanny zawsze bierze największą monetę, która się mieści, i nigdy nie zmienia decyzji. Przy monetach 1, 3 i 4 oraz kwocie 6 bierze 4, a potem 1 i 1: trzy monety, choć wystarczyłyby dwie trójki. Dla systemów monet takich jak euro czy dolar amerykański algorytm zachłanny akurat jest optymalny; takie systemy nazywa się kanonicznymi.

      Czym różni się liczenie sposobów od liczenia kolejności?

      Przy sposobach 1 + 2 i 2 + 1 to ta sama kombinacja; przy kolejnościach liczy się je osobno. Aplikacja liczy sposoby, dodając monety po jednym wierszu. Aby zamiast tego liczyć kolejności, przechodzi się po kwotach i dla każdej próbuje się każdej monety.

      Jak szybki jest algorytm wydawania reszty?

      Obie tabele wymagają tylu kroków, ile wynosi liczba rodzajów monet razy kwota. To szybko dla kwot rzędu tysięcy, ale kwota może być ogromną liczbą, więc mierzony liczbą cyfr problem jest w ogólności NP-trudny.

      Co, jeśli kwoty nie da się uzyskać?

      Jej komórka zostaje na ∞, na przykład kwoty 1 i 3 przy monetach 2 i 5. W trybie Liczba sposobów jej wynik to po prostu 0.

      Czy cokolwiek jest gdzieś wysyłane?

      Nie. Wszystko jest obliczane w twojej przeglądarce, a ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.

      Chcesz wypróbować?

      Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

      Przejdź do edytora