Implementacja - I_R_W14_M37_Java Algorytmy zachłanne

R1T11P5ZL3BNZ

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 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ł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 4. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. int k znak równości resztaDoWydania prawy ukośnik nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 6. wynik znak równości wynik plus k średnik. Linia 7. resztaDoWydania znak równości resztaDoWydania minus k asterysk nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 9. 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 10. zamknij nawias klamrowy. Linia 12. return wynik średnik. Linia 13. zamknij nawias klamrowy. Linia 15. 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 16. 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 17. int n znak równości nominaly kropka length średnik. Linia 18. int resztaDoWydania znak równości 77 średnik. Linia 19. 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 21. 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 22. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. 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 &lt; 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 6. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. int k znak równości resztaDoWydania prawy ukośnik nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 8. wynik znak równości wynik plus k średnik. Linia 9. resztaDoWydania znak równości resztaDoWydania procent nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 11. 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 12. zamknij nawias klamrowy. Linia 14. return wynik średnik. Linia 15. zamknij nawias klamrowy. Linia 17. 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 18. 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 19. int n znak równości nominaly kropka length średnik. Linia 20. int resztaDoWydania znak równości 77 średnik. Linia 21. 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 23. 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 24. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. 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 &lt; 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.

Eksperyment: zachłanny kontra optymalny

Strefa wyzwań

Implementacja algorytmu wydawania reszty w języku Java