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 z
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. Wez
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. Wez
macierz kwadratowÄ….
a11 a12 a13
a21 a22 a23
#" #"
a31 a32 a33
2. Dopisz, po prawej stronie macierzy, wszystkie kolumny z wyjÄ…tkiem ostatniej.
a11 a12 a13 a11 a12
a21 a22 a23 a21 a22
#" #"
a31 a32 a33 a31 a32
3. Poprowadz
, od wyrazów pierwszego wiersza macierzy (pierwszy indeks  1), przekątne
w prawo i w dół.
4. Poprowadz
, 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 z
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. Sprawdz
, czy pozostały liczby do zsumowania i jeśli:
ć% tak, dodaj następną do sumy i przejdz
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.
Rysunek 33: Algorytm Euklidesa - największy wspólny podzielnik.
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:
Rysunek 34: Projekt_079 w działaniu.
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.
Ć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:
Rysunek 35: Projekt_079 - NWD i NWW.
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. Sprawdz
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 przejdz
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:
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 znalez
ć 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 Maksimum> (odpowiedni wzór można znalez
ć 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 z
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:
Rysunek 36: Projekt_081 w działaniu.
Aby uniknąć nieporozumień prześledzimy kod implementacji algorytmu:
Rysunek 37: Instrukcje procedury Main w Projekt_081.
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.
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 odpowiedz
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 z
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:
Rysunek 38: Wykorzystanie funkcji Przeszukaj.
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.
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:
Rysunek 39: Wykorzystanie funkcji Przeszukaj z parametrem wskazujÄ…cym kryterium.
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-
lez
ć 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ć
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. A
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 znalez
ć 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 znalez
ć 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 odnalez
ć 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 . A
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 znalez
ć 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 . 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 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:
Rysunek 40: Jeden z przykładów implementacji algorytmu przeszukiwania binarnego.
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 > a
i 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 <= a . Chcąc uzyskać taki zbiór, ze zbio-
i i+1
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 ?
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:
Rysunek 41: Schemat blokowy sortowania.
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 z
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.
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:
a1d"a2'"a2d"a3 Ò!a1d"a3
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.
Rysunek 42: Algorytm sortowania ze sprawdzaniem uporzÄ…dkowania wstecz.
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.
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ć. Odpowiedz
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:
Rysunek 43: Pojedynczy krok metody QuickSort.
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ć wyraz
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 44: Algorytm 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.
Rysunek 45: Jedna z wersji metody Ustaw
dla algorytmu QuickSort.
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 .
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
2x2+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 odnalez
ć wartości minimalne i maksymalne obu zbiorów, a następnie tak przeskalować wykres,
aby wszystkie punkty mogły się na nim znalez
ć. Rysunek przedstawia wykres  przygotowany przez
arkusz kalkulacyjny.
2x2+3x-2
3
2,5
2
1,5
1
0,5
0
-0,5
0 0,2 0,4 0,6 0,8 1
-1
-1,5
-2
-2,5
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 . Można przy takim założeniu napisać proporcję:
p
yp y- ymin y- ymin
= Ò! y =
1 ymax- ymin p ymax- ymin
A
atwo sprawdzić, że prowadzi to do wartości 0 dla y=y oraz 1 dla y=y . Ponadto, jeśli przyj-
min max
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=3x2+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 ax2+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.