Film samouczek
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?
Plik zawierający kod źródłowy programu ukazującego działanie algorytmu zachłannego.
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ą.
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.
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łę.
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.
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.
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.
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.
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 binarnychdrzew binarnych.
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: