Page 28 - informatyka 8

1.5 Wybrane sposoby wyszukiwania i sortowania elementów w zbiorze

Podejmij temat O O Odszyfruj hasło, czytając tylko wielkie litery. Jak rozumiesz to wypowiedzenie?
P d O g R h Z j Ą k D o K e O r W h A j N k I g E o Z y B j I m O n R a U
W y E b D n Ł i U s G d K v L f U r C w Z e A

W życiu codziennym często czegoś lub kogoś szukamy, np. najwyższego ucznia
w klasie, zielonego pisaka w piórniku, określonego wyrazu w słowniku, banknotu
o najwyższym nominale. Można powiedzieć, że w różnych zbiorach wyszukujemy
elementy wyróżniające się ze względu na określoną cechę, np. wysokość, kolor,
kolejność, wartość.
Zbiór wyrazów w słowniku jest uporządkowany w kolejności alfabetycznej.
Odnalezienie w nim określonego wyrazu jest prostą czynnością. W zbiorach
nieuporządkowanych należy sprawdzić kolejno każdy element i porównać go
z innymi, biorąc pod uwagę określoną cechę. Taki sposób szukania nazywamy
przeszukiwaniem liniowym. Często porównujemy wartości liczbowe elemen-
Przeszukiwanie liniowe –
sprawdzenie każdego elementu tów, np. wzrost mierzony w centymetrach, nominał banknotu – w złotówkach.
zbioru. Wartości elementów określamy jako dane.

1. Przeanalizujcie w parach opis danych i wyników oraz listę kroków wyszukiwania minimalnego (najmniejszego) ele-
mentu w zbiorze. Przetestujcie opisany algorytm na zbiorze wybranych siedmiu liczb naturalnych.

Dane: Liczba naturalna n i zbiór n liczb a 1 , a 2 , ..., a n .
Wynik: Najmniejsza spośród liczb a 1 , a 2 , ..., a n – oznaczona jako min.
Krok 1. Przyjmij za min pierwszy element w zbiorze (przypisz min := a 1 ).
Krok 2. Dla kolejnych elementów a i , gdzie i = 2, 3, ..., n,
jeśli a i jest mniejsze niż min, to za min przyjmij a i (jeśli a 1 < min, to przypisz min := a i ).

2. W podobny sposób przedstawcie wyszukiwanie maksymalnego (największego) elementu w zbiorze. Zapiszcie pracę
w edytorze tekstu i udostępnijcie plik nauczycielowi.
3. Przeanalizuj opis algorytmu wyszukiwania numeru strony w książce. Czy jest to algorytm iteracyjny? Uzasadnij swą
odpowiedź.

Opis algorytmu wyszukiwania numeru strony w książce (czyli uporządkowanym zbiorze stron)

Otwórz książkę na dowolnej stronie. Sprawdź, czy jest to numer strony, którego szukasz. Jeśli nie, szukaj dalej
1. (jeśli poszukiwany numer strony jest wyższy niż ten na otwartej stronie, to szukaj w dalszej części książki, jeśli nie
– szukaj na wcześniejszych stronach).

Otwórz wybraną część książki. Sprawdź, czy jest to numer strony, którego szukasz. Jeśli nie, szukaj dalej
2. (jeśli poszukiwany numer strony jest wyższy niż ten na otwartej stronie, to szukaj w dalszej części książki, jeśli nie
– szukaj na wcześniejszych stronach, które jeszcze nie zostały sprawdzone).

3. Ponownie otwórz wybraną część książki. Wykonuj powyższe czynności tak długo, aż odnajdziesz właściwą stronę.

26