VII. Algorytmy

Możliwość utworzenia w Visual Basic 2010 procedur oraz funkcji pozwala programiście wydzie -

lać z programu ciągi instrukcji, nadawać im nazwy i używać tych nazw aby wykonać określony ze-

staw działań. Umiejętność tworzenia kodu źródłowego, procedur, funkcji, definiowania nowych typów

i wykorzystywania innych elementów języka nie daje jednak pewności, że aplikacja będzie działać

zgodnie z założonym dla niej celem. Historia przekazuje nam informacje o sposobach skutecznego

działania. Opisy takich sekwencji działań prowadzących do określonego efektu nazywa się algoryt-

mami. Istnieją algorytmy dla działań bardzo prostych, jak również dla tych bardziej skomplikowanych.

Należy podkreślić, że dla danego zadania może istnieć więcej niż jeden algorytm.

Przykłady algorytmów.

Pracowite otrzymywanie dwójki.

1. Weź dowolna liczbę.

2. Dodaj do niej 6.

3. Wynik pomnóż przez 2.

4. Od iloczynu odejmij 8.

5. Różnicę podziel przez 2.

6. Iloraz pomniejsz o liczbę, którą wziąłeś w punkcie 1.

7. Wynikiem jest liczba 2.

Schemat Sarrusa – obliczanie wyznacznika macierzy.

1. Weź macierz kwadratową.

∣

a

11

a

12

a

13

a

21

a

22

a

23

a

31

a

32

a

33

∣

2. Dopisz, po prawej stronie macierzy, wszystkie kolumny z wyjątkiem ostatniej.

∣

a

11

a

12

a

13

a

21

a

22

a

23

a

31

a

32

a

33

∣

a

11

a

12

a

21

a

22

a

31

a

32

→

3. Poprowadź, od wyrazów pierwszego wiersza macierzy (pierwszy indeks – 1), przekątne

w prawo i w dół.

4. Poprowadź, od wyrazów ostatniego wiersza macierzy (pierwszy indeks – 3), przekątne w

prawo i w górę.

5. Utwórz sumę iloczynów wyrazów leżących na przekątnych, pamiętając, aby iloczyny wy-

nikające z przekątnych idących w prawo i w górę poprzedzić znakiem minus.

a11·a22·a33 + a12·a23·a31 + a13·a21·a32 + (-a13·a22·a31) + (-a11·a23·a32) + (-a12·a21·a33)

6. Oblicz wartość wyrażenia – wynik jest wyznacznikiem macierzy.

Nawet osoba, która nie ma pojęcia o znaczeniu wyznacznika, na podstawie powyższego algo-

rytmu potrafi obliczyć odpowiednia wartość. Warunkiem jest umiejętność mnożenia, dodawania i

odejmowania, ale… istnieją przecież algorytmy tych działań.

Algorytmy opisane powyżej, aby mogły być zastosowane w programie, muszą zostać przetłu-

maczone na język zrozumiały dla maszyny. Proces ten nazywa się implementacją. Można zatem po-

wiedzieć „implementuję algorytm obliczania symbolu Newtona”. Dodatkowo, otrzymany kod źródłowy,

również nosi nazwę implementacji. Można zatem użyć wyrażenia „ten kod to implementacja algoryt-

mu obliczania wyznacznika”.

Wiele algorytmów stosuje się bezwiednie. Przykładem jest obliczanie wartości towarów włożo-

nych do koszyka, gdy posiadamy ograniczoną ilość gotówki. Nie chcąc przekroczyć zasobności port-

fela sumujemy w pamięci ceny poszczególnych towarów, dodając do sumy wcześniej obliczonej cenę

następnego towaru. Jeśli koszyk jest pusty suma wynosi 0. Po dodaniu paczki ciastek suma zwięk-

sza się o wartość tej paczki np. z wartości 0 do wartości 4,50. Kilogram cukru ponownie zwiększa

sumę o jakąś kwotę – z 4,50 na 7,40.

Opisowo można przedstawić algorytm następująco:

1. Przyjmij, że wartość sumy wynosi zero.

2. Sprawdź, czy pozostały liczby do zsumowania i jeśli:

◦

tak, dodaj następną do sumy i przejdź do wykonywania punktu 2.,

◦

nie, to obliczanie sumy zostało zakończone.

Algorytm można przedstawić w postaci schematu blokowego używając kartki i ołówka, lub do-

wolnego programu.

Elementy schematu o kształcie prostokąta z zaokrąglonymi narożnikami wskazują miejsce roz-

poczęcia, lub zakończenia, algorytmu. Prostokąty symbolizują działania (operacje, przetwarzanie da-

nych). Romby pokazują miejsca podejmowania decyzji. Pochylone równoległoboki oznaczają wpro-

wadzanie danych, lub wyprowadzanie wyników. Schemat blokowy jest niezależny od języka progra-

mowania. Elementowi schematu odpowiada w każdym języku pewna konstrukcja programowa.

W III w. p.n.e. Euklides zebrał wiedzę z zakresu arytmetyki i geometrii tworząc „Elementy”. Dzie-

ło to zawiera opis metody odszukiwania największego wspólnego dzielnika dwóch liczb, której auto-

rem jest Eudoksos z Knidos. Metoda ta nosi nazwę algorytmu Euklidesa. Zapis algorytmu w postaci

schematu blokowego przedstawiony jest na następnej stronie.

Widać, że w schemacie występuje pętla (obszar otoczony niebieską linią). Kolejne ćwiczenie

polegać będzie na zaimplementowaniu algorytmu Euklidesa.

Ćwiczenie 79
W projekcie aplikacji konsolowej Projekt_079 zaimplementować schemat blokowy
algorytmu Euklidesa wykorzystując pętlę While. Do pobierania liczb a oraz b wykorzystać
procedurę PobierzLiczbę z modułu Moje_060 pochodzącego z projektu Projekt_063.

Przykładowy efekt działania programu przedstawia poniższy rysunek:

Algorytmy mogą wykorzystywać efekt działania innych algorytmów. Przykładem może być obli-

czanie najmniejszej, wspólnej wielokrotności dwóch liczb w oparciu o następujący algorytm:

Oblicz iloczyn podanych liczb całkowitych.

Podziel uzyskany iloczyn przez największy, wspólny podzielnik tych liczb, a otrzymasz naj-

mniejszą, wspólną wielokrotność danych wejściowych.

Kolejne ćwiczenie będzie polegać na „zamknięciu” algorytmu Euklidesa w funkcji i wykorzysta-

nie jej do obliczenia najmniejszej, wspólnej wielokrotności.

Rysunek 33: Algorytm Euklidesa - największy wspólny podzielnik.

Rysunek 34: Projekt_079 w działaniu.

Ćwiczenie 80
Dodać do modułu Moje_060 deklarację funkcji NajwiększyWspólnyPodzielnik o dwóch
parametrach typu Integer i wyniku typu Integer. Wartość wyniku funkcji powinna być
zgodna z jej nazwą. Wykorzystać zdefiniowaną funkcję do obliczenia najmniejszej,
wspólnej wielokrotności liczb podanych przez użytkownika.

