Przeczytaj

Implementacja algorytmu wydawania reszty w języku Java

Problem 1

Zaimplementujemy metodę zachlanneWydawanieReszty(), która dla zadanej reszty resztaDoWydania zwróci liczbę monet lub banknotów z n elementowej tablicy nominaly potrzebnych do jej wydania. Każdego nominału z tablicy nominaly możemy użyć dowolną liczbę razy.

Wykorzystamy uproszczony polski system monetarnysystem monetarnysystem monetarny.

Specyfikacja:

Dane:

resztaDoWydania – liczba naturalna; wartość reszty do wydania
n – liczba naturalna; liczba dostępnych nominałów
nominaly – tablica liczb naturalnych; tablica dostępnych nominałów posortowana malejąco

Wynik:

komunikat dotyczący wykorzystanych nominałów

Przykładowy komunikat:

Nominal 50 wydano 1 razy
Nominal 20 wydano 1 razy
Nominal 10 wydano 0 razy
Nominal 5 wydano 1 razy
Nominal 2 wydano 1 razy
Nominal 1 wydano 0 razy
Liczba nominalow uzytych do wydania reszty 77: 4

W kodzie źródłowym języka Java przedstawiono przykładową implementację algorytmu zachłannegoalgorytm zachłannyalgorytmu zachłannego, który może zostać wykorzystany do rozwiązania problemu wydawania reszty. Metoda zachlanneWydawanieReszty() przyjmuje trzy parametry:

resztaDoWydania – wartość reszty do wydania,
nominaly – tablica dostępnych nominałów posortowana malejąco,
n – rozmiar tablicy, czyli po prostu liczba dostępnych nominałów.

Zmienna k wewnątrz pętli for przechowuje maksymalną liczbę powtórzeń nominału nominaly[i], przy pozostałej kwocie do wydania resztaDoWydania. Wartość resztaDoWydania jest zmniejszana o maksymalną wartość, którą można wydać danym nominałem. Algorytm zwraca liczbę monet lub banknotów użytych do wydania reszty o początkowej wartości resztaDoWydania.

Linia 1. public class ZachlanneWydawanieReszty otwórz nawias klamrowy. Linia 2. public static int zachlanneWydawanieReszty otwórz nawias okrągły int resztaDoWydania przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy nominaly przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. int wynik znak równości 0 średnik. Linia 5. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int k znak równości resztaDoWydania prawy ukośnik nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 7. wynik znak równości wynik plus k średnik. Linia 8. resztaDoWydania znak równości resztaDoWydania minus k asterysk nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. System kropka out kropka println otwórz nawias okrągły cudzysłów Nominal cudzysłów plus nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów wydano cudzysłów plus k plus cudzysłów razy cudzysłów zamknij nawias okrągły średnik. Linia 11. zamknij nawias klamrowy. Linia 13. return wynik średnik. Linia 14. zamknij nawias klamrowy. Linia 16. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. int otwórz nawias kwadratowy zamknij nawias kwadratowy nominaly znak równości otwórz nawias klamrowy 50 przecinek 20 przecinek 10 przecinek 5 przecinek 2 przecinek 1 zamknij nawias klamrowy średnik. Linia 18. int n znak równości nominaly kropka length średnik. Linia 19. int resztaDoWydania znak równości 77 średnik. Linia 20. int k znak równości zachlanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominaly przecinek n zamknij nawias okrągły średnik. Linia 22. System kropka out kropka println otwórz nawias okrągły cudzysłów Liczba nominalow uzytych do wydania reszty cudzysłów plus resztaDoWydania plus cudzysłów dwukropek cudzysłów plus k zamknij nawias okrągły średnik. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy.

public class ZachlanneWydawanieReszty {
    public static int zachlanneWydawanieReszty(int resztaDoWydania, int[] nominaly, int n) {
        int wynik = 0;

        for (int i = 0; i < n; i++) {
            int k = resztaDoWydania / nominaly[i];
            wynik = wynik + k;
            resztaDoWydania = resztaDoWydania - k * nominaly[i];

            System.out.println("Nominal " + nominaly[i] + " wydano " + k + " razy");
        }

        return wynik;
    }

    public static void main(String[] args) {
        int[] nominaly = { 50, 20, 10, 5, 2, 1 };
        int n = nominaly.length;
        int resztaDoWydania = 77;
        int k = zachlanneWydawanieReszty(resztaDoWydania, nominaly, n);

        System.out.println("Liczba nominalow uzytych do wydania reszty " + resztaDoWydania + ": " + k);
    }
}

