Stosowanie metody zachłannej i metody połowienia

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

Przypomnij sobie również temat „Wyszukiwanie elementów – liniowe i przez połowienie” z Materiału edukacyjnego.

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:

4. 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:

1. zapisuje za pomocą listy kroków lub pseudokodu, i implementuje w wybranym języku programowania, algorytmy poznane na wcześniejszych etapach oraz algorytmy:
        b) znajdowania określonego elementu w zbiorze uporządkowanym metodą binarnego wyszukiwania,
        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ą
3. Metoda binarnego wyszukiwania

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.

3. Metoda binarnego wyszukiwania

Do znajdowania określonego elementu w zbiorze uporządkowanym zastosujemy metodę binarnego wyszukiwania (zwaną także metodą połowienia).

W algorytmie znajdowania elementu w zbiorze uporządkowanym szukamy danego elementu i równocześnie jego położenia w tym zbiorze.

Załóżmy, że mamy zbiór dziesięciu liczb uporządkowany w kolejności od najmniejszej do największej (rys. 2.). Poszukiwana liczba to 44. Jeżeli w zbiorze jest kilka takich samych wartości, algorytm znajdzie pozycję jednego z tych elementów (nie jest określone, którego).

Dzielimy zbiór liczb na dwie części, rozdzielone środkowym elementem. Zaczynamy od sprawdzenia tego elementu (liczby zaznaczonej na rys. 2. strzałką). W przypadku, gdy liczba elementów zbioru jest parzysta, to spośród dwóch środkowych elementów (w naszym przypadku liczb 51 i 59) jako „środkowy” wybieramy ten, który jest pierwszy w kolejności (czyli 51). Jeśli środkowy element jest szukaną liczbą, kończymy wyszukiwanie. Jeśli środkowy element jest większy od poszukiwanej liczby, przeszukujemy podzbiór na lewo od elementu środkowego. Jeśli środkowy element jest mniejszy od poszukiwanej liczby, przeszukujemy podzbiór na prawo od elementu środkowego.

Ćwiczenie 5. Sprawdzamy działanie algorytmu znajdowania liczby w zbiorze uporządkowanym metodą binarnego wyszukiwania (połowienia)

1. Przygotuj odpowiednie pomoce dydaktyczne (rys. 2.) i przedstaw wspólnie z koleżankami i kolegami z klasy algorytm wyszukiwania liczby w zbiorze uporządkowanym metodą binarnego wyszukiwania (połowienia).
2. Przeprowadź analizę rozwiązania, tworząc i uzupełniając tabelę podobną do tabeli 1.
   Skorzystaj z rysunku 2. i podanego opisu algorytmu. Odpowiedz na pytania:
   1. Jakie powtarzające się operacje zauważasz w rozwiązaniu?
   2. Kiedy kończymy powtarzanie operacji połowienia zbioru?

Program realizujący algorytm znajdowania elementu w zbiorze uporządkowanym metodą binarnego wyszukiwania ma znajdować w zbiorze uporządkowanym daną podaną przez użytkownika i wyświetlać na ekranie jej pozycję (indeks) w tablicy lub liście. Zaczynamy od ustalenia, w jaki sposób będziemy pamiętać elementy zbioru. Elementy zbioru wprowadzimy do tablicy (C++) lub listy (Python). Zakładamy, że wprowadzamy dane od najmniejszej do największej (inaczej program nie będzie działał poprawnie). Bez takiego założenia należałoby dodać również funkcję sortowania danych (ustawiania w określonym porządku).

Przykład 3. Określenie zadania i jego specyfikacji

Zadanie: Wyszukaj dany element w uporządkowanym zbiorze N liczb, stosując metodę binarnego wyszukiwania (połowienia).

Dane: stała wartość N, tablica (lista) liczb a[N], szukana liczba wartosc.

Wynik: pozycja elementu srodek lub informacja, że elementu nie znaleziono.

Przykład 4. Definicja funkcji znajdowania elementu w zbiorze uporządkowanym metodą binarnego wyszukiwania (połowienia)

Zdefiniujemy funkcję znajdz_dana() z parametrem wartosc.

• W funkcji wyznaczamy pozycję elementu środkowego:
  
  srodek = (poczatek + koniec) / 2;

