Stosowanie metody zachłannej do wydawania reszty

Wszystkie treści na stronie ir.migra.pl chronione są prawami autorskimi. Więcej informacji znajdziesz tutaj.

Zapisy podstawy programowej 2024 realizowane w temacie:

I. Rozumienie, analizowanie i rozwiązywanie problemów.
Zakres rozszerzony. Uczeń spełnia wymagania określone dla zakresu podstawowego, a ponadto:

2. do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych;

I + II. Zakres rozszerzony. Uczeń spełnia wymagania określone dla zakresu podstawowego, a ponadto:

3. objaśnia oraz porównuje podstawowe metody i techniki algorytmiczne oraz struktury danych, wykorzystując przykłady problemów i algorytmów, w szczególności:
         d) podejście zachłanne (do wydawania reszty, szukania najkrótszej drogi),

Spis treści

1. Opis algorytmu wydawania reszty
2. Programowanie algorytmu wydawania reszty metodą zachłanną

1. Opis algorytmu wydawania reszty

Algorytm zachłanny możemy wykorzystać w różnych sytuacjach. W tym temacie omówimy zastosowanie tej metody przy wydawaniu reszty.

Z problemem wydawania reszty spotkamy się wielokrotnie. Mimo że dziś częściej używamy kart płatniczych, to umiejętność obliczenia reszty przydaje się, nawet jeśli kasa podpowiada sprzedawcy, ile reszty ma wydać. Resztę wydajemy, używając jak najmniejszej liczby banknotów lub bilonu.

Ćwiczenie 1. Wydajemy resztę klientowi

1. Artykuł kosztował 457 zł. Klient dał trzy banknoty po 200 zł. Wyjaśnij, jak wydasz resztę klientowi.
2. Czy stosujesz algorytm zachłanny? Uzasadnij odpowiedź.

Metoda zachłanna zakłada użycie do wydania reszty największych dostępnych nominałów (mniejszych od lub równych wydawanej wartości). Zanim zaczniemy wydawać resztę, musimy określić dostępne nominały (zbiór nominałów).

Opis algorytmu

Algorytm zaczynamy od sprawdzenia, czy w zbiorze nominałów znajduje się wartość N mniejsza od reszty R lub jej równa.

Jeśli odnaleziony nominał N jest równy R, to algorytm się kończy. Jeśli nie, to wybieramy największą możliwą liczbę L sztuk znalezionego nominału N mniejszego od R (zakładamy, że zbiór nominałów jest posortowany malejąco). Liczbę tę otrzymujemy, dzieląc R przez wartość odnalezionego nominału (liczba nominałów to oczywiście część całkowita wyniku dzielenia).

Następnie od reszty R odejmujemy wartość znalezionego nominału pomnożoną przez liczbę nominałów wynikającą z dzielenia.

Szukanie powtarzamy wśród kolejnych nominałów dla pomniejszonej wartości R do czasu, aż wypłacimy całą sumę. Mamy tu więc odniesienie do iteracji.

Przykład 1. Zastosowanie metody zachłannej do wydawania reszty

Korzystając z podanego opisu, znajdziemy nominały, którymi zostanie wydana reszta w wysokości 69 zł.

Zbiór dostępnych nominałów to: {50, 20, 10, 5, 2, 1}.

Tabela 1. Przykładowa analiza rozwiązania – wzór tabeli do ćwiczenia 2.

Ćwiczenie 2. Sprawdzamy działanie algorytmu wydawania reszty metodą zachłanną

1. Przygotuj odpowiednie pomoce dydaktyczne i przedstaw wspólnie z koleżankami i kolegami z klasy algorytm wydawania reszty metodą zachłanną.
2. Przeprowadź analizę rozwiązania, tworząc i uzupełniając tabelę podobną do tabeli 1. Skorzystaj z podanego opisu algorytmu. Odpowiedz na pytania:
   • Jakie operacje powtarzają się w rozwiązaniu?
   • Jak ostatecznie wydano resztę?

2. Programowanie algorytmu wydawania reszty metodą zachłanną

Program realizujący algorytm wydawania reszty napiszemy zgodnie z podanym wcześniej opisem. Listę dostępnych nominałów umieścimy w tablicy (C++) lub w liście (Python), które należy zdefiniować następująco:

const int nominaly[] = {100, 50, 20, 10, 5, 2, 1};
const int l_nominalow = 7;

nominaly = [100, 50, 20, 10, 5, 2, 1]

Elementy tablicy lub listy powinny być posortowane malejąco. Program powinien wyświetlić dla obliczonej reszty wypłacone nominały, podobnie jak pokazano na rysunku 2.

