Podejście zachłanne (ang. greedy approach) to metoda algorytmiczna, która polega na podejmowaniu serii lokalnie optymalnych decyzji, z nadzieją, że doprowadzą one do globalnego optymalnego rozwiązania. Algorytm zachłanny na każdym kroku wybiera najlepsze (najkorzystniejsze) rozwiązanie na dany moment, nie zważając na konsekwencje w dalszych krokach.
W Pythonie, podejście zachłanne można zastosować do wielu problemów, takich jak znajdowanie minimalnych ścieżek w grafach, problem plecakowy, czy sortowanie przedmiotów. Poniżej przedstawię kilka prostych przykładów, które będą zrozumiałe dla uczniów szkoły średniej.
Przykład: Minimalizacja liczby kroków do zera
Załóżmy, że masz liczbę całkowitą. Twoim zadaniem jest zmniejszyć tę liczbę do zera, wykonując jak najmniej kroków. Na każdym kroku możesz albo odjąć 1, albo podzielić liczbę przez 2, jeśli jest parzysta. Algorytm zachłanny będzie dążył do jak najszybszego zmniejszenia liczby, dzieląc ją przez 2, kiedy tylko jest to możliwe.
Skrypt w języku Python:
Wyjaśnienie:
- Zaczynasz od liczby (np. 25) i dążysz do tego, by zmniejszyć ją do zera.
- Jeśli liczba jest parzysta, dzielisz ją przez 2, co zmniejsza liczbę szybciej.
- Jeśli liczba jest nieparzysta, musisz odjąć 1, aby ją „sparzystnić” i w kolejnym kroku móc ją podzielić przez 2.
- Na końcu wypisujemy liczbę kroków potrzebnych do osiągnięcia zera.
Wynik:
Dla przykładowej liczby 25: 7 kroków
W tym przypadku:
- 25 jest nieparzyste, więc odejmujemy 1 (pozostaje 24),
- 24 dzielimy przez 2 (pozostaje 12),
- 12 dzielimy przez 2 (pozostaje 6),
- 6 dzielimy przez 2 (pozostaje 3),
- 3 jest nieparzyste, więc odejmujemy 1 (pozostaje 2),
- 2 dzielimy przez 2 (pozostaje 1),
- 1 jest nieparzyste, więc odejmujemy 1 (pozostaje 0).
Podsumowanie
Podejście zachłanne jest prostą, lecz często skuteczną techniką rozwiązywania problemów, które można rozwiązać poprzez podejmowanie lokalnie optymalnych decyzji. Chociaż nie zawsze daje globalnie optymalne rozwiązania, to w wielu przypadkach jest wystarczająco dobre, a także szybkie w implementacji.
Was this helpful?
0 / 0