Przedziały liczbowe i liczby


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
  Podejście pierwsze
Podejście drugie

 

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 Z
b  – koniec przedziału, b Z, 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>, i Z

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

 

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 Z
b  – koniec przedziału, b Z, 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, i Z

Lista kroków:
K01: i ← pierwsza liczba w <a,b> spełniająca kryterium ; ustalamy początkową wartość
K02: Dopóki ib, wykonuj kroki K03...K04 ; tworzymy pętlę generującą wynikowe liczby w <a,b>
K03:     Pisz i ; wyprowadzamy liczbę spełniającą kryterium
K04:     inastępna liczba spełniająca 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.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.