algorytmy.pdf

(2547 KB) Pobierz
ALGORYTMY W PRZYK£ADACH
ALGORYTMY
W PRZYKÿADACH
Tekst został opracowany na podstawie zasobów internetowych (m.in. teksty mgr Jerzego Wałaszka) , podręcznika
„Informatyka dla LO” WSIP , „ Algorytmy + Struktury danych = Programy” N. Wirtha , „Algorytmy” M.M.Sysło
Opracowanie : Dariusz Nyk
Strona 1 z 185
SPIS TRE Ś CI
Wst ę p................................................................................................................................................... 4
Schemat blokowy ............................................................................................................................. 5
Instrukcja iteracji .............................................................................................................................. 8
ZłoŜoność obliczeniowa algorytmu. ............................................................................................... 10
1. Wyznaczanie NWD i NWW – algorytm Euklidesa.................................................................. 13
2. Najwi ę kszy i najmniejszy element zbioru. ................................................................................. 16
3. Poszukiwanie lidera w zbiorze. ................................................................................................... 17
4. Przeszukiwanie sekwencyjne. ..................................................................................................... 20
5. Wyszukiwanie z wartownikiem. ................................................................................................. 21
6. Wyszukiwanie najcz ę stszego elementu zbioru. ......................................................................... 24
6.1. Drugi największy element zbioru. ........................................................................................... 32
6.2. K-ty największy element zbioru. ............................................................................................. 34
6.3. K-ty największy element zbioru – wyszukiwanie szybkie . .................................................... 36
7. Sito Erastotenesa. ......................................................................................................................... 41
8. Sortowanie zbioru. ....................................................................................................................... 49
8.1. Sortowanie zwariowane (Bogo Sort)....................................................................................... 52
8.2. Sortowanie naiwne (głupie). .................................................................................................... 57
8.3. Sortowanie bąbelkowe............................................................................................................. 58
8.4. Sortowanie przez wybór. ......................................................................................................... 65
8.5. Sortowanie przez wstawianie. ................................................................................................. 67
8.6. Sortowanie metodą Shella. ...................................................................................................... 71
8.7. Rekurencja. .............................................................................................................................. 75
8.8. Sortowanie przez scalanie........................................................................................................ 76
8.9. Sortowanie stogowe (przez kopcowanie , heap sort) .............................................................. 83
8.9.1. Drzewo binarne. ................................................................................................................ 83
8.9.2. Tworzenie kopca................................................................................................................ 85
8.9.3. Rozbiór kopca.................................................................................................................... 88
8.10. Sortowanie szybkie. ............................................................................................................... 92
8.11. Sortowanie dystrybucyjne. .................................................................................................... 97
8.11.1. Sortowanie rozrzutowe. ................................................................................................... 97
8.11.2. Sortowanie kubełkowe. .................................................................................................. 102
8.11.3. Sortowanie przez zliczanie. ........................................................................................... 106
8.12. Podsumowanie. .................................................................................................................... 112
9. Binarne kodowanie liczb. .......................................................................................................... 113
9.1. System dziesiętny. ................................................................................................................. 113
9.2. Schemat Hornera. .................................................................................................................. 116
9.3. Schemat Hornera jako sposób obliczania wartości liczby..................................................... 117
9.4. Przeliczanie liczb systemu dziesiętnego na dowolny system ............................................... 119
9.5. Liczby zmiennoprzecinkowe. ................................................................................................ 121
10. System binarny......................................................................................................................... 128
10.1. BIT – podstawowa jednostka informacji. ............................................................................ 128
10.2. Kod binarny. ........................................................................................................................ 129
10.3.Zastosowanie kodów binarnych. .......................................................................................... 130
10.3.1. Kodowanie grafiki. ........................................................................................................ 130
10.3.2. Kodowanie znaków........................................................................................................ 131
10.3.Bajt........................................................................................................................................ 132
10.4. MnoŜniki binarne................................................................................................................. 132
11. Naturalny system dwójkowy. .................................................................................................. 133
11.1. Wartość liczby w naturalnym systemie dwójkowym. ......................................................... 133
Strona 2 z 185
11.2. Zakres liczby binarnej.......................................................................................................... 133
11.3. Schemat Hornera dla liczb binarnych.................................................................................. 133
11.4. Przeliczanie liczb dziesiętnych na binarne. ......................................................................... 134
11.5. Dwójkowy system stałoprzecinkowy. ................................................................................. 135
11.5.1. Warto ść dwójkowej liczby stałoprzecinkowej. .............................................................. 135
11.5.2. Zakres binarnych liczb stałoprzecinkowych.................................................................. 137
11.6. Operacje arytmetyczne na systemie dwójkowym................................................................ 137
11.6.1. Dodawanie..................................................................................................................... 137
11.6.2. Odejmowanie................................................................................................................. 139
11.6.3. Mno Ŝ enie ....................................................................................................................... 140
11.6.4. Dzielenie. ....................................................................................................................... 141
11.7. Szybkie potęgowanie liczb. ................................................................................................. 142
12. Kodowanie liczb binarnych ze znakiem................................................................................. 143
12.1. Zapis „znak-moduł”............................................................................................................. 144
12.1.1. Warto ść dziesi ę tna liczby w zapisie ZM. ....................................................................... 144
12.2. Zapis uzupełnień do 1 – U1 (1C - One's Complement)...................................................... 145
12.2.1. Przeliczanie liczb dziesi ę tnych na zapis U1. ................................................................. 146
12.2.2. Stałoprzecinkowy zapis U1............................................................................................ 148
12.2.3. Dodawanie w U1 ........................................................................................................... 148
12.2.4.Odejmowanie w U1. ....................................................................................................... 149
12.3. Zapis uzupełnień do 2 – U2 (2C - Two's Complement ) .................................................... 150
12.3.1. Liczba przeciwna do liczby w U2 .................................................................................. 151
12.3.2. Przeliczanie liczb dziesi ę tnych na zapis U2 .................................................................. 152
12.3.3. Stałoprzecinkowy zapis U2............................................................................................ 154
12.3.4. Dodawanie i odejmowanie w U2................................................................................... 155
12.3.5. Mno Ŝ enie w U2. ............................................................................................................. 155
12.3.6. Dzielenie w U2. ............................................................................................................. 156
13. Pozostałe kody binarne. ........................................................................................................... 156
13.1. Kod BCD. ............................................................................................................................ 156
13.2. Kod Gray’a. ......................................................................................................................... 158
13.2.1. Wyznaczanie i-tego wyrazu n-bitowego kodu Gray'a. .................................................. 159
13.2.2.Rekurencyjny algorytm tworzenia wyrazów kodu Gray’a. ............................................ 160
14. Szyfrowanie danych. ................................................................................................................ 163
14.1. Steganografia ....................................................................................................................... 163
14.2. Kryptografia......................................................................................................................... 163
14.3. Szyfrowanie przez przestawianie. ....................................................................................... 166
14.4. Szyfrowanie przez podstawianie. ........................................................................................ 168
14.5. Kryptografia z kluczem jawnym. ........................................................................................ 177
14.5.1. Szyfr RSA. ...................................................................................................................... 179
14.6. Potwierdzenie autentyczności i podpis elektroniczny. ........................................................ 184
Strona 3 z 185
ALGORYTMY W PRZYKŁADACH
Wst ę p.
Algorytm – skończony ciąg czynności, przekształcający zbiór danych wejściowych na zbiór danych
wyjściowych (wyników).
Etapy konstruowania algorytm :
1) sformułowanie zadania – ustalamy jaki problem ma rozwiązywać algorytm
2) określenie danych wejściowych – ich typu ( w typie określamy, czy dane są liczbami
rzeczywistymi, całkowitymi, czy znakami, czy teŜ innego typu)
3) określenie wyniku oraz sposobu jego prezentacji
4) ustalenie metody wykonania zadania (moŜe być kilka metod na rozwiązanie –
wybieramy tą, która według nas jest najlepsza)
5) zapisanie algorytmu za pomocą wybranej metody (z punktu 4 )
6) Analiza poprawności rozwiązania
7) Testowanie rozwiązania dla róŜnych danych (algorytm musi być uniwersalny, aby
słuŜyć do rozwiązywania zadań dla róŜnych danych wejściowych)
8) Ocena skuteczności algorytmu ( praktyczna ocena algorytmu : np. szybkości,
skomplikowania)
Sposoby zapisu algorytmu.
Do najczęściej uŜywanych sposobów zapisu algorytmu naleŜą :
1) lista kroków
2) pseudojęzyk (pseudokod)
3) graficzna prezentacja za pomocą schematu blokowego
4) zapis w danym języku programowania
Zadanie : znaleźć średnią arytmetyczną dwóch liczb rzeczywistych
Ad. 1 Lista kroków charakteryzuje się tym, Ŝe kaŜdy wiersz opisujący pojedynczy krok
realizowanej czynności jest numerowany.
1) pobierz pierwszą liczbę
2) pobierz drugą liczbę
3) dodaj liczby do siebie
4) wynik dodawania podziel przez 2
5) wyświetl otrzymaną wartość
6) zakończ
Ad. 2. Pseudojęzyk jest metodą pośrednią między zapisem za pomocą listy kroków a zapisem w
języku programowania.
- początek
- wprowadzenie x i y rzeczywistych
- wykonanie działania (x+y)/2
- pisz wynik
- koniec
Strona 4 z 185
Ad. 4. Ten problem zapisany w postaci programu w języku Turbo Pascal
Program Srednia;
Var x, y : Real;
Begin
Readln (x);
Writeln (‘Średnia arytmetyczna wprowadzonych liczb wynosi : ‘ (x+y)/2 :7:2);
End.
Przedstawiony tu algorytm liczenia średniej jest wykonywany zawsze w tej samej kolejności,
niezaleŜnie od wartości danych wejściowych.
Algorytm liniowy (sekwencyjny) – algorytm, w którym kolejność wykonywanych czynności jest
taka sama i niezaleŜna od wartości danych wejściowych.
Ad. 3. Zapis za pomocą schematu blokowego.
Schemat blokowy .
Schemat blokowy przedstawia algorytm w postaci symboli graficznych, podając szczegółowo
wszystkie operacje arytmetyczne, logiczne, przesyłania, pomocnicze wraz z kolejnością ich
wykonywania. Składa się on z wielu elementów, wśród których podstawowym jest blok.
Wygl ą d bloku
Opis
Bloki graniczne – początek i koniec algorytmu.
Mają kształt owalu. Z bloku Start wychodzi tylko jedno połączenie;
kaŜdy schemat blokowy musi mieć dokładnie jeden blok START.
KaŜdy schemat blokowy musi mieć co najmniej jeden blok STOP.
Ł ą cznik pomiędzy blokami – określa kierunek przepływu danych
lub kolejność wykonywanych działań (ścieŜka sterująca)
Blok kolekcyjny – łączy kilka róŜnych dróg algorytmu
Blok operacyjny – zawiera operację lub grupę operacji, w których
wyniku ulega zmianie wartość zmiennej (tu : nadanie zmiennej x
wartości 10).
Bloki operacyjne mają kształt prostokąta , wchodzi do niego jedno
połączenie i wychodzi teŜ jedno.
Strona 5 z 185
Readln (y);
8227577.001.png 8227577.002.png 8227577.003.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin