Aplet
Zapoznaj się z apletem, który przedstawia wyniki działania algorytmu zachłannego oraz takiego, który daje najlepsze wyniki dla podanych danych. Przetestuj działanie apletu dla różnych danych.
Przeanalizuj działanie apletu.
Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/D98sYINqg
Przeanalizuj działanie apletu.
Aplet przedstawia wynik działania algorytmu zachłannego oraz wynik optymalny dla różnych nominałów monet.
Przykład 1:
Dla nominałów: 1, 4, 5, 7.
W pole wartość reszty wpisano: 9.
Wynik algorytmu zachłannego to:
Liczba monet 3.
Monety: 7, 1, 1.
Suma: 9.
Wynik optymalny to:
Liczba monet: 2.
Monety: 5, 4.
Suma: 9.
Przykład 2:
Dla nominałów: 2, 3, 4, 5, 7, 9.
W pole wartość reszty wpisano: 15.
Wynik algorytmu zachłannego to:
Liczba monet: 2.
Monety: 9, 5.
Suma: 14.
Wynik optymalny:
Liczba monet: 3.
Monety: 9, 4, 2.
Suma: 15.
Zapisz swoją propozycję modyfikacji algorytmu przedstawionego w sekcji „Przeczytaj” tak, by wydawał również resztę w groszach. Do zapisania algorytmu wykorzystaj pseudokod.
Reszta do wydania będzie podana w złotych z groszami po przecinku, natomiast nominały tylko w groszach.
Specyfikacja problemu:
Dane:
resztaDoWydania– liczba wymierna dodatnia; wartość reszty do wydanian– liczba naturalna; liczba dostępnych nominałównominały– tablica liczb całkowitych dodatnich; tablica dostępnych nominałów w groszach, posortowana malejąco
Wynik:
komunikat dotyczący wykorzystanych nominałów
R1C1aAbpbkcsU