Przyjrzyjmy się innej implementacji funkcji zachlanneWydawanieReszty(), która w celu określenia liczby nominałów, potrzebnej do wydania reszty resztaDoWydania, używa operacji dzielenia modulo. Możemy podzielić całkowicie resztę resztaDoWydania przez nominał nominaly[i], zaokrąglając tym samym wynik dzielenia w dół, do całkowitej części liczby. Dzięki temu dowiemy się, ile sztuk danego nominału algorytm użyje do wydania reszty. Operacja resztaDoWydania % nominaly[i] zwróci informację o tym, jaka kwota pozostała do wydania.

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class ZachlanneWydawanieReszty otwórz nawias klamrowy. Linia 4. public static int zachlanneWydawanieReszty otwórz nawias okrągły int resztaDoWydania przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy nominaly przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. int wynik znak równości 0 średnik. Linia 7. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. int k znak równości resztaDoWydania prawy ukośnik nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 9. wynik znak równości wynik plus k średnik. Linia 10. resztaDoWydania znak równości resztaDoWydania procent nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 12. System kropka out kropka println otwórz nawias okrągły cudzysłów Nominal cudzysłów plus nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów wydano cudzysłów plus k plus cudzysłów razy cudzysłów zamknij nawias okrągły średnik. Linia 13. zamknij nawias klamrowy. Linia 15. return wynik średnik. Linia 16. zamknij nawias klamrowy. Linia 18. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. int otwórz nawias kwadratowy zamknij nawias kwadratowy nominaly znak równości otwórz nawias klamrowy 50 przecinek 20 przecinek 10 przecinek 5 przecinek 2 przecinek 1 zamknij nawias klamrowy średnik. Linia 20. int n znak równości nominaly kropka length średnik. Linia 21. int resztaDoWydania znak równości 77 średnik. Linia 22. int k znak równości zachlanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominaly przecinek n zamknij nawias okrągły średnik. Linia 24. System kropka out kropka println otwórz nawias okrągły cudzysłów Liczba nominalow uzytych do wydania reszty cudzysłów plus resztaDoWydania plus cudzysłów dwukropek cudzysłów plus k zamknij nawias okrągły średnik. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy.

import java.util.Arrays;

public class ZachlanneWydawanieReszty {
    public static int zachlanneWydawanieReszty(int resztaDoWydania, int[] nominaly, int n) {
        int wynik = 0;

        for (int i = 0; i < n; i++) {
            int k = resztaDoWydania / nominaly[i];
            wynik = wynik + k;
            resztaDoWydania = resztaDoWydania % nominaly[i];

            System.out.println("Nominal " + nominaly[i] + " wydano " + k + " razy");
        }

        return wynik;
    }

    public static void main(String[] args) {
        int[] nominaly = { 50, 20, 10, 5, 2, 1 };
        int n = nominaly.length;
        int resztaDoWydania = 77;
        int k = zachlanneWydawanieReszty(resztaDoWydania, nominaly, n);

        System.out.println("Liczba nominalow uzytych do wydania reszty " + resztaDoWydania + ": " + k);
    }
}

Nie możemy zapomnieć o przypadku, w którym reszta będzie liczbą zmiennoprzecinkową. W Polsce do wydawania reszty po przecinku używamy nominałów 50 gr, 20 gr, 10 gr, 5 gr, 2 gr, 1 gr. W przypadku języka Java, podczas wydawania reszty, należy pamiętać o niedokładnościach w reprezentacji liczb zmiennoprzecinkowych. Operacje na takich liczbach powodują pewne niedokładności. Dlatego, aby nasze obliczenia były precyzyjne, najłatwiej jest zamienić wszystkie nominały na grosze. W takiej sytuacji resztę 19,99 zł zamienimy na 1999 gr, co pozwoli na łatwe i dokładne określenie minimalnej liczby monet lub banknotów potrzebnych do wydania reszty.

Słownik

algorytm zachłanny

algorytm dokonujący na każdym kroku takiego wyboru, który wydaje się w danym momencie najlepszy; zakładając, że seria wszystkich kroków doprowadzi do wyniku globalnie optymalnego

system monetarny

podział określonej waluty na nominały o określonej wartości

Wprowadzenie

Film samouczek

Implementacja algorytmu wydawania reszty w języku Java

Słownik