Polecenie 1

Zapoznaj się z filmem przedstawiającym działanie algorytmu zachłannego wydawania reszty. Przetestuj działanie programu w nim zaprezentowanego dla różnych danych. Czy potrafisz znaleźć przykład, dla którego algorytm zachłanny nie jest najlepszym wyborem?

R14MDW0hFdER61
Film przedstawia algorytmy zachłanne w języku Java.
1

Plik zawierający kod źródłowy programu ukazującego działanie algorytmu zachłannego.

RbC4ZkSJBg0zf

Przycisk służy do pobrania pliku PDF z programem przedstawionym w powyższym filmie tłumaczącym działanie algorytmu zachłannego.

Działanie algorytmu zachłannego
Plik PDF o rozmiarze 53.56 KB w języku polskim
Linia 1. public class Zadanie otwórz nawias klamrowy. Linia 3. static int wydawanieReszty otwórz nawias okrągły int kwotaDoWydania przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy nominaly zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. int ileMonetWydamy znak równości 0 średnik. Linia 5. int pozostalaKwota znak równości kwotaDoWydania średnik. Linia 6. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny nominaly kropka lenght średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. int liczbaMonetNominalu znak równości pozostalaKwota prawy ukośnik nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 8. ileMonetWydamy znak równości ileMonetWydamy plus liczbaMonetNominalu średnik. Linia 9. pozostalaKwota znak równości pozostala Kwota minus otwórz nawias okrągły liczbaMonetNominalu asterysk nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 10. System kropka out kropka println otwórz nawias okrągły cudzysłów Nominal dwukropek cudzysłów plus nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy cudzysłów liczba monet nominalu dwukropek cudzysłów. Linia 11. plus liczbaMonetNominalu zamknij nawias okrągły średnik. Linia 12. zamknij nawias klamrowy. Linia 14. return ileMonetWydamy średnik. Linia 15. zamknij nawias klamrowy. Linia 17. public static void main otwórz nawias okrągły String args otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int kwotaDoWydania znak równości 21 średnik. Linia 19. int otwórz nawias kwadratowy zamknij nawias kwadratowy nominaly znak równości otwórz nawias klamrowy 5 przecinek 2 przecinek 1 zamknij nawias klamrowy średnik. Linia 21. int ileMonetWydamy znak równości wydawanieReszty otwórz nawias okrągły KwotaDoWydania przecinek nominaly zamknij nawias okrągły średnik. Linia 22. System kropka out kropka println otwórz nawias okrągły ileMonetWydamy zamknij nawias okrągły średnik. Linia 23. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy.
Polecenie 2

Ania chciałaby napisać program, który szukałby wśród dostępnych połączeń takich tras lotniczych, które pozwoliłyby pasażerowi na zebranie jak największej liczby mil lotniczych. Zastanawia się, jakie algorytmy powinna wykorzystać. Ktoś poradził jej, by spróbowała napisać program, w którym wykorzystałaby algorytm zachłanny.

Przygotuj symulację, która porówna wynik uzyskany po zastosowaniu algorytmu zachłannego z najlepszym wynikiem. Skorzystaj z przedstawionego przykładu. Dostępne połączenia zaznaczone zostały na mapie wraz z odległościami między miastami, które łączą.

Polecenie 2

Ania chciałaby napisać program, który szukałby wśród dostępnych połączeń takich tras lotniczych, które pozwoliłyby pasażerowi na zebranie jak największej liczby mil lotniczych. Zastanawia się, jakie algorytmy powinna wykorzystać. Ktoś poradził jej, by spróbowała napisać program, w którym wykorzystałaby algorytm zachłanny. Zapoznaj się z opisem ilustracji przedstawiającym połączenia tras lotniczych oraz odległości w milach między nimi., a także z wynikami umieszczonymi w tabeli oraz na wykresie.

RLhLRhcEKHEsU1
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
Ważne!

