I_R_W14_M37_C++ Algorytmy zachłanne
Czy wiesz, że za każdym razem, kiedy wrzucasz do automatu monety, płacąc za kawę czy paczkę paluszków, maszyna staje przed nie lada problemem? Podobnie jest w przypadku wypłaty pieniędzy z bankomatu. Nie myślimy o tym zazwyczaj, ale nasza rzeczywistość często porządkowana jest przez świat algorytmów.
Jednym z najprostszych sposobów podejmowania decyzji w takich sytuacjach jest zasada „wybieraj to, co teraz wygląda najlepiej”. To podejście nazywamy algorytmem zachłannym. Nie analizuje on wszystkich możliwych rozwiązań, nie planuje daleko w przyszłość - po prostu na każdym kroku sięga po najbardziej obiecującą opcję.
Zaskakujące jest to, jak często taka prosta strategia działa znakomicie. W wielu urządzeniach, programach i usługach właśnie dzięki niej decyzje podejmowane są szybko, sprawnie i bez zbędnych obliczeń. W tym rozdziale zobaczysz, kiedy „zachłanność” się opłaca, a kiedy prowadzi na manowce, oraz poznasz algorytmy, które dzięki tej prostej idei stały się fundamentem współczesnej informatyki.
Ćwiczenia na rozgrzewkę
Symulacja interaktywna prezentuje wydawanie reszty zgodnie z algorytmem zachłannym. Wybierz kwotę i zastanów się, jaka jest minimalna liczba banknotów i monet potrzebnych, aby ją wydać. Następnie sprawdź swoje odpowiedzi w symulacji.
Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/D7R8MEAP2
Na samej górze symulacji widnieje napis:
Aby rozpocząć, wpisz kwotę do wydania (maksymalnie 3000 zł), a następnie wybierz „Wydaj”.
Poniżej znajduje się pole Kwota oraz przycisk Wydaj.
Przykład 1:
W pole kwota wypisano liczbę: 37.21.
Po kliknięciu przycisku Wydaj,
Przy napisie: Wydano, pojawiła się wartość 37.21 zł.
Przy napisie: Liczba wykorzystanych banknotów i monet, pojawiła się wartość 6.
Poniżej pojawiły się grafiki banknotów: 20 zł, 10 zł oraz monet: 5 zł, 2 zł, 50 gr, 1 gr.
Przykład 2:
W pole kwota wypisano liczbę: 1278.68 zł.
Po kliknięciu przycisku Wydaj,
Przy napisie wydano pojawiła się wartość 1278.68 zł.
Przy napisie Liczba wykorzystanych banknotów i motet pojawiła się wartość 13.
Poniżej pojawiły się grafiki banknotów: 500 zł, 500 zł, 200 zł, 50 zł, 20 zł oraz monet: 5 zł, 2 zł, 1 zł, 50 gr, 10 gr, 5 gr, 2 gr, 1 gr.
Wyjaśnisz, czym charakteryzują się algorytmy zachłanne.
Przeanalizujesz zagadnienie algorytmiczne, jakim jest problem wydawania reszty.
Zastosujesz podejście zachłanne przy rozwiązaniu problemów.
Wskażesz ograniczenia metody zachłannej oraz wyjaśnisz, dlaczego algorytmy zachłanne nie zawsze znajdują najlepsze rozwiązanie dla danego problemu.