Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Przedziały liczbowe i liczby

SPIS TREŚCI
Podrozdziały
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.

Podejście pierwsze

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.

Algorytm wyszukiwania liczb wg kryterium

Wejście:

a  –   początek przedziału, a  ∈ C.
b  – koniec przedziału, b ∈ C, a  < b.

Wyjście:

Liczby z przedziału [ a, b ], które spełniają zadane kryterium

Dane pomocnicze:

i  –   kolejne liczby w przedziale [ a, b ], ∈ C.

Lista kroków:

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  
Uwagi

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.

Na początek:  podrozdziału   strony 

Podejście drugie

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 ].

Algorytm wyznaczania liczb spełniających kryterium

Wejście:

a  –   początek przedziału, a  ∈ C.
b  – koniec przedziału, b  ∈ C, a < b.

Wyjście:

Liczby z przedziału [ a, b  ], które spełniają zadane kryterium.

Dane pomocnicze:

i  – liczby w przedziale [ a, b  ] spełniające kryterium,  ∈ C.

Lista kroków:

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  
Uwagi

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.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 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.