Page 10 - 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++

Definicja funkcji WydajReszte (linie 5–17) jest podobna do poprzed-
niej, jednak funkcja operuje już na liczbach całkowitych.
Przy wypisywaniu wartości potrzebnych monet (linia 12) podajemy
 Warto wiedzieć
Oprogramowanie wynik w postaci liczb niecałkowitych (w złotówkach). Typ niecałkowi-
stosowane w bankach ty jest wymuszony przez zastosowanie dzielenia przez wartość 100.0,
i innych instytucjach a nie przez 100.
finansowych również Przykładowe wywołanie programu pokazuje rysunek 4.5.
wykonuje obliczenia
na liczbach całkowitych.

Rys. 4.5. Wywołanie programu wydawanie_reszty_2.exe dla kwoty 8 zł 30 gr

Ćwiczenie 6
 Warto wiedzieć a. Zapisz kod programu w pliku wydawanie_reszty_2.cpp. Skom-
Dopiero w 2009 r. został piluj kod i uruchom program dla kilku różnych kwot reszty, np.
opublikowany artykuł
naukowy wyjaśniający, 7 zł 30 gr, 7 zł 85 gr.
jak sprawdzić, czy dla b. Zmodyfikuj kod programu tak, aby można było do niego wprowa-
danego zbioru nominałów dzać kwotę reszty większą niż 10 zł, a resztę można było wydawać
algorytm zachłanny
na pewno znajdzie z użyciem monet i banknotów.
rozwiązanie optymalne
niezależnie od wydawanej
kwoty. Autorami artykułu Optymalność zachłannego algorytmu wydawania reszty jest ściśle
było dwoje Polaków: związana ze zbiorem dostępnych nominałów. Można sobie wyobrazić
Anna Adamaszek fikcyjny system monetarny, np. o nominałach 25, 10, 1, dla którego algo-
i Michał Adamaszek.
rytm zachłanny nie znajduje optymalnego rozwiązania. Na przykład dla
reszty 30 otrzymamy sumę 25 + 1 + 1 + 1 + 1 + 1 zamiast 10 + 10 + 10.
Ten przykład wystarcza, aby stwierdzić, że w ogólnym przypadku
wydawanie reszty metodą zachłanną nie musi prowadzić do uzyskania
Rozwiązanie optymalne, rozwiązania optymalnego.
s. 63 

 A to ciekawe

Systemy monetarne a wydawanie reszty

Systemy monetarne wielu krajów są tak skonstruowane, aby
metoda zachłanna działała w nich optymalnie, tzn. żeby można było
wydać resztę najmniejszą liczbą banknotów i monet. Polski system
monetarny jest zbudowany na bazie liczb: 5, 2, 1. Wartości
banknotów i monet są wielokrotnościami tych liczb.

70