Kolejne odległości możesz do siebie dodawać, wykorzystując znak plusa (+). Kliknij dwukrotnie dowolną wartość w kolumnie wynik algorytmu zachłannego lub najlepszy wynik, by sprawdzić formułę.

1
1
Symulacja 1
RUZ7KOeaMnkF9
Ilustracja przedstawia wykres Symulacji dla trasy Mińsk- Madryt.
Ukazane są na nim algorytm zachłanny oraz algorytm optymalny.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ania wyniki obliczeń umieściła w tabeli oraz na wykresie. Tabela z wynikami prezentuje się następująco.

przystanek

wynik algorytmu zachłannego

najlepszy wynik

1

545

172

2

1062

565

3

1342

1082

4

2220

1335

5

3273

1859

6

3273

2436

7

3273

2866

8

3273

3919

Umieszczając dane z tabeli na wykresie liniowym o wartościach na osi y od zera do czterech tysięcy, a na osi x od zera do osiem. Dostajemy wykres,w którym w widoczne są dwa wykresy. Pierwszy z nich przedstawia wynik algorytmu zachłannego. Wykres ten od x równego zero do x równego sześć ma wartości rosnące, następnie wypłaszcza się uzyskując ostatecznie wartość y równą 3273.  Wykres ten aż do wartości x równej osiem i pół znajduje się ponad wykresem drugim. Drugi wykres przedstawia wartości wyniku najlepszego. Wykres jest liniowy i rosnący w całym swoim przedziale. Zatem w okolicach wartości x równej siedem i pół przecina się z wykresem przedstawiającym wyniki algorytmu zachłannego. Ostatecznie przyjmując wartość 3919.

1
1
Symulacja 2
R1Ztg7gpopyFC
Ilustracja przedstawia wykres Symulacji dla trasy Wilno- Rzym.
Ukazane są na nim algorytm zachłanny oraz algorytm optymalny.

Korzystając z informacji zawartych w opisie ilustracji przedstawiającym połączenia tras lotniczych oraz odległości w milach między nimi spróbuj dokonać własnych obliczeń przy użyciu algorytmu zachłannego, a następnie porównaj je z wynikami najlepszymi.

Polecenie 3
RNPYhQ9WaRstx
1
Polecenie 4

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.

R6o6oh3lEUZQO
Opis wyświetla się w trybie dostępności.
Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Opis wyświetla się w trybie dostępności.

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.

Ważne!

Zagadnienia z polecenia nr 4 dotyczą drzew binarnych, które wykraczają poza poziom podstawowy. Więcej na ich temat znajdziesz w e‑materiałach dotyczących drzew binarnychP1GgjGhGqdrzew binarnych.

Polecenie 5

Zapoznaj się z ilustracją i opisem algorytmu zachłannego znajdującego najdłuższą ścieżkę w ważonym drzewie binarnym. Odpowiedz na pytania.

Odległość między dwoma wierzchołkami drzewa binarnego reprezentowana jest przez wagę krawędzi między nimi. Odległości zapisano wewnątrz węzłów.

Algorytm ma na celu wskazanie kolejnych wierzchołków tworzących najdłuższą trasę w drzewie binarnym. W celu znalezienia ścieżki sprawdza on dystans do prawego i lewego sąsiada wierzchołka w drzewie, następnie wybiera wierzchołek, który znajduje się dalej od swojego poprzednika.

Zastanów się, czy podany algorytm poprawnie rozwiąże problem znalezienia najdłuższej trasy w drzewie.

Działanie algorytmu przedstawiono poniżej:

RheZLVVtm9Tj4
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
RALvhvvAvKYnd
Wyjaśnij, na jakiej zasadzie działa algorytm zachłanny. (Uzupełnij) Wskaż poprawne rozwiązanie. (Uzupełnij) Wyjaśnij, dlaczego algorytm zachłanny nie jest optymalnym wyborem w tym problemie. (Uzupełnij).
Polecenie 6
R1I9TmVf83nEN1