ALGORYTMY W PRZYK£ADACH

1 ALGORYTMY . W PRZYK ADACH. Tekst zosta opracowany na podstawie zasob w internetowych ( teksty mgr Jerzego Wa aszka) , podr cznika Informatyka dla LO WSIP , ALGORYTMY + Struktury danych = Programy N. Wirtha , ALGORYTMY o Opracowanie : Dariusz Nyk Strona 1 z 185. SPIS TRE CI. Wst Schemat blokowy ..5. Instrukcja iteracji ..8. Z o ono obliczeniowa algorytmu..10. 1. Wyznaczanie NWD i NWW algorytm 2. Najwi kszy i najmniejszy element 3. Poszukiwanie lidera w zbiorze..17. 4. Przeszukiwanie sekwencyjne..20. 5. Wyszukiwanie z wartownikiem..21. 6. Wyszukiwanie najcz stszego elementu zbioru..24. Drugi najwi kszy element zbioru..32. K-ty najwi kszy element zbioru..34. K-ty najwi kszy element zbioru wyszukiwanie szybkie ..36. 7. Sito Erastotenesa..41. 8. Sortowanie zbioru.

2 49. Sortowanie zwariowane (Bogo Sort)..52. Sortowanie naiwne (g upie)..57. Sortowanie b Sortowanie przez wyb r..65. Sortowanie przez wstawianie..67. Sortowanie metod Shella..71. Rekurencja..75. Sortowanie przez Sortowanie stogowe (przez kopcowanie , heap sort) ..83. Drzewo binarne..83. Tworzenie Rozbi r Sortowanie Sortowanie dystrybucyjne..97. Sortowanie rozrzutowe..97. Sortowanie kube Sortowanie przez zliczanie..106. 9. Binarne kodowanie liczb..113. System dziesi tny..113. Schemat Hornera..116. Schemat Hornera jako spos b obliczania warto ci Przeliczanie liczb systemu dziesi tnego na dowolny system ..119. Liczby zmiennoprzecinkowe..121. 10. System BIT podstawowa jednostka informacji..128. Kod binarny..129. kod w binarnych..130. Kodowanie grafiki.

3 130. Kodowanie znak Mno niki 11. Naturalny system dw jkowy..133. Warto liczby w naturalnym systemie dw jkowym..133. Strona 2 z 185. Zakres liczby Schemat Hornera dla liczb Przeliczanie liczb dziesi tnych na binarne..134. Dw jkowy system sta oprzecinkowy..135. Warto dw jkowej liczby sta oprzecinkowej..135. Zakres binarnych liczb sta Operacje arytmetyczne na systemie dw Mno enie ..140. Szybkie pot gowanie liczb..142. 12. Kodowanie liczb binarnych ze Zapis znak-modu ..144. Warto dziesi tna liczby w zapisie ZM..144. Zapis uzupe nie do 1 U1 (1C - One's Complement)..145. Przeliczanie liczb dziesi tnych na zapis U1..146. Sta oprzecinkowy zapis Dodawanie w U1 ..148. w U1..149. Zapis uzupe nie do 2 U2 (2C - Two's Complement ) ..150. Liczba przeciwna do liczby w U2.

4 151. Przeliczanie liczb dziesi tnych na zapis U2 ..152. Sta oprzecinkowy zapis Dodawanie i odejmowanie w Mno enie w Dzielenie w U2..156. 13. Pozosta e kody Kod BCD..156. Kod Gray'a..158. Wyznaczanie i-tego wyrazu n-bitowego kodu Gray'a..159. algorytm tworzenia wyraz w kodu Gray'a..160. 14. Szyfrowanie danych..163. Steganografia ..163. Szyfrowanie przez przestawianie..166. Szyfrowanie przez podstawianie..168. Kryptografia z kluczem jawnym..177. Szyfr RSA..179. 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).

5 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.

6 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);. Readln (y);. 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.

7 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).

8 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. Blok wej cia / wyj cia blok odpowiedzialny za wykonanie operacji wprowadzania i wyprowadzania danych, wynik w, komunikat w. Ma kszta t r wnoleg oboku, wchodzi i wychodzi z niego jedno po czenie. Blok decyzyjny okre la wyb r jednej z dw ch mo liwych dr g dzia ania. Ma kszta t rombu lub sze ciok ta. Wchodzi do niego jedno po czenie, a wychodz dwa : TAK gdy warunek wpisany wewn trz jest spe niony oraz NIE gdy warunek wpisany wewn trz nie jest spe niony. Wyb r kszta tu bloku zale y od nas.

9 Istniej oczywi cie jeszcze inne bloki, stosowane przy du ych projektach, ale my z nich nie b dziemy korzysta . Zapiszmy teraz nasz algorytm liczenia redniej w postaci schematu blokowego : Mamy ju algorytm, ale brakuje nam jeszcze jednego czynnika sprawiaj cego by zadanie rozwi zywane za pomoc algorytmu by o przedstawione w pe ni precyzyjnie specyfikacji problemu algorytmicznego. Specyfikacj problemu algorytmicznego nazywamy dok adny opis problemu algorytmicznego, kt ry ma zosta rozwi zany oraz podanie informacji o danych wej ciowych i wyj ciowych. Czyli przed naszym algorytmem powinien znale si dodatkowy zapis : Problem algorytmiczny : obliczenie redniej arytmetycznej dw ch licz rzeczywistych Dane wej ciowe : x,y R. Dane wyj ciowe : sr R rednia liczb x i y Strona 6 z 185.

10 Dane w algorytmie s najcz ciej przedstawiane za pomoc liter lub nazw. Zmienn nazywamy obiekt wyst puj cy w algorytmie, okre lony przez nazw i s u cy do zapami tywania okre lonych danych. Zmienna musi mie okre lony typ (rzeczywisty, a cuchowy itp.). Je li sta e i zmienne po czymy operatorami to otrzymamy wyra enie. Sta e i zmienne wyst puj ce w wyra eniu nazywamy operandami. Operatory arytmetyczne Operatory relacji Symbol Znaczenie Symbol Znaczenie + dodawanie = r wny - odejmowanie > wi kszy * mno enie >= wi kszy lub r wny / dzielenie < mniejszy div dzielenie ca kowite (3div2 = 1) <= mniejszy lub r wny mod reszta z dzielenia liczb ca kowitych <> r ny Operator przypisania :=. Po lewej stronie operatora przypisania mo e sta tylko zmienna ! Operatory logiczne and - koniunkcja (iloczyn zda ) /\.