Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
W tym dziale zajmujemy się problemami wyszukiwania liczb, które spełniają pewne kryteria. Znalezione liczby mogą być później wykorzystywane w charakterze danych wejściowych dla algorytmów wyższego poziomu. Istnieją zasadniczo dwa podejścia do rozwiązania problemu.
Metoda brutalna (ang. brutal force) polega na przejściu przez wszystkie wartości w danym przedziale liczbowym i sprawdzeniu każdej z nich, czy spełnia wymagane kryterium. Jeśli tak, to znaleziona liczba jest przekazywana na wyjście.
K01: Dla i = a, a+1, …, b : wykonuj krok K03 K03: Jeśli i spełnia kryterium, to pisz i K02: Zakończ
Podejście brutalne stosujemy zwykle w początkowej fazie projektowania algorytmu. Jeśli kryterium nie zależy od ilości liczb w przedziale, to metoda posiada klasę czasowej złożoności obliczeniowej równą O(n). Zaletą jest prostota algorytmu. Wadą jest konieczność testowania wszystkich liczb w przedziale.
Jeśli postać kryterium pozwala nam przewidzieć, obliczyć wartości, które go spełniają, możemy zastosować inne rozwiązanie:
Wyznaczamy pierwszą liczbę w przedziale
K01: i ← pierwsza liczba w przedziale <a, b>, która spełnia kryterium K02: Dopóki i ≤ b: ;tworzymy pętlę generującą wynikowe liczby w <a, b> wykonuj kroki K03…K04 K03: Pisz i ;wyprowadzamy liczbę spełniającą kryterium K04: i ← następna liczba w <a, b>, która spełnia kryterium K05: Zakończ
Takie podejście pozwala nam wyeliminować puste przebiegi pętli – wykonuje się ona tylko tyle razy, ile jest potrzebne na wygenerowanie liczb spełniających kryterium. W efekcie algorytm działa dużo szybciej. W pewnych sytuacjach możemy nawet obniżyć klasę czasowej złożoności obliczeniowej poniżej O(n). Wadą rozwiązania jest konieczność analizy problemu, co czasami może być bardzo trudne.
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.