Page 6 - Informatyka na czasie. Podejście zachłanne w rozwiązywaniu problemów. Podręcznik klasa 3

Rozdział 1. Algorytmika i programowanie w języku C++

Ćwiczenie 3

Wyobraź sobie, że korzystasz z automatu na dworcu kolejowym.
Z jakich monet składa się reszta, jeśli automat wydaje ją najmniejszą
możliwą liczbą monet, a ty płacisz banknotem 10 zł za zakup:
a. wody za 2,70 zł,
b. herbaty za 3,40 zł,
c. przekąski za 4,19 zł?
Zakładamy, że w automacie nie brakuje żadnych monet.

Napiszemy teraz program, który będzie wyznaczał nominały
potrzebne do wydania reszty. Przyjmijmy, że reszta jest kwotą mniej-
szą niż 10 zł. Będzie więc wydana wyłącznie z użyciem monet o nomi-
nałach: 5 zł, 2 zł, 1 zł, 0,50 zł, 0,20 zł, 0,10 zł, 0,05 zł, 0,02 zł i 0,01 zł.
Zapiszmy specyfi kację problemu.

Specyfikacja
Dane: kwota reszty do wydania – liczba z przedziału [0,01; 9,99];
tablica NOMINALY zawierająca uporządkowane malejąco liczby od 5
do 0,01, odpowiadające dostępnym nominałom.
Wynik: kolejne wartości nominałów potrzebnych do wydania reszty.

Algorytm wydawania reszty Zauważ, że przedstawiony na s. 65 algorytm wydawania reszty
Podejście zachłanne, (zwany niekiedy algorytmem kasjera) realizuje podejście zachłanne.
s. 63  Wybieramy największy nominał, który jest mniejszy lub równy kwocie
reszty, i wydajemy go tyle razy, ile można, aby nie przekroczyć tej kwoty.
Następnie wybieramy kolejny nominał i powtarzamy proces. Pamięta-
my przy tym, aby za każdym razem zmniejszać kwotę reszty.
Oto zapis algorytmu w postaci listy kroków:
1 Wczytaj kwotę reszty do wydania i zapisz ją w zmiennej reszta.
2 Ustaw na 0 wartość zmiennej i wskazującej komórkę tablicy
NOMINALY.
3 Dopóki reszta>0, wykonuj kolejno kroki 4 – 7 .
4 Jeśli reszta>=NOMINALY[i], to wykonaj kroki 5 i 6 .
5 Wypisz na ekranie wartość NOMINALY[i].
6 Pomniejsz wartość zmiennej reszta o wartość NOMINALY[i].
7 W przeciwnym przypadku zwiększ i o 1.
Zakładamy, że wartości groszowe będziemy wprowadzać do progra-
mu jako ułamki dziesiętne (stosujemy zapis z kropką zamiast przecin-
ka). Dlatego w kodzie źródłowym programu wykorzystamy typ zmien-
Typ float, noprzecinkowy, a dokładniej użyjemy zmiennych typu float.
s. 245  Oto kluczowy fragment kodu źródłowego programu Wydawanie
reszty, zawierający definicje zmiennych oraz funkcji WydajReszte.

66