srodek = (poczatek + koniec) // 2
• Jeśli element środkowy (a[srodek]) jest szukaną daną (zmienna wartosc), to funkcja zwraca wartość zmiennej srodek, czyli pozycję danego elementu;
  w przeciwnym wypadku:
  • jeśli szukana dana jest mniejsza od środkowej, odrzucamy prawą połowę zbioru (liczby większe od elementu środkowego lub mu równe) – ustalamy nową wartość zmiennej koniec:
    koniec = srodek – 1
  • w przeciwnym wypadku odrzucamy lewą połowę zbioru (liczby mniejsze od elementu środkowego lub mu równe) i ustalamy nowy początek:
    poczatek = srodek + 1
• Połowienie powtarzamy, dopóki początek zbioru jest mniejszy od końca zbioru lub mu równy (poczatek <= koniec) – o ile wcześniej nie znajdziemy szukanego elementu (wtedy komputer wykona instrukcję return srodek).
• Jeśli w przeszukiwanym zbiorze nie ma szukanej liczby, funkcja znajdz_dana() zwraca wartość –1.

Ćwiczenie 6. Analizujemy realizację algorytmu wyszukiwania elementu w zbiorze uporządkowanym metodą binarnego wyszukiwania (połowienia) z wykorzystaniem funkcji znajdz_wzorzec()

1. Zapoznaj się z wybraną definicją funkcji (przykład 4.) i, korzystając z niej,przeprowadź analizę realizacji algorytmu wyszukiwania elementu w zbiorze uporządkowanym metodą binarnego wyszukiwania (połowienia) dla następującego zbioru liczb:{11, 23, 35, 44, 51}. Liczby pamiętane są w tablicy (liście) a[N], N = 5. Szukany element to liczba 23. Analizę funkcji wykonaj w tabeli (podobnej do tabeli 1.), pokazując dodatkowo, jak zmieniają się wartości poszczególnych zmiennych (poczatek, koniec, srodek).
2. Odpowiedz na pytania:
   1. Dlaczego w funkcji znajdz_dana() zastosowano instrukcję iteracyjną do … while (C++) lub while (Python)?
   2. Jakie wartości zwraca funkcja znajdz_dana()?
Wskazówka: W analizie funkcji może pomóc rysunek przedstawiający schematycznie algorytm znajdowania elementu w zbiorze uporządkowanym metodą połowienia(rys. 2.). Możesz wykonać podobny lub skorzystać z przygotowanych pomocy dydaktycznych.

Zgodnie z podaną specyfikacją, wynikiem działania programu realizującego algorytm wyszukiwania elementu w zbiorze uporządkowanym metodą binarnego wyszukiwania (połowienia)  ma być pozycja szukanego elementu (indeks tablicy lub listy) lub komunikat, że elementu nie znaleziono. W programie umieścimy funkcję wprowadzania danych do tablicy (listy) i wyprowadzania ich na ekran oraz funkcję wyszukującą dany element. Następnie wywołamy je w programie głównym, dodając odpowiednie komunikaty.

Ćwiczenie 7. Piszemy program realizujący algorytm znajdowania liczby w zbiorze uporządkowanym metodą binarnego wyszukiwania (połowienia) w języku C++ lub Python

1. Otwórz plik C5_c7_p4_Wyszukiwanie_binarne.cpp lub C5_c7_p4_Wyszukiwanie_binarne.py. Uzupełnij program o wywołanie funkcji w programie głównym. Wyprowadzaj na ekran odpowiednie komunikaty.
2. Zapisz program w pliku pod nazwą Wyszukiwanie_binarnei przetestuj działanie programu dla różnych danych (również dla różnej liczby danych). Pamiętaj o wprowadzaniu danych uporządkowanych.

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.
2. Wykonaj ćwiczenie 5. dla nieparzystej liczby elementów zbioru {13, 29, 35, 41, 57, 62,75, 81, 99}. Wykonaj analizę rozwiązania w tabeli podobnej do tabeli 2.
3. Przeprowadź analizę funkcji znajdz_dana() (z przykładu 4.) dla zbioru liczb {14, 20, 33, 78, 90, 101},gdzie szukany element to 90.
Dla zainteresowanych
4. 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.