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

Okazuje się, że dla niektórych kwot reszty program wyświetla błędne
 Dobra rada
Pamiętaj, że liczby wyniki – po zsumowaniu wartości monet brakuje 1 gr. Na przykład
przechowywane suma monet wyznaczonych przez program dla wartości 7.85 wynosi
są w komputerze 7.84 (rys. 4.4).
w postaci binarnej,
np. liczba 0,1 nie ma
skończonego rozwinięcia
dwójkowego, lecz
okresowe: 0,000(1100).
W konsekwencji
w zmiennej typu float
będzie zapisana wartość
przybliżona, trochę
większa od 0,1.

Rys. 4.4. Błędny wynik dla kwoty 7 zł 85 gr

Niedokładny rezultat nie wynika z błędu w algorytmie ani z zasto-
sowania podejścia zachłannego. Jest on skutkiem dodawania wartości
typu float, które są tylko przybliżeniami właściwych wartości. Obli-
czenia z wykorzystaniem tego typu zmiennoprzecinkowego są obar-
Błąd przybliżenia czone konsekwencjami błędów przybliżeń.
Nawet jeśli zwiększymy precyzję zapisu liczb przez zastosowanie
Typ double, typu double, nie uzyskamy poprawy. Dla kwoty 7.30 wyświetli się
s. 245  błędny wynik: 5, 2, 0.2, 0.05, 0.02, 0.02. Błąd jest rezultatem kumulo-
wania się przybliżeń.
Zauważ, że program Wydawanie reszty – choć wyświetla niepopraw-
ne rozwiązanie – kończy swoje działanie, nie zawiesza się. Zawdzię-
czamy to warunkowi i<N w warunku logicznym pętli while. Brak tego
zapisu spowoduje zapętlenie się programu na skutek pojawienia się
Pętla nieskończona tzw. pętli nieskończonej.

Ćwiczenie 5
 Dobra rada W pliku wydawanie_reszty.cpp utworzonym w poprzednim ćwi-
Aby zatrzymać działanie czeniu usuń w kodzie drugą część warunku logicznego, tj. i<N.
zapętlonego programu, Plik zapisz pod nazwą wydawanie_reszy_petla.cpp. Skompiluj kod
naciśnij kombinację
klawiszy Ctrl + C. i sprawdź działanie programu dla różnych wartości reszty, w tym dla
7.30, 7.79 i 7.85. Co obserwujesz?

Poprawiony kod źródłowy dla algorytmu wydawania reszty
Aby rozwiązać problem błędów przybliżeń, możemy zastosować
Typ int, typ całkowito liczbowy int i sprowadzić wszystkie kwoty reszty do
s. 245  wartości wyrażo nych w groszach.
Nominały 5 zł, 2 zł i 1 zł zapisane w groszach mają wartości odpo-
wiednio 500, 200, 100. Sformułujmy poprawioną specyfikację problemu
wydawania reszty.

68