Rys. 1. Przykład wyświetlania reszty w postaci wypłaconych nominałów

Przykład 2. Definiowanie funkcji realizującej algorytm wydawania reszty metodą zachłanną w językach C++ i Python

W zachłannym algorytmie wydawania reszty wykorzystujemy iterację. Szukanie nominału powtarzamy dla pomniejszonej wartości reszty wśród kolejnych nominałów, aż wypłacimy całą sumę – wykorzystamy instrukcję while.

Na rysunkach pokazano definicję funkcji znajdz_wypisz_reszte() w językach C++ i Python. Funkcja ma za zadanie wypisać na ekranie liczbę poszczególnych nominałów, niezbędnych do wydania reszty.

Przyjęto następujące oznaczenia dla zmiennych:

• aktualny_nominal – aktualnie sprawdzany nominał, czyli indeks nominału w tablicy (liście),
• reszta – reszta do wydania,
• l_nominalow – liczba wydawanych nominałów o wartości nominaly[aktualny_nominal].

Do obliczenia liczby banknotów należy zastosować:

• w języku C++ operator dzielenia /, którego działanie zależy od typu danych (w przypadku liczb całkowitych wynik również będzie całkowity),
• w języku Python – operator dzielenia całkowitego //.

Ćwiczenie 3. Analizujemy realizację algorytmu wydawania reszty metodą zachłanną z wykorzystaniem funkcji znajdz_wypisz_reszte()

1. Zapoznaj się z wybraną definicją funkcji i, korzystając z niej, przeprowadź analizę realizacji algorytmu wydawania reszty metodą zachłanną dla reszty równej 97. Analizę funkcji wykonaj w tabeli, pokazując dodatkowo, jak zmieniają się wartości poszczególnych zmiennych (m.in. reszta, l_banknotow, nominaly[aktualny_nominal]).
2. Objaśnij znaczenie poszczególnych instrukcji, odpowiadając na pytania:
   • Dlaczego w funkcji znajdz_wypisz_reszte() zastosowano instrukcję iteracyjną while?
   • Jaki warunek musi być spełniony, aby nastąpiło wyjście z pętli zewnętrznej while, a jaki z pętli wewnętrznej while?
   • Jakie instrukcje umieszczono w bloku instrukcji warunkowej if? Kiedy zostaną one wykonane?

Ćwiczenie 4. Piszemy program realizujący algorytm zachłanny wydawania reszty w języku C++ lub Python

1. Otwórz plik TC5_p2_Wydawanie_reszty.cpp lub plik TC5_p2_Wydawanie_reszty.py. W plikach zapisana jest funkcja znajdz_wypisz_reszte() – odpowiednio w językach C++ i Python. Aby napisać cały program realizujący algorytm zachłanny wydawania reszty, należy uzupełnić wskazane miejsca w kodzie. Przyjmij następujące nominały: {100, 50, 20, 10, 5, 2, 1}, które zapamiętaj w tablicy (liście), jak pokazano w tym temacie.
   • Zdefiniuj funkcję niezwracającą wartości wypisz_nominaly(), wyprowadzającą na ekran dostępne nominały.
   • W programie głównym wywołaj funkcję wypisz_nominaly(), wprowadź cenę (cena) i wpłaconą kwotę (wplata), oblicz wartość reszty (r) i wywołaj funkcję znajdz_wypisz_reszte() z parametrem aktualnym r. Wyprowadzaj na ekran odpowiednie komunikaty.
2. Zapisz program w pliku pod nazwą Wydawanie_reszty, a następnie przetestuj program dla kilku różnych danych.

Zadania

1. Musisz przewieźć określoną liczbę palet ładunku, którego nie można rozdzielać. Dysponujesz pojazdami o trzech różnych ładownościach. W wybranym języku programowania napisz program obliczający, ile i jakich samochodów należy użyć, aby jak najlepiej wykorzystać przestrzeń. Liczbę palet do przewiezienia, liczbę samochodów i ich ładowność wprowadzaj z klawiatury. Zapisz program w pliku pod nazwą Ladunek. Przetestuj program dla następujących danych: do przewiezienia jest 50 palet ładunku (którego nie możesz rozdzielać) i dysponujesz pojazdami o ładownościach: 20 palet, 8 palet i 1 paleta.
Dla zainteresowanych
2. Sformułuj samodzielnie problem, do którego rozwiązania można zastosować podejście zachłanne. Napisz program rozwiązujący ten problem. Zdefiniuj odpowiednie funkcje. Program zapisz w pliku pod nazwą Problem_zachlanny.