1. Iteracja i rekurencja – ich definicje i odpowiednie przykłady ilustrujące



Pobieranie 3,09 Mb.
Strona1/21
Data31.12.2017
Rozmiar3,09 Mb.
  1   2   3   4   5   6   7   8   9   ...   21

1. Iteracja i rekurencja – ich definicje i odpowiednie przykłady ilustrujące.



Rekurencja.
Z rekurencją mamy do czynienia wtedy, gdy podprogram (funkcja lub procedura) wywołuje sam siebie. W Pascalu taka konstrukcja językowa jest dozwolona. Podprogramy rekurencyjne pozwalają na zgrabny i przejrzysty zapis algorytmu takich problemów, w których wynik końcowy jest złożeniem wielu wyników cząstkowych. Jednym z takich problemów jest np. obliczenie n!.
Jak widać, aby obliczyć n! musimy znać (n - 1)!, znając (n - 1)! musimy znać (n - 2)! itd. Cały proces kończy się w momencie kiedy n = 0.

Function silnia(n: integer): Longint;


Begin
If n = 0 Then
silnia := 1
Else
silnia := n * silnia(n - 1);
End;

Dla n = 4 kolejne rekurencyjne wywołania funkcji silnia można przedstawić następująco:

Z chwilą wywołania podprogramu następuje powołanie do życia zmiennych lokalnych podprogramu i zmiennych przechowujących wartość argumentu dla parametrów formalnych podprogramu przekazywanych przez wartość. W trakcie rekurencyjnego wywołania takiego podprogramu powstaje następny komplet takich zmiennych. Wielokrotne rekurencyjne wywołanie podprogramów sprawia, że w pamięci występuje wiele takich kompletów zmiennych, z których aktualnie dostępny jest tylko jeden (na schemacie oznaczenia z indeksami ', '', ''', ''''). Z tego wynika, że podprogram rekurencyjny zajmuje więcej pamięci niż odpowiadający mu podprogram iteracyjny. Poza tym podprogramy iteracyjne są zwykle szybsze. Tym niemniej niektóre przykłady da się rozwiązać tylko przy użyciu rekurencji.

Iteracja.

Iteracja – powtarzanie pewnych operacji czy całych fragmentów obliczeń np. kilku kroków – pętla.


Jest to metoda matematyczna polegająca na wielokrotnym kolejnym zastosowaniu tego samego algorytmu postępowania, przy czym wynik i-tej operacji stanowi dane wejściowe dla kolejnej, (i+1)-szej operacji.

INSTRUKCJE ITERACYJNE.


Służą do ograniczenia cykli programowych, tj. wielokrotnego wykonywania pewnych sekwencji instrukcji.
W języku Turbo Pascal występują trzy instrukcje iteracyjne.
· instrukcja [dla] FOR,
· instrukcja [dopóki] WHILE,
· instrukcja [powtarzaj] REPEAT.

Instrukcję iteracyjną [dla] FOR stosuje się w programie w przypadku, gdy liczba powtórzeń jest znana w danym miejscu programu. Instrukcja for może mieć jedną z dwóch postaci:


gdy wartość początkowa się zwiększa
FOR wartość := wartość_pocz TOwartość_końcowa DO instrukcja
gdy wartość początkowa się zmniejsza
FOR wartość := wartość_pocz DOWNTO wartość_końcowa DO instrukcja

Kolejną instrukcją iteracyjną jest instrukcja [dopóki] WHILE. Instrukcja ta służy do sprawdzenia warunku iteracji na początku i ma postać:

WHILE wyrażenie DO instrukcja

Wyrażenie jest najczęściej wyrażeniem porównania, powinno w wyniku dawać wartość logiczną TRUE lub FALSE, a instrukcja po słowie DO może być dowolną instrukcją prostą lub strukturalną. Instrukcja ta wykonywana jest tak długo dopóki wartością wyrażenia jest TRUE.


REPEAT
instrukcja


instrukcja
UNTIL warunek logiczny


2. Wybrane metody sortowania: przez wstawianie, wybór, scalanie, QuickSort.


Sortowanie to jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.

Algorytmy sortowania są zazwyczaj klasyfikowane według:



złożoności (pesymistyczna, oczekiwana i obliczeniowa) — zależność liczby wykonych operacji w stosunku od liczebności sortowanego zbioru (n). Typową, dobrą złożonością jest średnia O(n log n) i pesymistyczna Ω(n2). Idealną złożonością jest O(n). Algorytmy sortujące nie przyjmujące żadnych wstępnych założeń dla danych wejściowych wykonują co najmniej O(n log n) operacji;

złożoność pamięciowa

sposób działania: algorytmy sortujące za pomocą porównań to takie algorytmy sortowania, których sposób wyznaczania porządku jest oparty wyłącznie na wynikach porównań między elementami; Dla takich algorytmów dolne ograniczenie złożoności wynosi Ω(n log n);

stabilność: stabilne algorytmy sortowania utrzymują kolejność występowania dla elementów o tym samym kluczu (klucz - cecha charakterystyczna dla każdego elementu zbioru, względem której jest dokonywane sortowanie). Oznacza to, że dla każdych elementów R i S o tym samym kluczu, jeśli R wystąpiło przed S to po sortowaniu stabilnym R będzie przed S;

Kiedy elementy o tym samym kluczu są nierozróżnialne, stabilność nie jest istotna.

Przykład: (para liczb całkowitych sortowana względem pierwszej wartości)

(4, 1) (3, 7) (3, 1) (5, 6)

W tym przypadku są możliwe dwa różne wynik sortowania:

(3, 7) (3, 1) (4, 1) (5, 6) (kolejność zachowana)

(3, 1) (3, 7) (4, 1) (5, 6) (kolejność zmieniona)

Stabilne algorytmy sortowania gwarantują, że kolejność zostanie zachowana.

Niestabilne algorytmy sortowania mogą zmienić kolejność.

Przykładowe algorytmy sortowania

W podanej złożoności n oznacza liczbę elementów do posortowania, k liczbę różnych elementów.

Stabilne

sortowanie bąbelkowe — O(n2); (ang. bubblesort)

sortowanie przez scalanie — O(n log n), wymaga O(n) dodatkowej pamięci; (ang. merge sort)

sortowanie przez zliczanie — O(n+k), wymaga O(n+k) dodatkowej pamięci; (ang. counting sort)

sortowanie przez wstawianie — O(n2); (ang. insertion sort)

sortowanie kubełkowe — O(n), wymaga O(k) dodatkowej pamięci; (ang. bucket sort)

Niestabilne



sortowanie przez wybieranie — O(n2); (ang. selection sort)

sortowanie Shella — złożoność nieznana; (ang. Shellsort)

sortowanie grzebieniowe — złożoność nieznana; (ang. combsort)

sortowanie szybkie — O(n log n), pesymistyczny Θ(n2); (ang. quicksort)

sortowanie introspektywne — O(n log n); (ang. introsort)

sortowanie przez kopcowanie — O(n log n); (ang. heapsort)

Sortowanie przez wstawienie (insertion sort) to algorytm, którego czas działania wynosi O(n2). Jest on skuteczny dla małej ilości danych. Jest to jeden z prostszych i jeden z bardziej znanych algorytmów sortowania. Jest on stabilny i nie wymaga dodatkowej pamięci (działa w miejscu). Często stosujemy go podczas gry w karty, biorąc je ze stołu. Biorąc po jednej karcie ze stołu wstawiamy ją w odpowiednie miejsce do kart, które mamy w ręce.

 

Rozważmy jakiś przykład. Weźmy następujący ciąg liczb do posortowania: 3 0 9 5 1 7 6


Możemy sobie wyobrazić, że liczby po prawej stronie to nasze karty na stole, które będziemy po kolei brać, a te, które są po lewej (na razie nie mamy żadnej) to karty, które trzymamy w ręce. Przypominam, że każdą kartę, którą bierzemy ze stołu wstawiamy w odpowiednie miejsce wśród kart, które mamy w ręce tak, aby były one posortowane.

Tak więc bierzemy pierwszą liczbę (w tym wypadku jest to 3) i przenosimy ją na lewą stronę. Nie musimy nic poza tym robić, ponieważ po lewej stronie nie ma żadnych liczb. W ten sposób otrzymujemy:



3




0

9

5

1

7

6




Teraz bierzemy kolejną liczbę z lewej strony, czyli 0 i wstawiamy w odpowiednią pozycję po lewej stronie. Ponieważ 0 jest mniejsze od 3, więc wstawiamy je przed tą liczbę:

0

3




9

5

1

7

6




Podobnie postępujemy z liczbą 9. Ponieważ jest ona największa z tych po lewej, więc wstawiamy ją na końcu:

0

3

9




5

1

7

6




Następnie wstawiamy pierwszą liczbę w ciągu po prawej, czyli 5 w odpowiednie miejsce w ciągu po lewej. Odpowiednie miejsce dla tej liczby to pozycja między liczbami 3 i 9:

0

3

5

9




1

7

6




Postępując podobnie jak wyżej z 1 wstawiamy ją po lewej stronie między 0 a 3:

0

1

3

5

9




7

6




Tak samo dla liczby 7 - wstawiamy ją między liczby 5 i 9:

0

1

3

5

7

9




6




Na sam koniec wstawiamy ostatnią z liczb - 6 do ciągu po lewej stronie między 5 a 7:

0

1

3

5

6

7

9







Algorytm sortowania przez wstawianie najlepiej jest zaimplementować na strukturach danych zwanych listami, są one bowiem w tym przypadku bardziej elastyczne. Implementacja na tablicach może być mało efektywna ze względu na konieczność przesuwania danych w tychże tablicach.

Algorytm ten jest przydatny przy sortowaniu danych sukcesywnie napływających.



Sortowanie przez wstawianie - prosty algorytm sortowania, o złożoności O(n2). Mimo że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort posiada pewne zalety:

efektywny dla danych wstępnie posortowanych

efektywny dla zbiorów o niewielkiej liczebności

stabilny

prosty do implementacji

Sortowanie przez wybór (angielskie selectsort)
Jest to sortowanie, w którym w każdym kroku algorytmu znajduje się najmniejszy element w sortowanym ciągu, po czym przenosi się ten element na kolejną pozycję do ciągu wynikowego (przez zamianę elementów miejscami).

Sortowanie przez wybieranie (selection sort)


Sortowanie przez wybieranie jest już bardziej wydajnym algorytmem sortowania. Idea jego działania polega na wybieraniu z podzbioru danych zbioru elementu najmniejszego (w przypadku sortowania rosnącego) i zamianie jego położenia z początkowym elementem podzbioru. Następnie zakres poszukiwania zostaje zawężony do podzbioru danych znajdujących się po posortowanych już elementach. W pierwszym przeszukiwaniu tym podzbiorem jest naturalnie cały zbiór. Koszt tego algorytmu jest zauważalnie mniejszy od algorytmów bubblesort, shakersort i insertionsort. Wynosi on w pesymistycznym wypadku (n 2 -n)/2, gdzie n oznacza ilość elementów do posortowania. Zaletami algorytmu sortowania przez wybieranie jest optymalna ilość przestawień (n-1); prostota implementacji oraz zadowalająca szybkość dla małych wartości n.

Sortowanie przez wybieranie - jedna z prostszych metod sortowania o złożoności O(n2). Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.

Algorytm przedstawia się następująco:

wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy

zamień wartość minimalną, z elementem na pozycji i

Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu

Przykład

Posortowana zostanie tablica 8-elementowa [9,1,6,8,4,3,2,0]. W tablicy pogrubione zostaną te elementy wśród których wyszukuje się wartość minimalną.


nr iteracji (wartość i)

tablica

minimum

0

[9,1,6,8,4,3,2,0]

0

1

[0,1,6,8,4,3,2,9]

1 (element znajduje się na właściwej pozycji)

2

[0,1,6,8,4,3,2,9]

2

3

[0,1,2,8,4,3,6,9]

3

4

[0,1,2,3,4,8,6,9]

4 (...)

5

[0,1,2,3,4,8,6,9]

6

6

[0,1,2,3,4,6,8,9]

8 (...)

Algorytm można nieco przyspieszyć, gdy tablica jest wypełniana z obu końców, tj. wyszukiwane jest równocześnie minimum i maksimum.

Sortowanie przez scalanie
Algorytm sortowania przez scalanie jest przykładem algorytmu rekurencyjnego. Jeśli ciąg zawiera tylko jeden element, to jest już posortowany, jeśli elementy są co najmniej dwa, to dzielimy taki ciąg na połowy, sortujemy przez scalanie lewą i prawą część, a następnie wykonujemy scalenie tych ciągów.

W algorytmie sortowania przez scalanie jest wykorzystywana strategia "dziel i zwyciężaj". Jest to bardzo efektywna technika algorytmiczna (wykorzystana jest także w algorytmie sortowania "szybkiego").

Wyobraźmy sobie, że mamy dwa uporządkowane ciągi, a chcemy utworzyć z nich jeden – także uporządkowany. Można oczywiście potraktować je jako jeden ciąg i posortować jedną ze znanych metod, ale nie zostanie wykorzystane uporządkowanie obu ciągów. Warto zastosować następujący sposób:

Porównujemy ze sobą pierwsze elementy z każdego z ciągów danych.

Mniejszy element wstawiamy do nowego ciągu i usuwamy z ciągu danych.

Powtarzamy te czynności, aż oba ciągi danych będą puste.

W ten sposób, w nowo utworzonym ciągu wszystkie elementy są uporządkowane, a co najważniejsze operacja ta wymaga wykonania niewielu porównań.

Wiadomo już, jak z dwóch uporządkowanych ciągów otrzymać jeden. Wykorzystując to, można sformułować algorytm sortowania dowolnego ciągu:

Podziel ciąg na dwie równe części (jeśli ciąg ma nieparzystą liczbę elementów, jedna z części będzie miała o jeden element więcej).

Każdą z części uporządkuj.

Połącz dwa uporządkowane ciągi w jeden ciąg uporządkowany.

Pozostaje jeszcze rozstrzygnąć, w jaki sposób posortować każdy z dwóch podciągów? W odpowiedzi zawiera się cała siła tego algorytmu: w ten sam sposób! Po prostu wywołujemy rekurencyjnie ten sam algorytm dla każdego z podciągów. Aby takie postępowanie nie przebiegało w nieskończoność należy określić, kiedy zaprzestajemy podziału ciągu. Następuje to, gdy sortowany ciąg ma mniej niż dwa elementy. Ostatecznie algorytm ma następującą postać:

Jeśli ciąg zawiera więcej niż jeden element, to podziel go na dwie równe części (lub prawie równe, jeśli ciąg ma nieparzystą liczbę elementów).

Posortuj pierwszą część stosując ten sam algorytm.

Posortuj drugą część stosując ten sam algorytm.

Połącz dwa uporządkowane ciągi w jeden ciąg uporządkowany.




Sortowanie QuickSort

Jest to jeden z najpopularniejszych algorytmów sortowania. Wpłynęły na to dwie rzeczy. Po pierwsze jest ono bardzo szybkie (jak sama nazwa wskazuje), a po drugie - proste do wytłumaczenia i implementacji. Pesymistyczny czas jego działania wynosi O(n2), a średni O(n*lg(n)). Mimo tego w praktyce jest to najszybszy algorytm sortowania dużych tablic danych.
Sortowanie szybkie opiera się na technice "dziel i zwyciężaj". Wejściowa tablica jest dzielona (po przestawieniu niektórych z jej elementów) na dwie mniejsze. Każdy element pierwszej tablicy nie jest większy niż każdy element drugiej tablicy. Liczbę, według której wykonuje się podziału to najczęściej pierwszy element tablicy. Następnie dla tych dwóch podtablic wywoływany jest rekurencyjnie ten sam algorytm. Wywołania rekurencyjne kończą się aż któraś z kolejnych podtablic będzie zawierała tylko jeden element. QuickSort działa w miejscu.
Inna odmiana QuickSort
Wyżej wspomniane jest, że algorytm szybkiego sortowania ma pesymistyczny czas działania O(n2). Występuje to w przypadku, gdy tablica wejściowa jest posortowana odwrotnie, tzn. jej wyrazy stanowią ciąg nierosnący.

Sortowanie QuickSort zostało wynalezione przez C.A.R. Hoare'a. Jest to jeden z najpopularniejszych algorytmów sortowania. Wpłynęły na to dwie rzeczy. Po pierwsze jest ono bardzo szybkie (jak sama nazwa wskazuje), a po drugie - proste do wytłumaczenia i implementacji. Pesymistyczny czas jego działania wynosi O(n2), a średni O(n*lg(n)). Mimo tego w praktyce jest to najszybszy algorytm sortowania dużych tablic danych.

Sortowanie szybkie opiera się na technice "dziel i zwyciężaj". Wejściowa tablica jest dzielona (po przestawieniu niektórych z jej elementów) na dwie mniejsze. Każdy element pierwszej tablicy nie jest większy niż każdy element drugiej tablicy. Liczbę, według której wykonuje się podziału to najczęściej pierwszy element tablicy. Następnie dla tych dwóch podtablic wywoływany jest rekurencyjnie ten sam algorytm. Wywołania rekurencyjne kończą się aż któraś z kolejnych podtablic będzie zawierała tylko jeden element. QuickSort działa w miejscu.

Przykład

Posortujmy dla przykładu następującą tablicę:



5

7

8

1

4

0

4

6

8

2

1

5

2

6

9

Liczbą, według której będziemy wykonywać podział będzie pierwsza liczba danej tablicy - w tym przypadku jest to 5. Na początku przeglądamy tablicę od lewej strony, aż znaldziemy element większy od naszej liczby. W tym przypadku jest to element drugi, czyli 7. Następnie przeglądamy naszą tablicę od końca aż znajdziemy element mniejszy od naszej liczby (5). Tym elementem jest trzeci od końca, czyli liczba 2.

5

7

8

1

4

0

4

6

8

2

1

5

2

6

9

Elementy, które już "przeszliśmy" są pogrubione, a te, na których zatrzymaliśmy się podkreślone. Tak więc po lewej stronie zatrzymaliśmy się na 7, a po prawej na 2. Teraz zamieniamy te elementy ze sobą:

5

2

8

1

4

0

4

6

8

2

1

5

7

6

9

Znowu kontynuujemy przeglądanie od lewej strony. Zatrzymujemy się na elemencie trzecim, czyli 8. A w przeglądaniu od końca zatrzymujemy się na elemencie 5 od końca, czyli 1:

5

2

8

1

4

0

4

6

8

2

1

5

7

6

9

Zamieniamy te elementy ze sobą:

5

2

1

1

4

0

4

6

8

2

8

5

7

6

9

Postępując jak wyżej po lewej dochodzimy do elementu nr 8, czyli 6, a po prawej do 6 od końca, czyli 2:

5

2

1

1

4

0

4

6

8

2

8

5

7

6

9

Jak zwykle zamieniamy je ze sobą:

5

2

1

1

4

0

4

2

8

6

8

5

7

6

9

Idąc od lewej zatrzymujemy się na 8, a od prawej na dwójce, ponieważ nasze przeglądania od lewej i od prawej "spotkały się" tak więc cofamy się w każdym o jedną pozycję do tyłu i w ten sposób mamy wyznaczony podział:

5

2

1

1

4

0

4

2




8

6

8

5

7

6

9




Z tymi podtablicami postępujemy tak, jak z tablicą wejściową. Nie będę tutaj prezentował poszczególnych kroków sortowania. Elementem dzielącym po lewej jest liczba 5, a po prawej liczba 8 (pierwsze w tych tablicach). Po podziale takim jak przeprowadzonym wyżej otrzymujemy:

2

2

1

1

4

0

4




5




6

6

7

5




8

8

9




Zauważmy, że dla liczby 5, która jest "sama" nie będzie już wywołania rekurencyjnego. Po następnym podziale otrzymamy:

0

1

1




2

4

2

4




5




5




6

7

6




8




8

9




W tym przypadku mógł być problem z podziałem tablicy 6,6,7,5. W tym przypadku z lewej strony i prawej doszliśmy do elementu drugiego, tj. liczby 6 i zatrzymaliśmy się. Nie można zamienić elementu z nim samym. W tej sytuacji można przyjąć, że "sporna" liczba będzie należeć do lewej lub do prawej strony. Ja przyjełem, że do prawej.

Po następnym podziale otrzymamy:



0




1

1




2




4

2

4




5




5




6




7

6




8




8




9




Kolejny podział daje nam:

0




1




1




2




2




4

4




5




5




6




6




7




8




8




9




No, a po ostatnim podziale nasze dane będą wyglądać następująco:

0




1




1




2




2




4




4




5




5




6




6




7




8




8




9




Teraz łączymy wszystkie liczby i powstaje następujący ciąg:

0

1

1

2

2

4

4

5

5

6

6

7

8

8

9

Liczby są już posortowane. Oczywiście wszystkie podziały są wykonywane rekurencyjnie. Poprzez zastosowanie rekurencyjności algorytm QuickSort ma zwięzły kod i jest łatwy w implementacji.

 

Inna odmiana QuickSort

Wyżej wspomniałem, że algorytm szybkiego sortowania ma pesymistyczny czas działania O(n2). Występuje to w przypadku, gdy tablica wejściowa jest posortowana odwrotnie, tzn. jej wyrazy stanowią ciąg nierosnący. Na przykład taką tablicą może być:


9

8

7

6

5

4

3

2

1

0

Proszę spróbować przeprowadzić algorytm QuickSort dla tych danych. Wynika to z tego, że jako element dzielący daną tablicę wybieramy jej pierwszy element. Dla tablicy powyżej takie założenie powoduje, że za każdym razem granica podziału jest za pierwszą liczbą tej tablicy. Można oczywiście wybrać inny element jako granicę podziału. W ten spowodujemy, że algorytm szybkiego sortowania dla wyżej przedstawionych danych będzie działał dużo szybciej. Ale który element wybrać? Najlepiej wylosować. Jak się okazuje to bardzo dobre rozwiązanie, które nie wymaga dużo obliczeń. Najbardziej optymalnym rozwiązaniem jest wybranie mediany (najbardziej "środkowego" elementu tablicy). Jednakże wymaga to dużo dodatkowego czasu. Można także zmieszać losowanie liczb z wyborem mediany. Po prostu losujemy z tablicy do podziału pewną ilość liczb (najlepiej 3) i wyznaczamy wśród nich medianę, czyli element środkowy pod względem wartości. Następnie dokonujemy podziału według tego elementu.



  1   2   3   4   5   6   7   8   9   ...   21


©operacji.org 2019
wyślij wiadomość

    Strona główna