Przykładowy efekt działania programu przedstawia poniższy rysunek:

Wśród różnorakich algorytmów istnieją dwie grupy, które towarzyszą człowiekowi od bardzo

dawna. Są to przeszukiwanie (poszukiwanie) i sortowanie.

VII.1.

Przeszukiwanie

Wróćmy do przykładu z zakupami. Wchodząc do sklepu zdajemy sobie sprawę z tego jaki towar

(ograniczmy się do jednego) jest nam potrzebny. Idąc wzdłuż półek porównujemy cechy mijanych

przedmiotów z tymi, jakie posiada poszukiwany przez nas towar. Jeśli porównanie wypadnie pozy-

tywnie, to odnaleziony towar wkładamy do koszyka.

Algorytm przeszukiwania można zapisać następująco:

1. Sprawdź czy pozostały jeszcze elementy do porównania i jeśli:

◦

nie, to przeszukiwanie zakończyło się porażką (nie odnaleziono pożądanego elemen-

tu),

◦

tak, porównaj cechy kolejnego elementu z zadanymi wartościami i jeśli:

▪

nie spełniają one określonych warunków, to przejdź do wykonywania punktu 1.,

▪

spełniają warunki, to przeszukiwanie zakończyło się sukcesem (odnaleziono po-

żądany element).

Schemat blokowy może wyglądać następująco:

Rysunek 35: Projekt_079 - NWD i NWW.

Należy zauważyć, że algorytm zawsze zwróci wynik, niezależnie od poszukiwanego elementu

i przeszukiwanego zbioru. Nawet jeśli zbiór zawiera elementy z kategorii, która nie posiada wspól-

nych cech z pożądanym elementem (poszukiwanie pralki w salonie samochodowym), otrzymamy wy-

nik w postaci słowa „Porażka”.

Pytanie o posiadanie pożądanych cech jest celowo niezbyt precyzyjne. Często uzyskanie odpo-

wiedzi wymaga oddzielnego algorytmu, zależnego od kategorii poszukiwanego elementu oraz szcze-

gólnych kryteriów.

Narzucającym się kryterium jest relacja równości. Chcąc zbudować kwadratowy latawiec łączy

się środki dwóch, jednakowej długości listewek, w taki sposób, aby listewki były wzajemnie prostopa-

dłe. Nie wchodząc w dalsze szczegóły algorytmu budowania kwadratowego latawca przyjrzyjmy się

następującej sytuacji. Osoba budująca latawiec wybrała jedną listewkę, która wydaje się jej idealna

na konstrukcję. Pozostaje znaleźć wśród innych listewek drugą o długości identycznej z pierwszą.

Zastosujmy algorytm. Najpierw pytamy, czy są inne listewki. Brak listewek kończy poszukiwa-

nia. Jeśli pozostały jeszcze listewki, to bierzemy jedną z nich i sprawdzamy, czy ma długość równą

pierwszej. Jeśli listewki są równe, to poszukiwanie jest zakończone, w przeciwnym przypadku wraca -

my do pierwszego pytania (Czy są inne listewki?).

Dalsze ćwiczenia polegać będą na przeszukiwaniu tablic liczb całkowitych. Aby nie zmuszać

ćwiczących do żmudnego wprowadzania tych liczb, w kolejnym ćwiczeniu zdefiniowana zostanie

funkcja generująca wartości losowe z przedziału o granicach podanych jako parametry funkcji. O pro-

cedurach i funkcjach związanych z liczbami losowymi była już mowa przy okazji ćwiczeń poprzednich

rozdziałów. Przypomnijmy, że aby otrzymać różne ciągi liczb losowych przy każdym uruchomieniu

aplikacji, konieczne jest zainicjowanie generatora liczb losowych procedurą Randomize. Natomiast

wartość losowa jest wynikiem funkcji Rnd.

Ćwiczenie 81
Utworzyć projekt aplikacji konsolowej i zdefiniować w dodanym do niego module
Moje_081 funkcję LiczbaLosowa typu Integer o dwóch, opcjonalnych parametrach typu
Integer: Minimum o wartości domyślnej równej 0 i Maksimum o wartości domyślnej
równej 100. Funkcja powinna zwracać losową liczbę całkowitą z przedziału <Minimum,
Maksimum> (odpowiedni wzór można znaleźć w komentarzu przed ćwiczeniem 39.).
Skompilować projekt.

Funkcja zostanie wykorzystana do generowania wartości losowych, które będą przechowywane

w tablicy. Wartości zapisane w tablicy będą symulować długości listewek wyrażone w centymetrach.

W kolejnym ćwiczeniu wygenerowana zostanie tablica liczb losowych, która będzie symulować li-

stewki.

Ćwiczenie 82
Przygotować tablicę symulującą listewki i wypełnić ją wartościami losowymi.

1. Dołącz do projektu Projekt_081 moduł Moje_060 (zawiera procedurę PobierzLiczbę).

2. Zaprogramuj w procedurze Main zainicjowanie generatora liczb losowych (Randomize).

3. Zadeklaruj tablicę intDługościListewek o czterdziestu komórkach typu Integer.

4. Skonstruuj pętlę For i zaprogramuj w niej przypisanie kolejnym komórkom tablicy intDłu-

gościListewek wartości losowych z przedziału <45, 60>, wykorzystaj funkcję LiczbaLoso-

wa z odpowiednimi parametrami.

„Listewki” są gotowe (jeśli ćwiczący ma ochotę obejrzeć zbiór wygenerowanych liczb, to może

samodzielnie wygenerować odpowiedni fragment kodu źródłowego). W następnym ćwiczeniu zaim-

plementowany zostanie algorytm poszukiwania listewki o długości równej wartości podanej przez

użytkownika.

Ćwiczenie 83
Zaimplementować algorytm przeszukiwania tablicy.

1. Dodaj po pętli For, utworzonej w poprzednim ćwiczeniu, komentarz: Implementacja algo-

rytmu przeszukiwania.

2. Zadeklaruj zmienną intPoszukiwanaDługość typu Integer i zaprogramuj pobranie jej war-

tości od użytkownika – wykorzystaj procedurę PobierzLiczbę, jako ograniczenia podaj

wartości 45 i 60.

3. Zadeklaruj zmienną intPozostałoListewek typu Integer o wartości początkowej 40.

Zmienna posłuży do przechowywania liczby listewek, które nie zostały jeszcze spraw-

dzone.

4. Skonstruuj pętlę While … End While, która będzie wykonywana tylko wtedy, gdy liczba

pozostałych do sprawdzenia listewek jest większa niż 0, a w niej:

◦

skonstruuj konstrukcję warunkową, która sprawdza czy komórka tablicy intDługościLi-

stewek o numerze wynikającym z wartości zmiennej intPozostałoListewek ma war-

tość równą zmiennej intPoszukiwanaDługość; w przypadku spełnienia warunku (co

oznacza odnalezienie poszukiwanej listewki) należy zaprogramować zakończenie pę-

tli While (Exit While),

Przykład.

If intDługościListewek(intPozostałoListewek - 1) = intPoszukiwanaDługość Then

Exit While

End If

◦

zaprogramuj, po słowach End If kończących konstrukcję warunkową, zmniejszenie o

1 wartości zmiennej intPozostałoListewek.

5. Zaprogramuj po pętli wyświetlenie komunikatu o sukcesie (lub porażce) przeszukiwania.

Konstrukcja warunkowa powinna sprawdzać wartość zmiennej intPozostałoListewek – je-

śli wartość zmiennej jest większa niż zero, to listewka została odnaleziona, w przeciw-

nym przypadku listewki nie odnaleziono.

Efekt wykonania programu może być podobny do przedstawionego na rysunku:

Aby uniknąć nieporozumień prześledzimy kod implementacji algorytmu:

W wierszu 10. została zadeklarowana zmienna intPoszukiwanaDługość, która służy do prze-

chowywania wartości (długości listewki wzorcowej) pobranej od użytkownika. W sposób naturalny

(charakterystyczny dla ludzi) zmienna intPozostałoListewek przechowuje liczbę listewek, które nie

zostały jeszcze zweryfikowane. Ponieważ, początkowo, żadna z czterdziestu listewek nie przeszła

procesu weryfikacji, wartością początkową zmiennej jest 40.

Pętla While służy do zorganizowania weryfikacji (potencjalnie) wszystkich czterdziestu listewek.

Przed zakończeniem pętli wartość zmiennej intPozostałoListewek jest zmniejszana o jedność, co

symbolizuje zmniejszanie się liczby listewek, które pozostały do zweryfikowania.

Rysunek 36: Projekt_081 w działaniu.

Rysunek 37: Instrukcje procedury Main w Projekt_081.

Weryfikacja (porównanie wartości) następuje w warunku konstrukcji If (wiersz 14). Wartość

przechowywana w komórce o numerze intPozostałoListewek-1 porównywana jest z wartością wzor-

cową. Numer komórki wynika z przyjętej konwencji przechowywania liczby pozostałych listewek – są

przechowywane w sposób naturalny, a indeksy komórek tabeli zaczynają się od 0 i kończą na 39.

Jeśli weryfikacja daje wynik pozytywny – wartość w komórce tablicy jest równa wartości wzorco-

wej – to jest natychmiast przerywana (Exit While).

Wyjaśnienia wymaga jedynie konstrukcja warunkowa (wiersze 19-23). Logika tej konstrukcji jest

następująca. Jeśli żadna z wartości przechowywanych w tablicy nie jest równa wartości wzorcowej,

to pętla zakończy się wtedy, gdy wartość zmiennej intPozostałoListewek osiągnie zero. Zatem zero-

wa wartość tej zmiennej oznacza porażkę. Wartość większa niż zero oznacza sukces.

Przeszukiwanie posiada dwojakie zastosowanie. Po pierwsze, pozwala przekonać się,

że w zbiorze istnieje poszukiwana wartość. Po drugie, dla zbiorów indeksowanych (a takimi są tabli -

ce), umożliwia także odpowiedź na pytanie: jeśli poszukiwana wartość znajduje się w zbiorze, to pod

którym numerem (indeksem). Drugi aspekt jest o tyle istotny, że informacja o numerze indeksu jest

jednocześnie informacją o tym, że wartość została odnaleziona. Zasadę tą implementuje wiele metod

przeszukujących, w ten sposób, że zwracają indeks wartości odnalezionej w tablicy, lub wartość -1,

nie będącą dozwolonym numerem indeksu. Zatem wartość -1 oznacza porażkę przeszukiwania. Idea

ta zostanie zaimplementowana w kolejnym ćwiczeniu.

Ćwiczenie 84
Zdefiniować w module Moje_081 funkcję Przeszukaj typu Integer o dwóch parametrach.
Pierwszy parametr typu tablica o komórkach typu Integer oraz drugi typu Integer.
Funkcja powinna poszukiwać w tablicy przekazanej jako parametr wartości drugiego
parametru i zwracać jako wynik indeks, pod którym znajduje się odnaleziona wartość, a
w przypadku porażki liczbę -1.

1. Zdefiniuj w module Moje_081 blok funkcji Przeszukaj. Pamiętaj, że definiując parametr

typu tablicowego, nie ustala się rozmiaru tablicy.

Przykład.

Function Przeszukaj(ByVal Tablica() As Integer, ByVal Wzorzec As Integer) As Integer

2. Zadeklaruj zmienną intPozostło typu Integer o wartości początkowej równej maksymalne-

mu indeksowi tablicy przekazanej jako pierwszy parametr.

Przykład.

Dim intPozostało As Integer = UBound(Tablica)

3. Skonstruuj pętlę While wykonywaną tak długo, jak długo wartość zmiennej intPozostało

jest nieujemna (równa zeru, lub większa niż zero).

4. Skonstruuj instrukcję warunkową sprawdzającą czy komórka tablicy o indeksie równym

wartości zmiennej intPozostało jest równa wartości drugiego parametru funkcji.

5. Zaprogramuj w konstrukcji warunkowej wyjście z pętli While (jeśli warunek jest

spełniony).

6. Zaprogramuj po zakończeniu konstrukcji warunkowej zmniejszenie o jeden wartości

zmiennej intPozostało.

7. Zaprogramuj po pętli zwrócenie jako wyniku funkcji wartości zmiennej intPozostało.

8. Zastanów się nad tym, jakie wartości może zwrócić funkcja w przypadku gdy „Wzorzec”

zostanie odnaleziony w tablicy, a jaką w przeciwnym przypadku.

9. Wykorzystaj funkcję Przeszukaj w procedurze Main.

Aplikacja działa tak, jak poprzednio, ale kod źródłowy procedury Main uległ znacznemu skróce-

niu. Ponadto użycie funkcji Przeszukaj, ze względu na jej nazwę, powoduje poprawę czytelności

kodu:

Porażka przeszukiwania oznacza, że latawiec nie zostanie zbudowany.

Każdy, kto kiedykolwiek potrzebował dwóch równych listewek, powie, że „można przecież przy-

ciąć (skrócić) jedną z dłuższych listewek”. To prawda. Stwierdzenie takie prowadzi do kolejnego kry-

terium – poszukiwana listewka nie może być krótsza niż pierwsza (wzorcowa). Kryterium można za -

pisać słowami – jeśli weryfikowana listewka nie jest krótsza niż wzorcowa, to spełnia warunek, albo

wyrażeniem porównania:

PorównywanaListewka >= ListewkaWzorcowa

Wygodnie byłoby wykorzystać istniejącą deklarację funkcji Przeszukaj, która sprawdza już kry-

terium równości, dodając do niej fragment kodu weryfikującego fakt, że listewka jest dłuższa

niż wzorcowa. Nie chcąc tracić nic z użyteczności funkcji Przeszukaj, w kolejnym ćwiczeniu dodamy

do jej deklaracji opcjonalny parametr, który będzie przekazywał informację o tym, który warunek nale-

ży sprawdzać – „=”, czy „>=”.

Ćwiczenie 85
Dodać do funkcji Przeszukaj możliwość poszukiwania w tablicy indeksu komórki
przechowującej wartość nie mniejszą niż wzorcowa.

1. Zdefiniuj w module Moje_081 enumerację Kryteria o elementach: Równe, Niemniejsze.

2. Dodaj, do nagłówka funkcji Przeszukaj, trzeci, opcjonalny parametr Kryterium typu Kryte-

ria o wartości domyślnej Kryteria.Równe.

Rysunek 38: Wykorzystanie funkcji Przeszukaj.

3. Dodaj po słowach End If, kończących konstrukcję warunkową utworzoną w ćwiczeniu

84., nową konstrukcję warunkową, która sprawdza czy wartością parametru Kryterium

jest Kryteria.Niemniejsze.

4. Dodaj wewnątrz konstrukcji warunkowej utworzonej w poprzednim punkcie konstrukcję

warunkową sprawdzającą czy wartość przechowywana w komórce o indeksie intPozo-

stało jest większa niż wartość drugiego parametru.

5. Zaprogramuj wyjście z pętli While jeśli warunek konstrukcji If utworzonej w poprzednim

punkcie jest spełniony.

6. Dodaj w procedurze Main fragment kodu wykorzystujący do przeszukiwania procedurę

Przeszukaj z wartością trzeciego parametru równą Kryteria.Niemniejsze.

Efekt działania aplikacji może być taki, jak na rysunku:

Ponieważ funkcja sprawdza tablicę „od końca” (od najwyższego indeksu), to okazało się, że li-

stewka dłuższa niż 47 cm znajduje się w komórce o indeksie 39.

Wnikliwy obserwator zauważy, że odnaleziona listewka – nie krótsza od wzorca – może być

od wzorca dużo dłuższa. „Odpad” będący efektem skracania zbyt długiej listewki może być dłuższy

lub krótszy. Załóżmy, że odpad powinien być najkrótszy z możliwych. Oznacza to, że chcemy odna-

leźć wśród listewek listewkę tylko minimalnie dłuższą od wzorcowej.

Postulat zgłoszony w poprzednim akapicie prowadzi do kolejnego zagadnienia przeszukiwania.

Poszukiwanie wartości ekstremalnej (minimum, maksimum)

Przykłady (nie zawsze oczywiste) poszukiwania wartości ekstremalnych można długo wymie-

niać: wybory najpiękniejszej/najprzystojniejszego, zawody pływackie, rozgrywki ligowe piłki nożnej,

poszukiwanie najkrótszej (najdłuższej) listewki… Załóżmy, że zbiór zawiera wartość ekstremalną. Dla

ustalenia uwagi powiedzmy, że poszukujemy minimum. Przyjmujemy zatem, że w zbiorze występuje

wartość, od której pozostałe wartości nie są mniejsze. Jest oczywiste, że na początku poszukiwania

którakolwiek wartość ze zbioru może być tą minimalną. W takim razie, w pierwszym kroku zakłada-

my, że to pierwsza wartość w zbiorze, jest minimalna. Jeśli pierwsza wartość jest jedyną wartością

w zbiorze, to właśnie ona pozostanie minimalną. Prowadzi to do drugiego kroku. Należy sprawdzić,

czy w zbiorze pozostały jeszcze jakieś wartości. Jeśli zostały, to powstaje pytanie. Co zrobić jeśli dru-

ga wartość w zbiorze jest mniejsza niż ta aktualnie najmniejsza (minimalna)? Należy to sprawdzić

Rysunek 39: Wykorzystanie funkcji Przeszukaj z parametrem wskazującym kryterium.

i w przypadku, gdy druga wartość jest mniejsza, właśnie tą wartość należy przyjąć jako minimum

i oczywiście powrócić do drugiego kroku.

Algorytm powyższy można przedstawić w postaci schematu blokowego:

Poszukiwanie wartości minimalnej zastąpiono tu poszukiwaniem indeksu tej wartości. Łatwo za-

uważyć, że zastąpienie znaku „<”, w rombie decyzyjnym w dolnej części schematu, znakiem „>” jest

równoznaczne z zamianą algorytmu poszukiwania minimum w algorytm poszukiwania maksimum.

Aby nie mnożyć ćwiczeń realizujących podobne zagadnienia, w kolejnym ćwiczeniu zostaną zbudo-

wane funkcje Minimum i Maksimum zwracające indeks komórki tablicy zawierającej, odpowiednio,

minimalną lub maksymalną wartość. Tablica będzie jedynym parametrem funkcji.

Ćwiczenie 86
Zaimplementować algorytmy poszukiwania wartości minimalnej i maksymalnej w
funkcjach modułu Moje_081.

1. Utwórz blok funkcji Minimum typu Integer o parametrze typu tablica o komórkach typu In-

teger.

2. Zadeklaruj zmienną intIndeksMinimum typu Integer o wartości początkowej 0.

3. Skonstruuj pętlę For o zmiennej sterującej zmieniającej się od 1 do wartości maksymal-

nego indeksu tablicy przekazanej jako parametr funkcji (UBound).

4. Skonstruuj wewnątrz pętli For konstrukcję warunkową, która sprawdza, czy komórka ta-

blicy o indeksie równym zmiennej sterującej pętlą ma wartość mniejszą niż komórka o in-

deksie intIndeksMinimum.

5. Zaprogramuj przypisanie zmiennej intIndeksMinimum wartości zmiennej sterującej pętlą

jeśli warunek konstrukcji If jest spełniony.

6. Zaprogramuj po zakończeniu pętli przekazanie wartości intIndeksMinimum jako wyniku

funkcji.

7. Zdefiniuj w podobny sposób funkcję Maksimum, pamiętając o zmianie kierunku znaku

w warunku konstrukcji warunkowej.

8. Użyj obu funkcji w procedurze Main do wyznaczenia najkrótszej i najdłuższej listewki.

Efekt działania programu może być taki, jak na rysunku:

Skoro wiadomo już jak poszukiwać ekstremum powróćmy do budowniczego latawców. Przypo-

mnijmy, że chce on znaleźć listewkę, której długość jest większa od długości listewki wzorcowej o

najmniejszą wartość. Pierwszym krokiem do osiągnięcia celu wydaje się obliczenie różnic pomiędzy

długością każdej listewki w zbiorze, a długością listewki wzorcowej i zapisanie ich w tablicy. Niestety

tablica taka będzie zawierać oprócz nieujemnych wartości, dla których chcemy znaleźć minimum,

również ujemne, które nas nie interesują. Należy zatem zmodyfikować funkcję poszukującą minimum

tak, aby „brała pod uwagę” jedynie wartości nieujemne. Kolejne ćwiczenie polegać będzie na zdefi -

niowaniu odpowiedniej funkcji poszukującej minimum z wartości nieujemnych.

Ćwiczenie 87
Zaprogramować wyszukiwanie minimum z wartości nieujemnych.

1. Zadeklaruj w procedurze Main tablicę intRóżnice o czterdziestu komórkach typu Integer i

zaprogramuj obliczenie różnic pomiędzy wartościami przechowywanymi w tablicy intDłu-

gościListewek, a wartością zmiennej intPoszukiwanaDługość.

2. Zdefiniuj, w module Moje_081, funkcję NieujemneMinimum o jednym parametrze typu ta-

blica o komórkach typu Integer, która zwróci jako wynik indeks tej komórki parametru,

której nieujemna wartość jest minimalna.

3. Wykorzystaj w procedurze Main funkcję NieujemneMinimum do odnalezienia listewki mi-

nimalnie dłuższej od wzorcowej.

Efekt działania programu może być podobny do przedstawionego na rysunku:

Warto zauważyć, że nie została odnaleziona listewka o długości równej listewce wzorcowej

(45 cm). Są listewki dłuższe (np. ta o indeksie 14), ale te, które są „najmniej dłuższe” mają 46 cm dłu-

gości. Jedna z nich to ta o indeksie 6.

Wskazówka. W pierwszym kroku należy odnaleźć indeks jakiejkolwiek nieujemnej różnicy dłu-

gości. Następnie należy poszukiwać indeksu takiej nieujemnej różnicy, która jest mniejsza niż aktual-

nie minimalna.

Warunki przeszukiwania można mnożyć, za każdym razem trzeba adaptować ogólny algorytm

przeszukiwania. Do samodzielnego opracowania pozostawia się ćwiczącym następujący problem „li-

stewkowy”. Konstruktor latawca nie upiera się przy długości wzorcowej. Natomiast nie znosi zbyt du-

żych odpadów. W związku z tym podjął decyzję, że może skrócić listewkę wzorcową, jeśli zminimali-

zuje to wielkość odpadu. Oznacza to, że odnaleziona listewka może być równa wzorcowej, dłuższa,

lub krótsza od niej, ale różnica pomiędzy listewkami musi być możliwie najmniejsza. Wskazówka. Na-

leży poszukiwać minimum wartości bezwzględnej (Math.Abs) obliczonych wcześniej różnic.

Jeśli wartości w zbiorze występują w przypadkowej kolejności, to przeszukiwanie może wyma-

gać (w najgorszym przypadku) sprawdzenia wszystkich wartości. Sytuacja zmienia się jeśli wartości

są uporządkowane (np. rosnąco). W takim przypadku można zastosować algorytm przeszukiwania

binarnego. Wykorzystuje on uporządkowanie zbioru.

Przeszukiwanie binarne

Zanim przejdziemy do objaśnienia przeszukiwania binarnego przygotujemy uporządkowany ro-

snąco zbiór wartości losowych. Wykorzystamy w tym celu funkcję LiczbaLosowa w taki sposób, że

każda następna liczba losowana będzie z przedziału wyznaczonego przez wartość przechowywaną

w poprzedniej komórce i tą samą wartość powiększoną o 20. W ten sposób żadna następna liczba

nie będzie mniejsza od poprzedniej.

Przykład, zakłada się, że instrukcja znajduje się w pętli o zmiennej sterującej intLicznik.

intUporządkowany(intLicznik) = LiczbaLosowa(intUporządkowany(intLicznik - 1), _
intUporządkowany(intLicznik - 1) + 20)

Należy tylko zadbać o wylosowanie pierwszej wartości (intUporządkowany(0)). Innym sposo-

bem jest dodawanie liczby losowej do poprzedniej wartości w tablicy. Kolejne ćwiczenie poświęcone

jest generowaniu tablicy wartości losowych uporządkowanych niemalejąco.

Ćwiczenie 88
Przygotować tablicę wartości losowych uporządkowanych niemalejąco.

1. Utwórz projekt aplikacji konsolowej i dodaj do niej moduły: Moje_060 i Moje_081.

2. Zadeklaruj w procedurze Main tablicę intUporządkowany o 40. komórkach typu Integer.

3. Przypisz pierwszej komórce tablicy wartość losową z przedziału <0, 20>.

4. Skonstruuj pętlę, w której kolejnym komórkom zostaną przypisane wartości losowe. Po-

służ się przykładem podanym przed ćwiczeniem, lub innym, wybranym przez siebie, spo-

sobem.

Ćwiczący powinien samodzielnie przekonać się, że wartości tablicy tworzą niemalejący ciąg

liczb, np. wyświetlając je w konsoli.

Kiedy wygenerowaliśmy już uporządkowany zbiór liczb całkowitych chcemy zastosować do jego

przeszukiwania algorytm oparty o podział zbioru na dwie części i przeszukiwanie tylko tej z nich,

w której może znajdować się poszukiwana wartość. Indeks elementu dzielącego zbiór na dwie części

znajdziemy jako część całkowitą z dzielenia sumy pierwszego i ostatniego indeksu w zbiorze.

Przykład.

intIndeksŚrodkowy = (intIndeksPierwszy + intIndeksOstatni) \ 2

Słowo „środkowy” zostało tu użyte umownie.

Wartość przechowywana pod tym indeksem może być równa wartości poszukiwanej, wtedy

osiągnęliśmy sukces w przeszukiwaniu.

W przeciwnym razie, możliwe są trzy przypadki. Po pierwsze, indeks „środkowy” równy jest

„ostatniemu”. Łatwo sprawdzić, że oznacza to, iż „pierwszy” i „ostatni” indeks były sobie równe, czyli

sprawdzaliśmy nie przedział liczb, a tylko jedną liczbę. Skoro nie jest ona równa poszukiwanej, to

przeszukiwanie zakończyło się porażką. Po drugie, liczba przechowywana pod indeksem „środko-

wym” jest większa niż poszukiwana. Z faktu, że liczby są uporządkowane niemalejąco wynika, iż po-

szukiwaną liczbę można znaleźć tylko w komórkach przedziału leżącego po lewej stronie od „środko-

wej”. Należy zatem przeszukiwać zbiór danych przechowywanych w komórkach o indeksach z prze-

działu <intIndeksPierwszy, intIndeksŚrodkowy – 1>. Po trzecie, liczba przechowywana pod indeksem

„środkowym” jest mniejsza niż poszukiwana. Wychodząc z tych samych przesłanek, jak w drugim

przypadku, dochodzimy do wniosku, że należy przeszukiwać komórki o indeksach <intIndeksŚrodko-

wy + 1, intIndeksOstatni>.

Należy zauważyć, że podział taki korzystnie wpływa na liczbę wykonywanych porównań. Każdy

kolejny podział zmniejsza liczbę pozostałych do przeszukania komórek o „połowę”.

Ponieważ każdy następny krok przeszukiwania jest podobny do pierwszego i występują dwa

przypadki elementarne, kończące przeszukiwanie:

intUporządkowany(intIndeksŚrodkowy) = intPoszukiwanaWartość ' Sukces
intIndeksŚrodkowy = intIndeksOstatni ' Porażka

to nasuwa się przypuszczenie, że można zastosować rekurencję. Kolejne ćwiczenie polegać będzie

na zdefiniowaniu rekurencyjnej funkcji przeszukującej binarnie uporządkowany niemalejąco zbiór

wartości.

Ćwiczenie 89
Zdefiniować w module Moje_081 rekurencyjną funkcję PrzeszukajBinarnie typu Integer
o czterech parametrach. Pierwszy to (przeszukiwana) tablica o komórkach typu Integer,
drugi (poszukiwana wartość), trzeci (pierwszy indeks) i czwarty (ostatni indeks) typu
Integer. Funkcja powinna implementować algorytm przeszukiwania binarnego i zwracać
indeks odnalezionej komórki, lub -1 w przypadku porażki.

