Symulacja interaktywna
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/DdkkggtaJ
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.
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ą.
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łę.
Ukazane są na nim algorytm zachłanny oraz algorytm optymalny.
Ukazane są na nim algorytm zachłanny oraz algorytm optymalny.
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:
