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
©2023 mgr Jerzy Wałaszek
I LO w Tarnowie
|
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 |
©2023 mgr Jerzy Wałaszek
|
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.
| a | – | początek przedziału, a ∈ C. |
| b | – | koniec przedziału, b ∈ C, a < b. |
Liczby z przedziału [ a, b ], które spełniają zadane kryterium
| i | – | kolejne liczby w przedziale [ a, b ], i ∈ C. |
| K01: | Dla i = a, a + 1,
..., b : wykonuj: Jeśli i spełnia kryterium, to pisz i |
tworzymy pętlę
przechodzącą przez kolejne wartości w przedziale i testujemy kolejną liczbą. Jeśli spełnia kryterium, to przekazujemy ją na wyjście |
| 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 [ a, b ], która spełnia kryterium. Następnie w pętli sprawdzamy, czy wyznaczona liczba mieści się w przedziale [ a, b ]. Jeśli tak, przesyłamy ją na wyjście, po czym wyznaczamy kolejną liczbę i wracamy na początek pętli. Pętlę kontynuujemy, aż wygenerowana liczba wyjdzie poza przedział [ a, b ].
| a | – | początek przedziału, a ∈ C. |
| b | – | koniec przedziału, b ∈ C, a < b. |
Liczby z przedziału [ a, b ], które spełniają zadane kryterium.
i – liczby w przedziale [ a, b ] spełniające kryterium, i ∈ C.
| K01: | i ← pierwsza liczba w [
a, b ], która spełnia kryterium |
ustalamy początkową wartość |
| K02: | Dopóki i ≤ b, wykonuj kroki K03...K04 |
tworzymy pętlę generującą wynikowe liczby w <a, b> |
| K03: | Pisz i | wyprowadzamy liczbę spełniającą kryterium |
| K04: | i ←
następna liczba w [ a, b ], która spełnia kryterium |
wyznaczamy następną liczbę |
| 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 ©2023 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: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.