1. Zdefiniuj w module Moje_081 blok funkcji PrzeszukajBinarnie.

2. Zadeklaruj zmienną intIndeksŚrodkowy typu Integer o wartości początkowej obliczonej

jako część całkowita z dzielenia, sumy czwartego i trzeciego parametru (ostatniego i

pierwszego indeksu), przez 2.

3. Utwórz konstrukcję warunkową (trzy warunki), która sprawdza, czy:

◦

wartość przechowywana w komórce o indeksie intIndeksŚrodkowy jest równa drugie-

mu parametrowi funkcji (poszukiwanej wartości), a jeśli tak, to zwraca jako wynik war-

tość zmiennej intIndeksŚrodkowy,

◦

wartość intIndeksŚrodkowy jest równa wartości czwartego parametru (ostatni indeks),

a jeśli tak, to zwraca jako wynik wartość -1 (nie odnaleziono wartości),

◦

wartość przechowywana w komórce o indeksie intIndeksŚrodkowy jest większa niż

wartość drugiego parametru funkcji, a jeśli tak, to zwraca wynik funkcji PrzeszukajBi-

narnie wywołanej z odpowiednimi wartościami trzeciego i czwartego parametru (po-

szukiwanie „po lewej”),

◦

jeśli nie zachodzi żadne z powyższych trzech, to zwraca wynik funkcji PrzeszukajBi-

narnie wywołanej z odpowiednimi wartościami trzeciego i czwartego parametru (po-

szukiwanie „po prawej”).

4. Zaprogramuj w procedurze Main pobranie od użytkownika poszukiwanej wartości oraz

wyświetlenie informacji o wyniku poszukiwań.

Efekt działania programu może być podobny do przedstawionego na rysunku:

Przykład implementacji przedstawia poniższy rysunek:

Algorytm można przystosować także dla zbiorów uporządkowanych nierosnąco, ale można rów-

nież wykorzystać istniejący algorytm, tworząc wcześniej zbiór o elementach ułożonych w odwrotnej

kolejności niż w pierwotnym zbiorze. Utworzony zbiór, zgodnie z założeniem algorytmu, uporządko-

wany jest niemalejąco i może być przeszukiwany funkcją PrzeszukajBinarnie.

Zbiór uporządkowany niemalejąco uzyskaliśmy w ćwiczeniach stosując w odpowiedni sposób

funkcję LiczbaLosowa. Jednak można takie zbiory otrzymywać poprzez przetworzenie zbioru o przy-

padkowym (nieuporządkowanym) rozkładzie elementów. Prowadzi nas to do kolejnego zagadnienia.

VII.2.

Sortowanie

Sortowanie to operacja polegająca na wprowadzaniu porządku w pewnym zbiorze. W zbiorach

liczbowych porządek ten określa odpowiednia relacja, która zachodzi między elementami. Przykłado-

wo, jeśli pomiędzy każdymi dwoma kolejnymi elementami zbioru liczbowego zachodzi relacja więk -

szości:

a

i

> a

i+1

to mówimy, że zbiór uporządkowany jest malejąco. Jeśli zastąpimy znak „>” przez „<”, to zbiór, w któ-

rym zachowana jest taka relacja, uporządkowany jest rosnąco.

Dla skupienia uwagi pozostaniemy przy uporządkowaniu niemalejącym, to znaczy takim, w któ-

rym każde dwa kolejne elementy zbioru spełniają relację a

i

<= a

i+1

. Chcąc uzyskać taki zbiór, ze zbio-

ru nieuporządkowanego, musimy doprowadzić do sytuacji, w której wspomniana relacja jest spełnio-

na. Narzuca się rozwiązanie polegające na porządkowaniu par sąsiadujących elementów zbioru tak

długo, aż wszystkie będą spełniały relację porządkującą. Co oznacza termin „porządkowanie par”?

Rysunek 40: Jeden z przykładów implementacji algorytmu przeszukiwania binarnego.

Jeśli dwie wartości nie spełniają relacji, to zamieniając je miejscami otrzymamy parę uporządkowaną

w pożądany sposób.

Przykład.

3, 2 ‘ nie spełnia warunku 3 <= 2
2, 3 ‘ spełnia warunek 2 <= 3 – para jest uporządkowana niemalejąco

Ponieważ porządkowanie par jest ważnym elementem sortowania, to w kolejnym ćwiczeniu

zdefiniowana zostanie procedura implementująca zamianę miejscami dwóch liczb całkowitych.

Ćwiczenie 90
Zdefiniować procedurę Przestaw o dwóch parametrach typu Integer przekazywanych
przez referencję.

1. Utwórz projekt aplikacji konsolowej i dodaj do niej moduł Moje_081.

2. Zdefiniuj w module Moje_081 blok procedury Przestaw.

3. Zadeklaruj zmienną intPrzechowalnia typu Integer i przypisz jej wartość pierwszego pa-

rametru procedury.

4. Przypisz pierwszemu parametrowi procedury wartość drugiego parametru.

5. Przypisz drugiemu parametrowi wartość zmiennej intPrzechowalnia.

6. Skompiluj projekt.

Procedura Przestaw powoduje zamianę wartości zmiennych. Będzie ona przydatna do imple-

mentacji algorytmu sortowania. Z pewnością algorytm musi zacząć swoją pracę od pierwszej pary

komórek tablicy nieuporządkowanej.

5, 3

, 2, 4

Jeśli ich wartości nie spełniają wymaganej relacji, to należy je przestawić.

3

,

5, 2

, 4

Następnie porównujemy drugą i trzecią komórkę i jeśli nie spełniają relacji, to należy je przesta -

wić.

3, 2

, 5, 4

Jednak w tym momencie może się okazać, że pierwsza i druga komórka nie spełniają relacji.

W związku z tym po każdej zamianie należałoby rozpocząć sprawdzanie od początku (od pierwszej

pary).

2, 3

, 5, 4 → 2, 3, 4, 5

Ostatnia para, to komórka przedostatnia i ostatnia.

Uwzględniając powyższe uwagi algorytm można przedstawić w postaci schematu blokowego:

Algorytm nie jest zbyt wyrafinowany. Dane z początku zbioru są sprawdzane wielokrotnie, na-

wet wtedy, gdy zostały już uporządkowane. Kolejne ćwiczenie polega na implementacji algorytmu

w postaci procedury.

Ćwiczenie 91
Zaimplementować algorytm sortowania w procedurze Sortuj.

1. Utwórz w module Moje_081 blok procedury Sortuj z jednym parametrem, typu tablicowe-

go o komórkach typu Integer, przekazywanym przez referencję.

2. „Przetłumacz” (zaimplementuj) schemat blokowy przedstawiony na rysunku na kod źró-

dłowy procedury Sortuj. Wykorzystaj procedurę Przestaw.

3. Zadeklaruj w procedurze Main tablicę o elementach typu Integer

4. Zaprogramuj wypełnienie tablicy liczbami losowymi.

5. Zaprogramuj wyświetlenie elementów tablicy.

6. Zaprogramuj sortowanie tablicy i wyświetlenie jej elementów.

Rysunek 41: Schemat blokowy sortowania.

Efekt działania programu może być podobny do przedstawionego na rysunku:

Przyjrzyjmy się następującej sytuacji początkowej:

1, 4, 5, 3, 2

Para 5, 3 jako pierwsza zostanie przestawiona, co doprowadzi do następującego układu:

1, 4, 3, 5, 2

Algorytm przedstawiony na schemacie blokowym ponownie rozpocznie sprawdzanie od pierw-

szej pary (1, 4), która jest już uporządkowana. Wydaje się, że jest to „strata czasu”. Być może wy-

starczyłoby sprawdzić „wstecz”, czy przestawiona przed chwilą 3 spełnia relację uporządkowania

z liczbą poprzedzającą, czyli 4. Jeśli porządek jest zachowany, to z faktu, że relacja „<=” jest prze -

chodnia:

a

1

≤

a

2

∧

a

2

≤

a

3

⇒

a

1

≤

a

3

wynika, że porządek jest zachowany od początku, aż do czwartego elementu zbioru (5). Jeśli

porządek nie jest zachowany (tak, jak w przykładzie), to należy przestawić nieuporządkowaną parę i

sprawdzać „wstecz” uporządkowanie, aż do chwili, gdy natrafi się na parę uporządkowaną. Moment

ten oznacza, że wszystkie pary, aż do czwartego elementu (5) są uporządkowane, można zatem dal-

sze sprawdzanie prowadzić od tego właśnie elementu. Oznacza to, że algorytm powinien „pamiętać”

miejsce zbioru, w którym, przy porządkowaniu „do przodu” nastąpiło przestawienie.

Receptura działa jak wahadło. Algorytm przesuwa się przez zbiór w kierunku od początku

do końca i jeśli napotka na nieuporządkowaną parę, to przestawia ją i sprawdza wstecz, czy przesta-

wienie spowodowało utratę uporządkowania tej części zbioru, która była wcześniej uporządkowana.

Jeśli uporządkowanie zostanie przywrócone, to algorytm nie rozpoczyna od początku, tylko od miej-

sca, w którym zostało przerwane porządkowanie „do przodu”.

Schemat blokowy przedstawia rysunek na następnej stronie.

Widać, że modyfikacja polega na dodaniu, w gałęzi przestawiającej elementy zbioru, pętli reali-

zującej porządkowanie wsteczne. Kolejne ćwiczenie polega na implementacji algorytmu w postaci

procedury.

Ćwiczenie 92
Utworzyć procedurę SortujSzybciej implementującą zmodyfikowany algorytm.

1. Utwórz kopię procedury Sortuj i zmień jej nazwę na SortujSzybciej.

2. Zadeklaruj konieczne zmienne i zmodyfikuj kod zgodnie ze schematem blokowym.

Rysunek 42: Algorytm sortowania ze sprawdzaniem uporządkowania wstecz.

3. Zastąp w procedurze Main wywołanie procedury Sortuj wywołaniem procedury Sortuj-

Szybciej.

Obie procedury sortują dane prawidłowo. Sprawdzenie różnicy pomiędzy czasami sortowania

obu procedur pozostawia się ćwiczącym jako zadanie do samodzielnego wykonania.

Jednym z ciekawych rozwiązań problemu sortowania jest grupa algorytmów znanych pod

wspólną nazwą QuickSort (albo QSort). Kolejne ćwiczenia poświęcone będą zapoznaniu się z tą me-

todą.

Załóżmy przez chwilę, że istnieje pewna szybka metoda sortowania np. procedura o nazwie

QS, która jako parametry przyjmuje tablicę i dwa indeksy, ograniczające z dołu i z góry część tablicy

do posortowania. Wywołanie metody mogłoby wyglądać następująco:

QS(Tablica, IndeksPoczątkowy, IndeksKońcowy)

Załóżmy następnie, że tablica (nieposortowana) posiada pewien porządek. Polega on na tym,

że występuje w tablicy komórka, o której wiemy z pewnością, że w komórkach o niższych indeksach

są wartości mniejsze, a w komórkach o indeksach wyższych – większe. Na rysunku przedstawiono

przykład takiej sytuacji:

3

5

1

2

6

10

8

7

9

Jeśli szybka metoda QS posortuje pierwsze cztery komórki, a następnie ostatnie cztery komór-

ki, to cała tablica będzie posortowana. W tym przypadku problem sortowania 9 elementów został za-

stąpiony dwoma polegającymi na posortowaniu 4 elementów (każdy).

Pozostaje tylko odpowiedzieć na pytanie, jak uzyskać założone uporządkowanie. Każda meto-

da prowadząca do tego celu tworzy nowy algorytm z rodziny QSort. Odnajdywanie elementu (nazwij-

my go „środkowym”) samo w sobie byłoby problemem bardziej czasochłonnym niż sortowanie.

Jeden ze sposobów polega na wskazaniu dowolnej komórki jako środkowej, a następnie prze-

stawieniu wszystkich wartości mniejszych „na lewo”, a większych „na prawo”. Przestawianie realizo-

wane jest bez dodatkowych ograniczeń.

Skoro można wskazać, jako środkową, dowolną wartość, załóżmy, że pierwsza komórka taką

właśnie wartość zawiera. Pozostaje teraz przestawić wszystkie wartości mniejsze przed tą komórkę.

Zauważmy, że wartościami większymi nie ma potrzeby się zajmować, gdyż ostatecznie pozostaną

one po prawej stronie. Pytanie tylko, jak tego dokonać. Odpowiedź jest oczywista. Należy porówny-

wać wartości wszystkich komórek z wartością środkową i jeśli są mniejsze przestawiać je na lewą

stronę tablicy.

Zobaczmy jak to działa na przykładzie tablicy pokazanej wcześniej:

3

5

1

2

6

10

8

7

9

Zakładamy, że pierwsza komórka zawiera wartość nazwaną umownie „środkową” (można ją na-

zwać „dzielącą”, ale najczęściej używa się określenia „osiową” – ang. pivot oznacza oś). Sprawdza -

my kolejną wartość – 5, która jest większa niż 3, zatem pozostaje na swoim miejscu. Kolejna jest je -

dynka. Jest ona mniejsza niż 3, dlatego przestawiamy ją z liczbą 5:

3

1

5

2

6

10

8

7

9

Podobnie z dwójką:

3

1

2

5

6

10

8

7

9

Dalsze przeglądanie nie powoduje żadnych przestawień. Wiemy, że tylko dwie liczby są mniej-

sze niż „środkowa”, dlatego przestawiamy środkową na trzecie miejsce:

2

1

3

5

6

10

8

7

9

Uzyskaliśmy pożądane ustawienie, do lewej i prawej części tablicy stosujemy procedurę QS. Al-

gorytm, można przedstawić następująco:

Liczby 0, 1, 3 i 8 w wywołaniach metody QS oznaczają indeksy ograniczające lewą część tabli -

cy (0, 1) i prawą część tablicy – (3, 8).

Do tej pory zakładaliśmy, że istnieje metoda QS, która zostanie wykorzystana do posortowania

fragmentu tablicy. Teraz ustalimy, że jest to metoda, której schemat blokowy narysowano powyżej.

Widać wyraźnie, że procedura zamienia się w procedurę rekurencyjną. Potrzebny jest zatem

warunek zakończenia procedury. Wydaje się on oczywisty – nie trzeba sortować pojedynczego ele-

mentu, jeśli zatem parametr drugi jest równy trzeciemu, to należy zakończyć procedurę. Dodajmy ten

warunek do schematu blokowego (patrz: kolejna strona).

Rysunek 43: Pojedynczy krok metody QuickSort.

LewyPoczątkowy i LewyKońcowy, to indeksy początkowy i końcowy lewej części tablicy (po

ustawieniu), a PrawyPoczątkowy i PrawyKońcowy – prawej strony. Pozostaje jeszcze przedstawić

schemat blokowy części opisanej jako Ustaw(Tablica). Ustawieniu podlega każdorazowo część tabli-

cy ograniczona indeksami: IndeksPoczątkowy i IndeksKońcowy.

Przypisanie zmiennej IndeksŚrodkowy wartości IndeksPoczątkowy oznacza, że zakładamy po-

czątkowo, iż wszystkie wartości w tablicy są większe niż „środkowa”.

Rysunek 44: Algorytm QuickSort.

Rysunek 45: Jedna z wersji metody Ustaw

dla algorytmu QuickSort.

Dalej następuje pętla, w której sprawdza się czy kolejne wartości (aż do IndeksKońcowy) są

mniejsze niż „środkowa” i jeśli tak, to przyszłe położenie wartości środkowej przesuwa się „w prawo”

(inkrementacja zmiennej IndeksŚrodkowy). W to miejsce wędruje sprawdzona wartość. Po zakończe-

niu pętli, przestawia się wartość z komórki przeznaczonej na wartość środkową do pierwszej komórki

zakresu (IndeksPoczątkowy), a wartość środkowa (przechowywana do tej pory w pierwszej komórce)

wędruje na przeznaczone dla niej miejsce.

Mając rozrysowane oba algorytmy przystąpimy w kolejnym ćwiczeniu do implementacji tego al-

gorytmu.

Ćwiczenie 93
Zaimplementować omówiony algorytm w postaci procedury QuickSort.

1. Zdefiniuj w module Moje_081 procedurę QuickSort opierając się na przedstawionych

schematach blokowych.

2. Porównaj czasy sortowania dwóch identycznych tablic przez procedurę SortujSzybciej i

procedurę QuickSort.

VII.3.

Zastosowania

Przyjrzyjmy się tabeli wartości funkcji kwadratowej dla pewnego zbioru argumentów:

x

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

2x

2

+3x-2

-2 -1,68 -1,32 -0,92 -0,48

0

0,52

1,08

1,68

2,32

Chcąc zaprezentować wszystkie punkty na wykresie, a jednocześnie nie kreślić wykresu o zbyt

dużych wymiarach, musimy odpowiednio dobrać skalę układu współrzędnych i wartość przesunięcia

jego początku. Pierwszy rzut oka na tabelę pozwala ocenić, że oś 0x powinna pozwalać na umiesz -

czenie na wykresie wartości z przedziału <0, 0,9>, a oś 0y - <-2, 2,32>. „Rzut oka” to jedno z najlep-

szych narzędzi człowieka, program komputerowy musi przeanalizować dane w inny sposób. Powi-

nien odnaleźć wartości minimalne i maksymalne obu zbiorów, a następnie tak przeskalować wykres,

aby wszystkie punkty mogły się na nim znaleźć. Rysunek przedstawia wykres „przygotowany” przez

arkusz kalkulacyjny.

2x

2

+3x-2

-2,5

-2

-1,5

-1

-0,5

0

0,5

1

1,5

2

2,5

3

0

0,2

0,4

0,6

0,8

1

Na czym polega skalowanie? Załóżmy, że niezależnie od przyjętych jednostek, wykres ma za-

wsze wysokość równą 1. Oznacza to, że odległość pomiędzy najmniejszą, a największą wartością y

musi również wynieść 1. Wartości pośrednie między minimalną a maksymalną, trzeba tak przetwo-

rzyć, aby mieściły się we wskazanym zakresie. Przyjmijmy, że przeskalowanej wartości y odpowiada

wartość y

p

. Można przy takim założeniu napisać proporcję:

y

p

1

=

y− y

min

y

max

−

y

min

⇒

y

p

=

y− y

min

y

max

−

y

min

Łatwo sprawdzić, że prowadzi to do wartości 0 dla y=y

min

oraz 1 dla y=y

max

. Ponadto, jeśli przyj-

miemy, że wykres ma mieć wysokość 50, to wystarczy pomnożyć przeskalowane wartości przez tą

liczbę.

Kolejne ćwiczenie będzie polegać na przygotowaniu tablicy z wartościami funkcji y=3x

2

+2x-1,

przy tym, aby nie komplikować problemu, przyjmiemy sztywne założenie, że argumenty x to liczby

całkowite z przedziału <0, 60>. Pozwoli to zatrudnić algorytm jedynie do odszukania najmniejszej i

największej wartości funkcji.

Ćwiczenie 94
Wykorzystać algorytm poszukiwania ekstremum do odnalezienia wartości przydatnych
do skalowania wykresu.

1. Utwórz nowy projekt aplikacji konsolowej. Jeśli uznasz, że niektóre metody zdefiniowane

wcześniej (w innych projektach) będą przydatne, to dodaj do projektu odpowiednie mo-

duły.

2. Zdefiniuj funkcję Trójmian typu Double o czterech parametrach: x, a, b, c zwracającą

wartość obliczoną według wzoru ax

2

+bx+c.

3. Zadeklaruj zmienne do przechowywania współczynników a, b, c i zaprogramuj pobiera-

nie ich wartości od użytkownika.

4. Zadeklaruj tablicę o 61 komórkach typu Double i zaprogramuj wypełnienie jej wartościa-

mi funkcji Trójmian (x zmienia się od 0 do 60).

5. Zdefiniuj funkcję Minimum odnajdującą indeks minimalnej wartości przechowywanej w

tablicy o komórkach typu Double (jeśli korzystasz z modułów, przeciąż istniejącą funkcję

odnajdującą indeks minimalnej wartości w tablicy o komórkach typu Integer).

6. Zdefiniuj funkcję Maksimum – uwagi, jak w poprzednim punkcie.

7. Zadeklaruj zmienne do przechowywania indeksów komórek zawierających minimalną

(maksymalną) wartość i wyznacz je.

8. Zadeklaruj tablicę o 61 komórkach typu Double i przeskaluj obliczone wcześniej wartości

przyjmując, że wykres ma wysokość 15 jednostek.

9. Przedstaw obliczone wartości w postaci wykresu zbudowanego ze znaku „*”.

Efekt działania programu może być podobny do przedstawionego poniżej:

Rysunek 46: Projekt_094 w działaniu.