Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00219 003963 15209991 na godz. na dobę w sumie
Informatyka Europejczyka. Informatyka. Podręcznik dla szkół ponadgimnazjalnych. Zakres rozszerzony. Część 1 (Wydanie II) - książka
Informatyka Europejczyka. Informatyka. Podręcznik dla szkół ponadgimnazjalnych. Zakres rozszerzony. Część 1 (Wydanie II) - książka
Autor: Liczba stron: 304
Wydawca: Helion Edukacja Język publikacji: polski
ISBN: 978-83-246-2823-0 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> podręczniki szkolne >> szkoła ponadgimnazjalna
Porównaj ceny (książka, ebook, audiobook).
Każdy program jest tylko na tyle dobry, na ile jest przydatny.
Linus Torvalds,
programista, twórca i opiekun Linuksa

Dynamika zmian i ewolucji w obszarze technologii informacyjnej jest tak ogromna, że nie da się jej porównać z rozwojem innych dyscyplin. Szczególnie dobrze widać to w dziedzinie edukacji informatycznej. Zestaw Informatyka Europejczyka jest całkowicie kompatybilny z wymaganiami, jakie stawia przed każdym uczniem współczesna informatyka. Został stworzony do nauczania informatyki w zakresie rozszerzonym w szkołach ponadgimnazjalnych, a jego treści, struktura, duża liczba przykładów i zadań pozwalają na doskonałe przygotowanie do egzaminu maturalnego.

Rozpoczynasz właśnie pracę z pierwszą częścią podręcznika - związaną z algorytmiką i programowaniem. Dzięki przejrzystemu układowi książki, świetnemu doborowi przykładów i ciekawemu opracowaniu materiału bez problemu poznasz sposoby przedstawiania algorytmów, a także zmierzysz się z ich analizą i realizacją. Przebrniesz przez wybrane metody programowania oraz podstawy programowania w języku C++. Odkryjesz także fascynujący świat kryptografii i algorytmów szyfrujących. Na płycie CD zamieszczono realizacje wszystkich algorytmów (programy w językach C++ i Pascal, algorytmy w arkuszach kalkulacyjnych) oraz materiał uzupełniający, dotyczący programowania obiektowego. Wybrane zadania z egzaminów dojrzałości umożliwią Ci nie tylko zapoznanie się z formą zadań pojawiających się na maturze, ale także pomogą w rozwijaniu Twojej pasji.

Komplet podręczników oraz płyty z serii Informatyka Europejczyka pozwolą uczniom zdobywać wiedzę poprzez praktykę, a nauczycielom ułatwią przekazywanie nowego materiału w interesujący i niebanalny sposób. Helion, największe wydawnictwo informatyczne w Polsce, teraz pomaga zgłębić tajemnice świata komputerów także pokoleniu przyszłych specjalistów.

Wciśnij Enter i do dzieła!

Numer dopuszczenia: 410/1/2012


Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

2 strona.pdf 1 2013-01-09 13:21:43 Podręcznik dopuszczony do użytku szkolnego przez ministra właściwego do spraw oświaty i wychowania i wpisany do wykazu podręczników przeznaczonych do kształcenia ogólnego do nauczania informatyki, na podstawie opinii rzeczoznawców: mgr. inż. Włodzimierza Kruszwickiego, dr. Leszka Rudaka, dr Iwony Wandy Grygiel. Zakres kształcenia: rozszerzony. Etap edukacyjny: IV. Typ szkoły: szkoły ponadgimnazjalne. Rok dopuszczenia 2012. Numer ewidencyjny w wykazie: 410/1/2012 Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje naruszenie praw autorskich niniejszej publikacji. Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich właścicieli. Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Redaktor prowadzący: Joanna Zaręba Projekt okładki: ULABUKA Skład: Ewa Galczak Ilustracja na okładce została wykorzystana za zgodą Shutterstock. Wydawnictwo HELION ul. Kościuszki 1c, 44-100 GLIWICE tel. 32 231 22 19, 32 230 98 63 e-mail: helion@helion.pl WWW: http://helion.pl (księgarnia internetowa, katalog książek) Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://helion.pl/user/opinie?iepp12 Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. ISBN: 978-83-246-2823-0 Copyright © Helion 2013 Wydanie II Printed in Poland. (cid:127) Kup książkę (cid:127) Poleć książkę (cid:127) Oceń książkę (cid:127) Księgarnia internetowa (cid:127) Lubię to! » Nasza społeczność C M Y CM MY CY CMY K Spis treści Wstęp Rozdział 1. Wprowadzenie do algorytmiki 1.1. Pojęcie algorytmu 1.2. Etapy rozwiązywania zadań za pomocą komputera 1.3. Sposoby reprezentowania algorytmów 1.3.1. Lista kroków algorytmu 1.3.2. Schemat blokowy algorytmu 1.3.3. Drzewo algorytmu 1.3.4. Program w języku programowania wysokiego poziomu 1.4. Algorytmy liniowe i z warunkami 1.4.1. Algorytmy liniowe 1.4.2. Algorytmy z warunkami 1.4.3. Rozwiązywanie równania kwadratowego 1.5. Iteracja 1.6. Rekurencja 1.6.1. Obliczanie silni liczby naturalnej 1.6.2. Wyznaczanie wyrazów ciągu Fibonacciego 1.6.3. Wieże Hanoi 1.7. Metoda „dziel i zwyciężaj” 1.7.1. Przeszukiwanie binarne ciągu uporządkowanego 1.8. Programowanie zachłanne 1.8.1. Minimalizacja łączenia par 1.9. Kryptografi a i kryptoanaliza. Metody szyfrowania 1.10. Własności algorytmów 1.10.1. Złożoność obliczeniowa i efektywność algorytmów 1.10.2. Poprawność i skończoność algorytmów 1.10.3. Optymalność algorytmów Rozdział 2. Algorytmy i ich zastosowanie 2.1. Algorytmy badające własności geometryczne 2.2. Wyznaczanie największego wspólnego dzielnika i najmniejszej wspólnej wielokrotności dwóch liczb naturalnych 2.2.1. Algorytm Euklidesa 2.2.2. Obliczanie najmniejszej wspólnej wielokrotności 7 9 9 10 11 11 13 14 15 16 16 18 21 28 36 37 39 43 47 47 50 50 53 55 55 57 58 61 61 66 66 71 Spis treści 3 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe i reprezentacja danych liczbowych w komputerze 2.3.1. Systemy liczbowe 2.3.2. Konwersje pozycyjnych systemów liczbowych 2.3.3. Operacje arytmetyczne wykonywane w różnych systemach liczbowych 2.3.4. Wyznaczanie wartości wielomianu za pomocą schematu Hornera 2.3.5. Zamiana liczb z dowolnego pozycyjnego systemu liczbowego na system dziesiętny z zastosowaniem schematu Hornera 2.3.6. Reprezentacja danych liczbowych w komputerze 2.3.7. Błędy w obliczeniach 2.4. Generowanie liczb pierwszych i badanie, czy liczba jest pierwsza 2.4.1. Badanie, czy liczba jest pierwsza 2.4.2. Sito Eratostenesa 2.5. Przeszukiwanie ciągu liczbowego — metody liniowe 2.5.1. Liniowe przeszukiwanie ciągu liczbowego 2.5.2. Liniowe przeszukiwanie ciągu liczbowego z wartownikiem 2.6. Znajdowanie minimalnego lub maksymalnego elementu 2.7. Znajdowanie lidera w zbiorze 2.8. Sprawdzanie monotoniczności ciągu liczbowego 2.9. Sortowanie ciągu liczbowego 2.9.1. Metody sortowania przez porównania 2.9.2. Sortowanie w czasie liniowym 2.10. Zastosowanie metody „dziel i zwyciężaj” 2.10.1. Jednoczesne znajdowanie minimalnego i maksymalnego elementu 2.10.2. Sortowanie przez scalanie 2.10.3. Sortowanie szybkie 2.11. Metody numeryczne i obliczenia przybliżone 2.11.1. Obliczanie wartości pierwiastka kwadratowego z liczby nieujemnej — algorytm Newtona-Raphsona 2.11.2. Obliczanie pola obszaru ograniczonego wykresem funkcji 2.11.3. Znajdowanie przybliżonej wartości miejsca zerowego funkcji — metoda połowienia przedziałów 2.12. Zastosowanie programowania zachłannego 2.12.1. Problem plecakowy 2.12.2. Algorytm wydawania reszty 72 72 74 80 84 87 89 94 98 98 100 104 104 108 110 113 117 119 121 130 135 135 140 145 149 149 152 160 164 164 173 4 Spis treści 2.13. Algorytmy na tekstach 2.13.1. Palindromy 2.13.2. Sortowanie tekstu 2.13.3. Anagramy 2.13.4. Wyszukiwanie wzorca w tekście 2.13.5. Wyznaczanie wartości wyrażenia zapisanego w odwrotnej notacji polskiej ONP 2.14. Wybrane algorytmy kryptografi czne 2.14.1. Szyfrowanie symetryczne 2.14.2. Szyfrowanie asymetryczne Rozdział 3. Programowanie w języku C++ 3.1. Języki programowania — pojęcia, klasyfi kacja, przykłady 3.2. Wprowadzenie do programowania 3.2.1. Struktura programu 3.2.2. Operacje wejścia-wyjścia 3.2.3. Zmienne, stałe, wskaźniki i referencje 3.2.4. Wyrażenia arytmetyczne, relacje i operatory logiczne 3.2.5. Priorytety relacji i działań 3.2.6. Funkcje matematyczne 3.2.7. Liczby losowe 3.2.8. Komentarze 3.3. Podstawowe konstrukcje algorytmiczne 3.3.1. Instrukcja przypisania 3.3.2. Instrukcja złożona 3.3.3. Instrukcje warunkowe 3.3.4. Instrukcja wyboru 3.3.5. Instrukcje iteracyjne 3.3.6. Instrukcje sterujące 3.4. Proste typy danych 3.5. Strukturalizacja programu 3.5.1. Struktura funkcji 3.5.2. Zmienne lokalne i globalne 3.5.3. Przekazywanie parametrów w funkcjach 3.5.4. Przeładowanie funkcji 3.6. Strukturalne typy danych 3.6.1. Tablice 3.6.2. Łańcuchy 3.6.3. Struktury 175 175 177 179 182 186 189 189 200 203 203 205 206 209 214 217 223 224 225 226 226 226 227 227 230 233 238 240 241 241 244 245 252 257 257 265 271 Spis treści 5 3.7. Dynamiczne struktury danych 3.7.1. Stos 3.7.2. Kolejka 3.7.3. Lista 3.7.4. Drzewo binarne 3.8. Plikowe operacje wejścia-wyjścia Rozdział 4. Projekt programistyczny 4.1. Inżynieria oprogramowania 4.2. Projekt programistyczny Bibliografia CD-ROM Skorowidz 276 277 278 279 282 285 291 291 293 295 296 297 6 Spis treści D e fi n i c j a D e fi n i c j a 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe i reprezentacja danych liczbowych w komputerze 2.3.1. Systemy liczbowe Systemem liczbowym nazywamy zbiór zasad określających sposób zapisywania i nazywania liczb. Pozycyjny system liczbowy to system, w którym wartość cyfry zależy od miejsca, w jakim znajduje się ona w danej liczbie. Miejsce to nazywamy pozycją. Do najważniejszych pozycyjnych systemów liczbowych wykorzystywanych w informa- tyce należą: • • • system dwójkowy, czyli binarny; system ósemkowy, czyli oktalny; system szesnastkowy, czyli heksadecymalny. Podstawą systemu binarnego, określającą liczbę cyfr, jest dwa. System ten korzysta więc z dwóch cyfr, którymi są 0 i 1. System oktalny ma podstawę osiem, stąd cyframi są tutaj 0, 1, 2, 3, 4, 5, 6, 7. Podstawą systemu heksadecymalnego jest szesnaście, a więc w systemie tym korzystamy z szesnastu cyfr. Cyframi tego systemu są: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Wy- korzystanie liter w zapisie cyfr podyktowane jest koniecznością jednoznacznej notacji liczby w tym systemie. Litery odpowiadają cyfrom, których wartości zapisane w ukła- dzie dziesiętnym są liczbami dwucyfrowymi: A B C D E F Gdybyśmy nie korzystali z liter, zapis liczby 11216 mógłby oznaczać 11216 lub B216 lub 1C16 . 16 = 1010 , 16 = 1110 , 16 = 1210 , 16 = 1310 , 16 = 1410 , 16 = 1510 . 72 Rozdział 2. Algorytmy i ich zastosowanie W s k a z ó w k a Przy realizacji konwersji i działań arytmetycznych w różnych systemach liczbowych można zastosować udostępnioną w systemie Windows aplikację Kalkulator. Pro- gram ten umożliwia realizację obliczeń w następujących systemach: decymalnym (czyli dziesiętnym), binarnym, oktalnym i heksadecymalnym. Wykonywać można zarówno konwersję pomiędzy wymienionymi systemami, jak i operacje arytme- tyczne. Aby uzyskać dostęp do tych systemów, należy po uruchomieniu aplikacji Kalkulator wybrać w menu polecenie Widok/Programisty (we wcześniejszych wer- sjach systemu Windows — Widok/Naukowy). I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. Najbardziej znanym systemem liczbowym, który nie jest pozycyjny, jest system rzym- ski. Zaliczany jest on do systemów zwanych addytywnymi. Charakteryzują się one tym, że bazują na symbolach dla kilku małych liczb oraz ich wielokrotności. W przypadku systemu rzymskiego dotyczy to wielokrotności liczb 5 i 10. Dostępnych jest razem sie- dem znaków: Zapisywanie liczby w tym systemie polega na składaniu jej przez dodawanie lub odej- mowanie kolejnych symboli o określonej wartości. Liczba reprezentująca dany symbol odejmowana jest wówczas, gdy następny symbol ma większą od niej wartość. W prze- ciwnym wypadku wykonywane jest dodawanie. Na przykład wartość liczby MCCXCIX wyznacza się następująco: MCCXCIX = 100010+10010+10010–1010+10010–110+1010 = 129910. Zadanie 2.9. Zamień liczby podane w systemie rzymskim na system dziesiętny: a) MXLVIII, b) MCMLXXXIV, c) CMXLVII, d) DXLIX, e) MMMCDI. 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 73 Zadanie 2.10. Zamień liczby podane w systemie dziesiętnym na system rzymski: a) 199910 , b) 18410 , c) 287610 , d) 301210 , e) 48810 . Zadanie 2.11. Podaj specyfi kację zadania i skonstruuj algorytm w postaci schematu blokowego i programu realizujący konwersję liczb z systemu rzymskiego na dziesiętny. Zadanie 2.12. Podaj specyfi kację zadania i skonstruuj algorytm w postaci programu realizujący konwersję liczb z systemu dziesiętnego na rzymski. 2.3.2. Konwersje pozycyjnych systemów liczbowych Konwersja systemu dziesiętnego na inny pozycyjny system liczbowy W s k a z ó w k a Aby zamienić liczbę nieujemną zapisaną w systemie decymalnym na wartość w systemie binarnym, należy powtarzać dzielenie z resztą tej liczby przez podstawę systemu dwójkowego, dopóki w wyniku takiego dzielenia nie uzyskamy 0. Wówczas otrzymane reszty z dzielenia, w kolejności od ostatniej obliczonej reszty do pierw- szej, stanowią rozwiązanie. Przykład 2.5. Przykład 2.5. Przykład 2.5. Przykład 2.5. Przeanalizujmy konwersję systemu dziesiętnego na dwójkowy na przykładzie liczbowym. Zapiszmy liczbę 12510 w systemie binarnym: 125 62 31 15 7 3 1 : : : : : : : 2 2 2 2 2 2 2 = = = = = = = 62 31 15 7 3 1 0 reszta 1 reszta 0 reszta 1 reszta 1 reszta 1 reszta 1 reszta 1 W wyniku dzielenia uzyskaliśmy zero, więc obliczenia zostały zakończone. Rozwiązanie odczytujemy, rozpoczynając od reszty uzyskanej na końcu, stąd 12510 = 11111012 . 74 Rozdział 2. Algorytmy i ich zastosowanie Wygodniejszy jest następujący zapis konwersji tych liczb: 1 0 1 1 1 1 1 125 62 31 15 7 3 1 0 Opracujmy algorytm wykonujący zamianę liczb zapisanych w systemie decymalnym na liczby binarne w postaci schematu blokowego (patrz rysunek 2.5) oraz programów w językach C++ (patrz punkt 3.6.1, „Tablice”) i Pascal. Dodatkowo na płycie CD znajduje się realizacja tego algorytmu wykonana za pomocą arkusza kalkulacyjnego (arkusz2_4.xls, arkusz2_4.ods). Specyfi kacja: Dane: Wynik: Liczba całkowita: liczba ≥ 0 (liczba w systemie dziesiętnym). Liczba całkowita: i 0 (liczba cyfr wartości otrzymanej po zamianie z systemu dziesiętnego na dwójkowy). i-elementowa tablica jednowymiarowa zawierająca liczby całkowite: W[0...i–1] (liczba zapisana w systemie dwójkowym uzyskana po zamianie z systemu dziesiętnego, której cyfry należy odczytać w kolejności W[i–1], W[i–2], …, W[0]). Funkcja w języku C++ (prog2_8.cpp): void oblicz (long liczba, int i, int W[]) { i=0; do { W[i]=liczba 2; liczba=liczba/2; i++; } while (liczba!=0); } 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 75 Procedura w języku Pascal (prog2_8.pas): procedure oblicz (liczba: longint; var i: integer; var W:tablica); begin i:=0; repeat W[i]:=liczba mod 2; liczba:=liczba div 2; i:=i+1 until liczba=0 end; START Rysunek 2.5. Schemat blokowy algorytmu realizującego konwersję liczb z systemu dziesiętnego na dwójkowy wczytaj: liczba i=0 W[i]=liczba 2 liczba=liczba / 2 i=i+1 NIE liczba!=0 TAK wypisz: W[i-1...0] STOP Omówioną metodę konwersji liczb z systemu decymalnego na binarny można zastoso- wać również przy zamianie systemu dziesiętnego na inne systemy liczbowe. Należy jednak pamiętać, że każdy z tych systemów ma inną podstawę. Na przykład zamieniając liczby systemu decymalnego na system oktalny, będziemy dzielić przez osiem, na system szesnastkowy — przez szesnaście itd. 76 Rozdział 2. Algorytmy i ich zastosowanie Przykład 2.6. Przykład 2.6. Przykład 2.6. Przykład 2.6. Zapiszmy liczbę 45910 w systemie szesnastkowym. Zwróć uwagę na cyfry, których war- tość jest większa niż 9. 459 28 1 : : : 16 16 16 = = = 28 1 0 reszta 11 = B reszta 12 = C reszta 1 Poniżej przedstawiono skrócony zapis konwersji tych liczb: 11 = B 12 = C 1 459 28 1 0 Uzyskaliśmy następujący wynik: 45910 = 1CB16. Zadanie 2.13. Przekonwertuj podane liczby całkowite z systemu dziesiętnego na sy- stemy o podstawach 2, 4, 8, 9, 16: a) 123410, b) 99910, c) 138010, d) 4910, e) 213510. Zadanie 2.14. Podaj specyfi kację zadania i skonstruuj algorytm w postaci listy kro- ków realizujący konwersję liczb zapisanych w systemie dziesiętnym na liczby w systemie o podstawie z przedziału [2, 9]. Zadanie 2.15. Podaj specyfi kację zadania i skonstruuj algorytm w postaci programu re- alizujący konwersję liczb zapisanych w systemie dziesiętnym na system szesnastkowy. Konwersja innych pozycyjnych systemów liczbowych na system dziesiętny W s k a z ó w k a Aby zamienić liczbę zapisaną w systemie binarnym na decymalny, należy wyzna- czyć wartość sumy cyfr tej liczby pomnożonych przez kolejne potęgi podstawy sy- stemu, czyli 2. 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 77 Przykład 2.7. Przykład 2.7. Przykład 2.7. Przykład 2.7. Przeanalizujmy przebieg działania tej metody na przykładzie liczbowym. Wykonajmy konwersję z systemu binarnego na decymalny liczby 10110112. Najpierw należy do każ- dej cyfry tej liczby dopasować odpowiednie potęgi liczby 2. Wartość mnożnika będącego potęgą liczby 2 zależy tutaj od pozycji cyfry w danej liczbie. 1 26 0 25 1 24 1 23 0 22 1 21 1 20 Następnie wyznaczamy wartość sumy iloczynów: + ⋅ 1 2 3 + ⋅ 0 2 2 + ⋅ 1 1 2 + ⋅ 1 2 0 = 91 10 . 6 ⋅ 1 2 + ⋅ 0 2 5 + ⋅ 1 2 4 Uzyskana wartość 9110 to liczba dziesiętna będąca wynikiem konwersji. Mamy więc 10110112 = 9110. W przypadku gdy chcemy zamieniać liczby z innych systemów pozycyjnych na decy- malny, postępujemy podobnie. Musimy jednak pamiętać o tym, by kolejne cyfry kon- wertowanej liczby mnożyć przez potęgi podstawy systemu, w którym jest zapisana. Przykład 2.8. Przykład 2.8. Przykład 2.8. Przykład 2.8. Zapiszmy liczbę 1A0B12 w systemie decymalnym: 1 123 A 122 0 121 B 120 1⋅123+10⋅122+0⋅121+11⋅120 = 317910 Otrzymaliśmy wynik: 1A0B12 = 317910. Zadanie 2.16. Zapisz podane liczby całkowite w systemie dziesiętnym: a) 10111012, b) 100111112, c) 10000012, d) 21203, e) 4305, f) 1456, g) 2648, h) 77778, i) 100078, 78 Rozdział 2. Algorytmy i ich zastosowanie j) ABCDE16, k) FFFF16, l) 1A17B016. Konwersje między systemami niedziesiętnymi W s k a z ó w k a Najczęściej stosowanymi systemami liczbowymi w informatyce są systemy: binarny, oktalny i heksadecymalny. Wykorzystanie systemu dwójkowego wynika ze sposobu zapisu liczb w pamięci komputera za pomocą bitów. Bit to najmniejsza jednostka informacji, która przyjmuje jedną z dwóch wartości, zwykle określanych jako 0 i 1. Z kolei systemy ósemkowy i szesnastkowy to systemy, których podstawy są potę- gami liczby 2. Wynika stąd możliwość wykonywania bezpośredniej konwersji mię- dzy tymi systemami a systemem binarnym. Liczba binarna zapisana na trzech miejscach ma wartości w przedziale [0, 111], co w sy- stemie dziesiętnym wynosi [0, 7]. Liczby zawarte w tym zakresie to wszystkie cyfry sy- stemu ósemkowego. Wykorzystajmy tę własność przy konwersji liczb między systemami binarnym i oktalnym. Przykład 2.9. Przykład 2.9. Przykład 2.9. Przykład 2.9. Wykonajmy konwersję liczby 10111011112 na system oktalny. Najpierw należy zamie- nianą liczbę pogrupować po trzy cyfry, rozpoczynając od prawej strony: 1 011 101 111 Następnie każdą z uzyskanych grup traktujemy jak cyfrę liczby, którą chcemy uzyskać w systemie oktalnym. Wykonujemy więc następujące obliczenia: 1 2 ⋅= 21 0 = 1 211 = ⋅ 1 1 2 + ⋅ 1 2 0 = 3 101 2 ⋅= 21 2 ⋅+ 20 1 ⋅+ 21 0 = 5 ⋅+ 21 1 ⋅+ 21 0 = 7 111 ⋅= 21 2 2 Uzyskujemy wynik: 10111011112 = 13578. Zamianę liczby zapisanej w systemie oktalnym na binarny realizujemy podobnie. Tym razem jednak każdą kolejną cyfrę liczby oktalnej konwertujemy na system binarny. W przypadku konwersji między systemem binarnym i heksadecymalnym tok myślenia jest podobny. Należy jednak uwzględnić grupowanie po cztery cyfry. Wynika to stąd, że liczba binarna zapisana na czterech miejscach ma wartości w przedziale [0, 1111], 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 79 co w systemie dziesiętnym daje [0, 15]. Tym razem są to wszystkie cyfry systemu szes- nastkowego. Przykład 2.10. Przykład 2.10. Przykład 2.10. Przykład 2.10. Przykład 2.10. Przekonwertujmy liczbę 1100110112 na system szesnastkowy: 1001 1011 1 1 2 ⋅= 21 0 = 1 1001 2 ⋅= 21 3 ⋅+ 20 2 ⋅+ 20 1 ⋅+ 21 0 = 9 1011 2 = ⋅ 1 2 3 + ⋅ 0 2 2 + ⋅ 1 1 2 + ⋅ 1 2 0 = 11 B = Po wykonaniu konwersji otrzymujemy: 1100110112 = 19B16. Zadanie 2.17. Zamień podane liczby całkowite z systemu dziesiętnego na ósemkowy i szesnastkowy z wykorzystaniem systemu dwójkowego: a) 52310, b) 45810, c) 39910, d) 87810, e) 100110, f) 111210, g) 205610. 2.3.3. Operacje arytmetyczne wykonywane w różnych systemach liczbowych Wykonując operacje arytmetyczne w różnych systemach liczbowych, należy pamię- tać przede wszystkim o podstawie tych systemów. W przypadku systemu dziesiętnego wiemy, że zarówno dodawanie, odejmowanie, jak i mnożenie wykonuje się w oparciu o podstawę systemu, którą jest liczba dziesięć. Gdy realizujemy operację dodawania, nadmiar dziesiątek przenosimy w lewo, natomiast odejmowanie wymaga „pożyczania” dziesiątek z lewej strony. Wykonajmy podstawowe operacje arytmetyczne w systemie binarnym. Rozpocznijmy od działania dodawania. W tym przypadku, gdy w wyniku dodawania otrzymamy wartość równą lub większą od dwóch, w rozwiązaniu wpisujemy resztę z dzielenia tej wartości przez 2, natomiast w lewo przenosimy wynik dzielenia całkowi- tego tej liczby przez 2. 80 Rozdział 2. Algorytmy i ich zastosowanie Przykład 2.11. Przykład 2.11. Przykład 2.11. Przykład 2.11. Przykład 2.11. Obliczmy sumę liczb w systemie binarnym: 110112+1111102. Pogrubieniem wyróżnione są wartości przenoszone w lewo. 1 + 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 1 Otrzymany wynik to: 110112+1111102 = 10110012. Przykład 2.12. Przykład 2.12. Przykład 2.12. Przykład 2.12. Przykład 2.12. Wyznaczmy systemie binarnym: 1111112+11102+101112+1101112. Ten przykład wydaje się trudniejszy, jednak jego reali- zacja opiera się na dokładnie tych samych zasadach. liczb zapisanych w sumę czterech 1 2 + 1 0 2 1 1 0 2 1 1 1 1 3 1 1 0 0 1 2 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 Po wykonaniu obliczeń uzyskujemy następujący wynik: 1111112+11102+101112+1101112 = 100110112. Kolejnym działaniem, które wykonamy w systemie binarnym, będzie odejmowanie. W tym przypadku problem pojawia się w sytuacji, gdy chcemy wykonać operację odej- mowania, a liczba, od której odejmujemy, jest zbyt mała. Wówczas należy pobrać war- tość z lewej strony. Każda jedynka pobrana bezpośrednio z lewej strony zamieniana jest na podstawę systemu, czyli dwa, a następnie wykonywane jest odejmowanie. Przykład 2.13. Przykład 2.13. Przykład 2.13. Przykład 2.13. Przykład 2.13. Obliczmy różnicę liczb zapisanych w systemie binarnym: 1101102–10102. Pogrubieniem wyróżnione są wartości uzyskane po pobraniu z lewej strony. 0 1 0 2 0 1 1 1 – 1 1 0 1 1 1 0 0 0 0 Wynikiem wykonanego działania jest: 1101102–10102 = 1011002. 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 81 Przykład 2.14. Przykład 2.14. Przykład 2.14. Przykład 2.14. Przykład 2.14. Wyznaczmy różnicę liczb binarnych: 1000002–1112 . Ten przykład jest trudniejszy, ale zasady identyczne. Dokładnie przeanalizuj wykonane działanie. 0 1 – 1 2 0 1 1 2 0 1 1 2 0 1 0 1 2 0 1 0 2 0 1 1 Uzyskaliśmy następujący wynik: 1000002–1112 = 110012 . Mnożenie liczb binarnych jest działaniem, które łączy w sobie operacje mnożenia i doda- wania. Najpierw wykonujemy mnożenie kolejnych cyfr jednej liczby przez kolejne cyfry drugiej liczby, a następnie uzyskane wyniki w odpowiedni sposób dodajemy. Przykład 2.15. Przykład 2.15. Przykład 2.15. Przykład 2.15. Przykład 2.15. Obliczmy iloczyn dwóch liczb w systemie binarnym: 1101112⋅10112 . Porównajmy wyko- nanie tego działania w systemie dwójkowym z mnożeniem w systemie dziesiętnym. 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 × 1 0 1 + 1 1 0 1 0 Po wykonaniu obliczeń otrzymujemy: 1101112⋅10112 = 10010111012 . Zadanie 2.18. Wykonaj następujące działania arytmetyczne w systemie binarnym: a) b) c) 10110 2 + 1101 2 ⋅ 111 2 , 111000 − 11 2 + 2 101100 110 ⋅ 2 , 2 101 1100 ⋅ 2 − 11011 2 + 10 , 2 2 d) 101110 − 10011 2 − 111 2 , 2 e) f) 110 11001 2 2 ⋅ + 110111 2 − 11 2 , 11111111 + . 2 1 2 Zadanie 2.19. Podaj specyfi kację zadania i skonstruuj algorytm w postaci programu wykonujący dodawanie dwóch wprowadzonych z klawiatury nieujemnych liczb całko- witych zapisanych w systemie binarnym. 82 Rozdział 2. Algorytmy i ich zastosowanie Przeanalizowaliśmy dokładnie realizację podstawowych działań arytmetycznych w syste- mie binarnym. Znając zasady wykonywania tych operacji, można przenieść je na płasz- czyznę innych pozycyjnych systemów liczbowych. Należy jednak pamiętać, aby w tych systemach stosować właściwą im podstawę. Na przykład w oktalnym — 8, w heksade- cymalnym — 16. Przykład 2.16. Przykład 2.16. Przykład 2.16. Przykład 2.16. Przykład 2.16. Wyznaczmy wartość wyrażenia: 3234⋅324–2134. 3 3 0 3 3 2 1 × 1 3 0 0 0 2 3 1 1 2 1 2 1 0 3 2 2 2 6 2 3 3 + – 2 3 3 3 Uzyskaliśmy następujący wynik: 3234⋅324–2134 = 301034. Zadanie 2.20. Wykonaj następujące działania arytmetyczne w podanych systemach liczbowych: a) 112 3 ⋅ 222 3 − 1100 b) 4430 5 + 302 31 5 5 ⋅ c) 707 8 + 1066 45 8 8 ⋅ , 3 , − 12 8 d) AB 10 16 − FF C 16 16 ⋅ + 1 16 , . Zadanie 2.21. Podaj, w jakich systemach pozycyjnych zostały wykonane następujące działania: a) 1001 + 10 − 1010 = 1, b) 244 ⋅ 2 − 14 = 474, c) (10 − 2) ⋅ 2 = 2, d) A1 − 3 ⋅ 10 + A = 80. Które z podanych działań można wykonać w różnych systemach liczbowych? 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 83 + − 1 n a x 1 + a x 1 +…+ − 2 n = + + a x a − 1 n n ) +…+ a x a n n ) +…+ a n + − 1 − 2 x a n = n − 2 n − + a x 1 3 n = = a x 0 ( a x 0 ( ( = a x 0 = … = ( ( = … ) − 1 + x a n = (2.11) Zadanie 2.22. Podaj specyfi kację zadania i skonstruuj algorytm w postaci programu wykonujący dodawanie dwóch wprowadzonych z klawiatury nieujemnych liczb całko- witych zapisanych w systemie liczbowym o podstawie z przedziału [2, 9], również wpro- wadzonej z klawiatury. Wynik niech będzie wypisany w tym samym systemie. 2.3.4. Wyznaczanie wartości wielomianu za pomocą schematu Hornera Schemat Hornera jest najszybszym sposobem obliczania wartości wielomianu. Przeanali- zujmy działanie tej metody, przekształcając ogólny wzór na wartość wielomianu stopnia n. Dany mamy wielomian stopnia n, gdzie n ≥ 0: + W omawianym algorytmie należy stosować grupowanie wyrazów tak długo, aż pozo- stanie dwumian. ( ) w x ( ) xw axa xa 0 (2.10) xa 1 … + = + + . − 1 − 1 − 1 n n n n n n n Schemat Hornera ma więc następującą postać: ( ( a x a 0 1 + ) + x a 2 ) x +…+ a n − 2 ) + x a n − 1 ) + x a n ( ) w x n ( ( = … ( ( a x a x a 0 2 ) + + 1 ) x +…+ a n − 2 + x a n − 1 ) ) + x a . n Porównując wzory 2.10 i 2.12 na obliczanie wartości wielomianu, łatwo zauważyć, że w schemacie Hornera wykonywana jest mniejsza liczba mnożeń. (2.12) Przykład 2.17. Przykład 2.17. Przykład 2.17. Przykład 2.17. Przykład 2.17. Obliczmy wartość wielomianu w(x) = 2x3+4x2–3x+7 dla x = 3, wykorzystując schemat Obliczmy wartość wielomianu Hornera. Współczynnikami wielomianu są tutaj a0 = 2, a1 = 4, a2 = –3, a3 = 7, a stopień wielomianu n wynosi 3. + 4 x ) + 4 x ( ) w x 3 2 = = − + = 7 3 x ) − + 3 7 x x 2 x ( ( 2 Stąd dla x = 3 mamy: = ⋅ − ⋅ + = + ⋅ 3 2 2 3 4 3 3 3 7 ( ) ) ( = ⋅ − ⋅ + = ⋅ + 2 3 4 3 3 3 7 ) ( ⋅ + = ⋅ − = 10 3 3 3 7 = ⋅ + = 27 3 7 = 88 ( ) 3 w 84 Rozdział 2. Algorytmy i ich zastosowanie Porównajmy liczbę działań wykonywanych przy obliczaniu wartości wielomianu po wy- braniu każdego ze wzorów. ( ) xw ⋅= 2 ⋅ xxx ⋅+⋅ 4 +⋅−+⋅ xx x W powyższym przykładzie wykonano sześć operacji mnożenia oraz trzy operacje do- dawania. 7 ( ) 3 W przypadku schematu Hornera wzór można przedstawić następująco: ( ) xw = ( ( 2 +⋅ x ) ( −+⋅ x ) ) +⋅ 3 x 4 7 . Liczba wykonanych działań jest tutaj znacznie mniejsza: trzy mnożenia i trzy dodawania. Zadanie 2.23. Opierając się na powyższej analizie, wyznacz ogólną liczbę operacji mnożenia i dodawania przy obliczaniu wartości wielomianu stopnia n. Na podstawie uzyskanych wyników podaj złożoność czasową obydwu algorytmów. Wyznaczając wartość wielomianu schematem Hornera (patrz wzór 2.12), należy wyko- nać następujące operacje: w a 0 w wx a 1 w wx a 2 w wx a 3 + + + = = = = … = = w wx a w wx a n + + − 1n Możemy więc zdefi niować wzór iteracyjny tego algorytmu: = w a 0  = w wx a  i + dla i = … 1, 2, , n (2.13) (2.14) Na podstawie otrzymanego wzoru 2.14 konstruujemy algorytm iteracyjny w postaci li- sty kroków, schematu blokowego (patrz rysunek 2.6) oraz programów w językach C++ i Pascal. Specyfi kacja: Dane: Liczba całkowita: n ≥ 0 (stopień wielomianu). n +1-elementowa tablica liczb rzeczywistych: A[0...n] (współczynniki wielo- mianu). Liczba rzeczywista: x (wartość argumentu). Wynik: Wartość rzeczywista wielomianu stopnia n dla wartości argumentu x. 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 85 Rysunek 2.6. Schemat blokowy algorytmu iteracyj- nego wyznaczającego wartość wielomianu schema- tem Hornera START wczytaj: n, A[0...n], x w=A[0] i=1 NIE i =n TAK wypisz: w w=w*x+A[i] STOP i=i+1 Lista kroków: Krok 0. Wczytaj wartości danych n, A[0...n], x. Krok 1. Przypisz w = A[0]. Krok 2. Dla kolejnych wartości i: 1, 2, …, n, wykonuj krok 3. Krok 3. Przypisz w = w·x+A[i]. Krok 4. Wypisz wartość wielomianu: w. Zakończ algorytm. Funkcja w języku C++ (prog2_9.cpp): double oblicz (double A[], int n, double x) { double w=A[0]; for (int i=1;i =n;i++) w=w*x+A[i]; return w; } Funkcja w języku Pascal (prog2_9.pas): function oblicz (A: tablica; n: integer; x: real): real; var w: real; i: integer; begin w:=A[0]; 86 Rozdział 2. Algorytmy i ich zastosowanie for i:=1 to n do w:=w*x+A[i]; oblicz:=w end; Przedstawiony algorytm można wykonać również rekurencyjnie. Nietrudno zauważyć za- leżność rekurencyjną, na podstawie której obliczana jest wartość wielomianu stopnia n. ( ) w x n = n a x 0 + a x 1 n − 1 +…+ a x a n n − 1 + = n − 1 ( ) x a a x − 0 1 n  +…+ a x 1 a n + + − 2 n w n − 1 ( ) x = w n − 1 ( ) x x a + n (2.15) Na podstawie wzoru 2.15 tworzymy defi nicję rekurencyjną, która wygląda następu- jąco: W s k a z ó w k a ( ) xw n =    a 0 ( ) xw − 1 n +⋅ ax dla dla n n = 0 0 n (2.16) Zastosowanie schematu Hornera nie ogranicza się do wyznaczania wartości wielo- mianu stopnia n. Algorytm ten wykorzystywany jest również do: • konwersji liczb z dowolnego pozycyjnego systemu liczbowego na system dzie- siętny; szybkiego obliczania wartości potęgi; jednoczesnego obliczania wartości wielomianu i jego pochodnej. • • Zadanie 2.24. Napisz program obliczający rekurencyjnie wartość wielomianu stop- nia n z wykorzystaniem schematu Hornera, zgodny z podaną powyżej specyfi kacją al- gorytmu iteracyjnego. 2.3.5. Zamiana liczb z dowolnego pozycyjnego systemu liczbowego na system dziesiętny z zastosowaniem schematu Hornera Schemat Hornera można zastosować do konwersji liczb zapisanych w różnych syste- mach liczbowych na system dziesiętny. Przypomnijmy, w jaki sposób dokonujemy ta- kiej zamiany w systemie binarnym, co zostało omówione w punkcie 2.3.2, „Konwersje pozycyjnych systemów liczbowych”. Zamieńmy liczbę 10111012 na wartość w systemie decymalnym: 1011101 2 = ⋅ 1 2 6 + ⋅ 0 2 5 + ⋅ 1 2 4 Łatwo zauważyć, że zapis liczby podczas obliczeń przypomina wielomian. Cyfry zamie- nianej liczby można więc potraktować jak współczynniki wielomianu, a podstawę sy- stemu jak wartość argumentu x. W tym przypadku mamy następującą sytuację: + ⋅ 1 2 3 + ⋅ 1 2 2 + ⋅ 1 0 2 + ⋅ 1 2 0 = 93 10 . 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 87 a a a a a a a x n = 6, 0 = 1, 1 = 0, 2 = 1, 3 = 1, 4 = 1, 5 = 0, 6 = 1, = 2. Taka interpretacja konwersji liczb na system dziesiętny umożliwia zastosowanie do jej realizacji schematu Hornera. Skonstruujmy więc algorytm wykonujący zamianę liczb z systemu dwójkowego na dziesiętny. Specyfikacja: Dane: Wynik: Liczba całkowita: n ≥ 0 (stopień wielomianu). n+1-elementowa tablica liczb całkowitych: A[0...n] (współczynniki wielo- mianu, czyli cyfry liczby zapisanej w systemie binarnym). Wartość wielomianu stopnia n dla argumentu 2 (liczba w systemie dziesięt- nym). Funkcja w języku C++ (prog2_10.cpp): long oblicz (int A[], int n) { long w=A[0]; for (int i=1;i =n;i++) w=w*2+A[i]; return w; } Funkcja w języku Pascal (prog2_10.pas): function oblicz (A: tablica; n: integer): longint; var w: longint; i: integer; begin w:=A[0]; for i:=1 to n do w:=w*2+A[i]; oblicz:=w end; 88 Rozdział 2. Algorytmy i ich zastosowanie Zadanie 2.25. Podaj specyfi kację zadania i skonstruuj rekurencyjny algorytm w po- staci programu realizujący konwersję liczb zapisanych w systemie o podstawie p, gdzie p jest dowolną liczbą naturalną z przedziału [2, 9], na system dziesiętny z zastosowa- niem schematu Hornera. Zadanie 2.26. Podaj specyfi kację zadania i skonstruuj iteracyjny algorytm w postaci programu realizujący konwersję liczb zapisanych w systemie szesnastkowym na system dziesiętny z zastosowaniem schematu Hornera. 2.3.6. Reprezentacja danych liczbowych w komputerze Binarna reprezentacja liczb ujemnych Dane w komputerze zapisywane są w postaci liczb binarnych. Wynika to stąd, że naj- mniejsza jednostka informacji, czyli bit, służy do zapisu jednej cyfry systemu dwójkowego: 0 lub 1. Dotychczas poznaliśmy reprezentację binarną liczb całkowitych nieujemnych. War- tości ujemne zapisuje się, używając kodu uzupełnieniowego do dwóch, zwanego kodem U2. Ogólny zapis liczby w kodzie U2 można przedstawić za pomocą następującego wzoru: y =    x 2 n + x dla dla x x ≥ 0 0 (2.17) gdzie: x — liczba, którą chcemy zapisać w kodzie U2; n — liczba bitów przeznaczonych do zapisania kodowanej liczby; y — liczba x zapisana za pomocą kodu U2. Liczba y po wykonaniu obliczeń przedstawiana jest w postaci binarnej. Zakres wartości liczby x, którą konwertujemy za pomocą kodu U2, zależy od liczby bi- tów przeznaczonych do zapisania tej liczby. Mając do dyspozycji n bitów, pierwszy bit rezerwujemy do oznaczenia znaku liczby (1 — liczba ujemna, 0 — liczba nieujemna), pozostałe n–1 bitów do zapisania liczby. Zauważmy, że rolę pierwszego bitu można rozu- mieć na dwa równoważne sposoby: reprezentuje on znak liczby x w kodzie U2, a zarazem jest pierwszym (najbardziej znaczącym) bitem nieujemnej liczby y w zwykłym układzie dwójkowym. Wartość kodowanej liczby x zawiera się więc w przedziale [–2n–1, 2n–1). Przykład 2.18. Przykład 2.18. Przykład 2.18. Przykład 2.18. Przykład 2.18. Załóżmy, że dysponujemy 1 bajtem (czyli 8 bitami) przeznaczonym do zapisania liczby. Stąd n = 8, a wartość kodowanej liczby x musi zawierać się w przedziale [–2n–1, 2n–1) = [–27, 27) = [–12810, 12810). Korzystając z wzoru, wyznaczmy wartość liczby x = –56 w ko- dzie U2. Musimy wykonać następujące obliczenia: y = 8 2 ( + − 56 ) = 256 56 200 10 − = . 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 89 Następnie konwertujemy uzyskaną wartość z systemu dziesiętnego na dwójkowy: = 11001000 . 200 10 2 Uzyskana liczba, y = 110010002, to zakodowana wartość liczby x = –5610. Zadanie 2.27. Zapisz podane liczby ujemne dla określonej wartości n za pomocą kodu U2. a) –10810 dla n = 8 bitów, b) –9910 dla n = 8 bitów, c) –24110 dla n = 16 bitów, d) –18910 dla n = 16 bitów. Stałopozycyjna reprezentacja liczb Stałopozycyjna reprezentacja liczb charakteryzuje się stałym położeniem przecinka, który oddziela część całkowitą od części ułamkowej zapisywanej liczby. Powoduje to, że taki zapis liczby jest dokładny tylko wtedy, gdy dana liczba nie wykracza poza zakres miej- sca, jakie zostało przeznaczone do jej zapisu. Załóżmy, że mamy do dyspozycji 2 bajty (czyli 16 bitów) do zapisania liczby w repre- zentacji stałopozycyjnej. Wówczas podział na część całkowitą i ułamkową może przed- stawiać się jak na rysunku 2.7. Rysunek 2.7. Przykładowy podział na część całkowitą i ułamkową w stało- pozycyjnej reprezentacji liczb znak liczby część całkowita część ułamkowa (1 bit) (8 bitów) (7 bitów) W reprezentacji stałopozycyjnej liczba zapisywana jest w kodzie uzupełniającym do dwóch. Potrafimy już wykonywać konwersję liczby całkowitej pomiędzy systemami binarnym i decymalnym. Jednak aby przedstawić liczbę rzeczywistą z wykorzystaniem reprezen- tacji stałopozycyjnej, trzeba uwzględnić również część ułamkową. Konwertując liczby z systemu binarnego na decymalny, mnożymy kolejne cyfry tej liczby przez potęgi dwójki. W części ułamkowej mnożnikiem są ujemne potęgi liczby 2. 90 Rozdział 2. Algorytmy i ich zastosowanie Przykład 2.19. Przykład 2.19. Przykład 2.19. Przykład 2.19. Przykład 2.19. Zapiszmy liczbę rzeczywistą 101111,011012 w systemie dziesiętnym. Zaczynamy od do- pasowania potęg liczby 2 do kolejnych cyfr podanej wartości: 1 25 0 24 1 23 1 22 1 21 1 20 , 0 2–1 1 2–2 1 2–3 0 2–4 1 2–5 Następnie obliczamy wartość konwertowanej liczby w systemie dziesiętnym: 101111,01101 2 = ⋅ 1 2 5 + ⋅ 0 2 4 + ⋅ 1 2 3 + ⋅ 1 2 2 + ⋅ 1 1 2 + ⋅ 1 2 0 + ⋅ 0 2 − 1 + ⋅ 1 2 − 2 + ⋅ 1 2 − 3 + ⋅ 0 2 − 4 + ⋅ 1 2 − 5 = 47 13 32 10 . Zamiana liczby ułamkowej z systemu dziesiętnego na dwójkowy wykonywana jest przez mnożenie części ułamkowej przez 2 tak długo, aż w części ułamkowej uzyskamy zero lub zauważymy, że wynikiem jest ułamek nieskończony. Rozwiązaniem jest liczba utworzona z całkowitych części wyników uzyskiwanych podczas mnożenia liczby przez 2. Przykład 2.20. Przykład 2.20. Przykład 2.20. Przykład 2.20. Przykład 2.20. Przekonwertujmy liczbę ułamkową 0,182510 na system binarny. W tym celu należy wykonać mnożenie części ułamkowej tej liczby przez 2: 0,1825 0,375 0,75 1,5 1,0 0,1825 · 2 = = 0,375 · 2 = 0,75 · 2 0,5 · 2 = 0,375 0,75 1,5 1,0 Rozwiązaniem jest ułamek skończony. Widać to po wartości ostatniego wyniku 1,0, w któ- rym część ułamkowa wynosi zero. Uzyskaliśmy więc następujące rozwiązanie: 0,182510 = 0,00112. Poniżej pokazany został czytelniejszy zapis konwersji liczb ułamkowych z systemu de- cymalnego na binarny: 0 0 0 1 1 1825 375 75 5 0 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 91 Przykład 2.21. Przykład 2.21. Przykład 2.21. Przykład 2.21. Przykład 2.21. Przekonwertujmy liczbę 0,210 na system binarny. Rozwiązaniem będzie ułamek nieskoń- czony. 2 4 8 6 2 4 8 6 2 4 0 0 0 1 1 0 0 1 1 0 … Łatwo zauważyć, że sekwencja liczb „0011” będzie się powtarzać. Wynikiem jest więc ułamek okresowy 0,(0011)2. Zadanie 2.28. Przekonwertuj podane liczby rzeczywiste na system dziesiętny: a) 10100,111012, b) 0,01110112, c) 11,1100012, d) 10110011,111001012, e) 11011100,100101012. Zadanie 2.29. Przekonwertuj podane liczby rzeczywiste na system binarny: a) 852,687510, b) 620,0937510, c) 612,0312510, d) 1536,992187510, e) 2707,773437510. Zadanie 2.30. Wykonaj następujące operacje arytmetyczne w systemie binarnym: a) 1110,0112·10001,001112, b) 1111,0012+100000,110112, c) 10011,010112–100,10112. 92 Rozdział 2. Algorytmy i ich zastosowanie liczba = m⋅2c, Zmiennopozycyjna reprezentacja liczb Zmiennopozycyjna reprezentacja liczb charakteryzuje się zmiennym położeniem prze- cinka, które zależy od zapisywanej liczby. Ogólny wzór na wartości w tej reprezentacji przedstawia się następująco: gdzie: liczba — liczba, którą chcemy zapisać w reprezentacji zmiennopozycyjnej; m — mantysa (ułamek właściwy); c — cecha (liczba całkowita). Ponadto mantysa powinna spełniać warunek |m|∈[0,5, 1). Wówczas kodowana liczba jest w postaci znormalizowanej. (2.18) Aby wyznaczyć wartość liczby zapisanej w reprezentacji zmiennopozycyjnej, trzeba znać wartości mantysy i cechy. Na rysunku 2.8 przedstawiono grafi cznie zapis zmiennopozy- cyjny, z uwzględnieniem podziału na cechę i mantysę. Cecha i mantysa zapisywane są jako liczby stałopozycyjne w kodzie U2. cecha mantysa Rysunek 2.8. Przykładowy podział na ce- chę i mantysę w zmiennopozycyjnej repre- zentacji liczb znak cechy (1 bit) znak mantysy (1 bit) Przykład 2.22. Przykład 2.22. Przykład 2.22. Przykład 2.22. Przykład 2.22. Załóżmy, że daną mamy liczbę 0000111011100001 zapisaną w reprezentacji zmiennopo- zycyjnej. Podana liczba zajmuje 2 bajty (czyli 16 bitów), z czego 7 bitów to cecha, a po- zostałe 9 bitów to mantysa. Wówczas liczba składa się z następujących elementów: • • • • 0 — bit znaku cechy, 000111 — cecha, 0 — bit znaku mantysy, 11100001 — mantysa. Zarówno cecha, jak i mantysa to w tym przypadku liczby nieujemne, o czym świadczą bity znaku równe zero. Wyznaczmy wartości cechy i mantysy: c = 111 2 = ⋅ 1 2 2 + ⋅ 1 1 2 + ⋅ 1 2 0 = 7 10 , 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 93 m = 0,11100001 2 = ⋅ 1 2 − 1 + ⋅ 1 2 − 2 + ⋅ 1 2 − 3 + ⋅ 0 2 − 4 + ⋅ 0 2 − 5 + ⋅ 0 2 − 6 + ⋅ 0 2 − 7 + ⋅ 1 2 − 8 = 225 256 10 = 0,87890625 10 . Następnie, korzystając z podanego wzoru 2.18, obliczmy wartość zakodowanej liczby: 225 256 liczba m= ⋅ c 2 = ⋅ 7 2 = 0,87890625 2 ⋅ 7 = 112,5 10 . W reprezentacji zmiennopozycyjnej nie każdą liczbę rzeczywistą można zapisać dokład- nie. Liczby te są najczęściej reprezentowane w sposób przybliżony. Na dokładność ma wpływ liczba cyfr w mantysie, natomiast od liczby cyfr w cesze zależy, jak duże liczby mogą być zapisywane. Zadanie 2.31. Wyznacz wartości dziesiętne liczb podanych w reprezentacji zmienno- pozycyjnej (cecha i mantysa oddzielone są odstępem): a) 000000010 0110011, b) 0001010 010000101, c) 0000011 010100001. 2.3.7. Błędy w obliczeniach Notacja naukowa liczb W notacji naukowej liczby zapisuje się w postaci: , liczba m= ⋅ 10c gdzie: liczba — liczba, którą chcemy zapisać w notacji naukowej, m — mantysa, c — cecha. (2.19) Mówimy, że zapis liczby jest znormalizowany, jeżeli m ∈ [ ) 0,1,1 . Przykład 2.23. Przykład 2.23. Przykład 2.23. Przykład 2.23. Przykład 2.23. Zapis naukowy może być stosowany do bardzo dużych liczb, na przykład: 25! = 15511210043330985984000000 = 0,15511210043330985984·1026. Liczba cyfr przeznaczonych na mantysę ma wpływ na dokładność obliczeń. Jeśli przyj- miemy, że na mantysę przeznaczono n cyfr, to do obliczeń wykorzystana zostanie zaokrą- glona wartość mantysy do n cyfr, którą oznaczymy m . Zmiennopozycyjna reprezentacja liczby liczba w komputerze będzie więc wartością przybliżoną równą: 94 Rozdział 2. Algorytmy i ich zastosowanie gdzie: liczba m= ⋅ 10c , (2.20) liczba — przybliżona wartość liczby, m — zaokrąglona wartość mantysy do n cyfr, c — cecha. Przykład 2.24. Przykład 2.24. Przykład 2.24. Przykład 2.24. Przykład 2.24. Przyjmijmy, że na mantysę przeznaczono sześć cyfr. Wówczas wartość 25! zapisana w tej notacji jest przybliżona, a więc niedokładna: 25! = 15511210043330985984000000 = 0,155112·1026. Przykład 2.25. Przykład 2.25. Przykład 2.25. Przykład 2.25. Przykład 2.25. Notacja naukowa stosowana jest również do zapisu liczb bliskich zeru, na przykład w celu wyrażenia masy elektronu. Wartość ta, zapisana w notacji naukowej dla mantysy zawie- rającej dwie cyfry, jest przybliżona i wynosi: 0,00000000000000000000000000000091095 kg = 0,91·10–30 kg. Przykład 2.26. Przykład 2.26. Przykład 2.26. Przykład 2.26. Przykład 2.26. W tabeli 2.1 podano przykładowe wartości i ich komputerową reprezentację dla liczby cyfr w mantysie n równej 6. Tabela 2.1. Przykładowe liczby i ich komputerowa reprezentacja dla n = 6 liczba liczba =2 3 0,666666(6) =13 7 1,(857142) 0,666667 10 ⋅ 0 1 0,185714 10 ⋅ 1 50000000000 = 0,00000000002 0,2 10 ⋅ − 10 Zadanie 2.32. Zapisz podane liczby w postaci naukowej znormalizowanej dla n = 5: a) 5124, b) π, c) 544327789045, d) 0,0000000012581479. 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 95 D e fi n i c j a D e fi n i c j a Błąd bezwzględny i względny Zajmijmy się teraz dokładnością liczb zapisanych w reprezentacji zmiennopozycyjnej. Obliczenia wykonywane na liczbach w zapisie zmiennopozycyjnym są niedokładne. Uzy- skane wyniki to najczęściej wartości przybliżone. Obarczone są więc błędami. Błędem bezwzględnym nazywamy wartość bezwzględną różnicy między wynikiem oczekiwanym a uzyskanym w obliczeniach. Błąd bezwzględny obliczamy wzorem: gdzie: x −=ε x x x , (2.21) xε — błąd bezwzględny, — oczekiwany wynik, x — uzyskany wynik. Błędem względnym nazywamy stosunek błędu bezwzględnego do oczekiwanego wyniku obliczeń. Dla użytkownika programu ważniejszy jest błąd względny, który pokazuje, jaki jest wpływ błędu bezwzględnego na uzyskany wynik obliczeń. Błąd względny obliczamy wzorem: δ x = x − x x = x ε x , (2.22) gdzie: xδ — błąd względny, xε — błąd bezwzględny, x — oczekiwany wynik, x — uzyskany wynik. 96 Rozdział 2. Algorytmy i ich zastosowanie Przykład 2.27. Przykład 2.27. Przykład 2.27. Przykład 2.27. Przykład 2.27. Oszacujmy błąd względny i bezwzględny dla różnicy liczb a = 22,84563391 i b = 17,799344112. Obliczenia wykonamy dla liczb a i b z dokładnością do 5 miejsc po przecinku, natomiast oczekiwany wynik będzie dokładną wartością różnicy tych liczb. Obliczmy wartość oczekiwanego wyniku: Następnym krokiem jest wyznaczenie wartości różnicy liczb a i b z dokładnością do 5 miejsc po przecinku: x = a–b = 22,84563391–17,799344112 = 5,046289798. = − = a b x Kolejną czynnością jest oszacowanie błędu bezwzględnego: 22,84563 17,79934 5,04629 − = . xε −= x x = ,5 046289798 − ,5 04629 = ,0 000000202 . Na podstawie wyznaczonego błędu bezwzględnego obliczamy błąd względny: δ x = x ε x = ,0 ,5 000000202 046289798 ≈ 0,0000000400294093454678… ≈ 0,00000004 = 0,4⋅10-7. Zadanie 2.33. Wyznacz obwód okręgu o promieniu r = 10 cm. Wykonaj obliczenia dla liczby π z dokładnością do 1, 2, 3, 4 i 5 miejsc po przecinku. Wyznacz błąd bezwzględny i względny przeprowadzonych obliczeń. Przyjmij, że oczekiwany wynik obliczany jest dla π z dokładnością do 10 miejsc po przecinku. Wybrane zadania maturalne Na załączonej do podręcznika płycie CD zamieszczono treści wybranych zadań matu- ralnych. Zaproponowane zadania wymagają od ucznia znajomości schematu Hornera i jego zastosowań, a także systemów liczbowych, ich konwersji oraz umiejętności wyko- nywania na nich operacji arytmetycznych. • • (Egzamin styczeń 2006 r. Arkusz I, zadanie 3.). (Informator maturalny od 2009 r. Arkusz I, poziom podstawowy, zadanie matura2.2.pdf matura2.3.pdf 2. KRAJE). matura2.4.pdf DODAWANIE LICZB TRÓJKOWYCH). matura2.5.pdf KOSMOS LICZB). matura2.6.pdf W SYSTEMACH DZIESIĘTNYM I DWÓJKOWYM). • • • (Informator maturalny od 2009 r. Arkusz II, poziom podstawowy, zadanie 5. (Egzamin próbny 2009 r. Arkusz I, poziom rozszerzony, zadanie 3. (Egzamin maj 2009 r. Arkusz I, poziom podstawowy, zadanie 2. CENY 2.3. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe 97 2.4. Generowanie liczb pierwszych i badanie, czy liczba jest pierwsza 2.4.1. Badanie, czy liczba jest pierwsza D e fi n i c j a Liczbę naturalną n większą od 1 nazywamy liczbą pierwszą, jeśli posiada tylko dwa dzielniki: 1 i n. Liczbę naturalną większą od 1, która nie jest liczbą pierwszą, na- zywamy liczbą złożoną. Natomiast liczby 0 i 1 nie są ani liczbami złożonymi, ani pierwszymi. Najprostszym algorytmem określającym, czy liczba n to liczba pierwsza, jest sprawdzenie, czy posiada ona więcej niż dwa dzielniki. Należy więc zbadać, czy w przedziale [2, n–1] znajduje się co najmniej jedna wartość całkowita, przez którą dzieli się liczba n. Specyfikacja: Dane: Liczba naturalna: n 1. Wynik: Komunikat informujący, czy liczba n jest liczbą pierwszą. Funkcja w języku C++ (prog2_11.cpp): bool sprawdz (int n) { for (int i=2;i n;i++) if (n i==0) return false; return true; } Funkcja w języku Pascal (prog2_11.pas): function sprawdz (n: integer): boolean; var pierwsza: boolean; i: integer; begin pierwsza:=true; i:=2; while i n do begin if n mod i = 0 then pierwsza:=false; i:=i+1 end; sprawdz:=pierwsza end; 98 Rozdział 2. Algorytmy i ich zastosowanie Przedstawiona funkcja jest typu logicznego. Jeśli po wykonaniu ma ona wartość true, liczba n jest liczbą pierwszą. W przeciwnym wypadku n jest liczbą złożoną. Spróbujmy zmodyfi kować powyższy algorytm w taki sposób, aby poprawić jego złożo- ność obliczeniową. W obecnej postaci złożoność tej metody jest klasy O(n). Wynika to stąd, że liczba operacji dominujących, czyli porównań, wynosi n–2. Zauważmy, że nie ma konieczności dalszego sprawdzania podzielności liczby n, jeśli zo- stanie znaleziony dzielnik tej liczby w przedziale [2, n–1]. Dodanie w pętli while wa- runku sprawdzającego, czy zmienna pierwsza jest równa true, spowoduje przerwanie pętli w przypadku znalezienia takiego dzielnika. Nie ma również sensu sprawdzanie wszystkich liczb z przedziału [2, n–1]. Załóżmy, że istnieje liczba x większa niż n , która jest dzielnikiem liczby n. Wynika stąd, że musi istnieć liczba y, będąca również dzielnikiem liczby n, taka, że n = x⋅y. Liczba y musia- łaby jednak być mniejsza od n , a to oznacza, że zostałaby znaleziona już w przedziale [2, n ]. W rzeczywistości wystarczy więc sprawdzenie, czy w przedziale [2, n ] znajduje się wartość, która jest dzielnikiem liczby n. Na rysunku 2.9 przedstawiony został schemat blokowy zmodyfi kowanego algorytmu sprawdzającego, czy dana liczba jest pierwsza. Dodatkowo na płycie CD znajduje się realizacja tego algorytmu wykonana za pomocą arkusza kalkulacyjnego (arkusz2_5.xls, arkusz2_5.ods). Rysunek 2.9. Schemat blokowy algo- rytmu sprawdzającego, czy dana liczba jest pierwsza START wczytaj: n i=2 pom=sqrt(n) NIE i =pom TAK wypisz: „TAK” TAK n i==0 NIE STOP wypisz: „NIE” i=i+1 STOP 2.4. Generowanie liczb pierwszych i badanie, czy liczba jest pierwsza 99 Liczba operacji dominujących, czyli porównań, w tym algorytmie jest tym większa, im później zostaje znaleziona liczba będąca dzielnikiem n. Największa liczba porównań będzie więc wykonana w sytuacji, gdy n jest liczbą pierwszą. Złożoność tego algorytmu jest więc rzędu O( n ). Funkcję realizującą ten algorytm można uruchomić w pętli generującej wartości z okre- ślonego zakresu, uzyskując w ten sposób metodę wyznaczania wszystkich liczb pierw- szych z podanego zakresu liczb. Zadanie 2.34. Napisz program sprawdzający, czy liczba wczytana z klawiatury jest pierwsza. Skonstruuj algorytm zgodny ze schematem blokowym przedstawionym na rysunku 2.9. 2.4.2. Sito Eratostenesa Sito Eratostenesa to algorytm generujący liczby pierwsze z przedziału [2, n]. Działanie tego algorytmu opiera się na własności liczb złożonych mówiącej, że liczba złożona jest wielokrotnością co najmniej jednej liczby pierwszej. Na przykład wartość 10 jest wie- lokrotnością liczb 2 i 5, liczba 9 to wielokrotność liczby 3, a liczba 24 to wielokrotność liczb 2, 4, 6, 8 i 12. Twórcą omawianej w tym punkcie metody jest Eratostenes z Cyreny, grecki matematyk żyjący około II wieku p.n.e. Algorytm ten nazywamy „sitem”, ponieważ w kolejnych krokach „odsiewane” są liczby złożone będące wielokrotnościami znalezionych liczb pierwszych. Operacje wykonywane są w określonym przedziale [2, n]. Wynikiem jest uzyskanie wszystkich liczb pierwszych z tego zakresu. Rozpoczynamy od najmniejszej liczby pierwszej, którą jest 2. Usuwamy wszystkie wielokrotności tej liczby, a wartość 2 oznaczamy jako liczbę pierwszą. Następ- nie przechodzimy do następnej nieskreślonej liczby, którą jest 3. „Odsiewamy” jej wie- lokrotności i oznaczamy ją jako liczbę pierwszą. Kontynuujemy te działania, wybierając kolejno tylko te liczby z przedziału [2, n], które nie zostały jeszcze „odsiane”. Przykład 2.28. Przykład 2.28. Przykład 2.28. Przykład 2.28. Przykład 2.28. Załóżmy, że w tablicy T indeks elementu i to wartość kolejnej liczby z podanego zakresu, natomiast wartość elementu tablicy T[i] to informacja, czy i jest liczbą pierwszą. Przeanalizujmy działanie algorytmu dla n = 10. Naszym zadaniem jest znalezienie wszyst- kich liczb pierwszych z przedziału [2, 10]. Przed rozpoczęciem generowania liczb pierwszych należy wszystkim elementom tablicy T przypisać wartość 1: T[i] = 1, dla i = 2, 3, ..., n. W ten sposób na początku oznaczamy wszystkie liczby jako pierwsze. W kolejnych krokach algorytmu, po znalezieniu liczby złożonej (jako wielokrotności wybranej liczby pierwszej), zmieniamy wartość elementu tablicy o numerze i (gdzie i jest wyznaczoną liczbą złożoną) na 0: T[i] = 0. 100 Rozdział 2. Algorytmy i ich zastosowanie i T[i] 2 1 3 1 4 1→0 5 1 6 1→0 7 1 8 1→0 9 1 10 1→0 Pierwszą znalezioną najmniejszą liczbą pierwszą jest 2, co zaznaczono kolorem niebie- skim. Szarym tłem wyróżniono jej wielokrotności, które zostały oznaczone zerami. i T[i] 2 1 3 1 4 0 5 1 6 0 7 1 Drugą liczbą pierwszą jest 3, a jej wielokrotności to 6 i 9. i T[i] i T[i] 2 1 2 1 3 1 3 1 4 0 4 0 5 1 5 1 6 0 6 0 7 1 7 1 8 0 8 0 8 0 9 1→0 9 0 9 0 10 0 10 0 10 0 W następnych dwóch krokach algorytmu odnajdujemy kolejno wartości 5 i 7. Wynikiem działania tej metody jest tablica T[2...10], w której jeśli T[i] = 1, to i jest liczbą pierwszą, natomiast jeśli T[i] = 0, to i nie jest liczbą pierwszą. Konstruując algorytm, zamiast wartości liczbowych 0 i 1 można zastosować wartości typu logicznego. Wówczas liczbie 1 odpowiadałoby true, natomiast 0 — false. Specyfi kacja: Dane: Wynik: Liczba naturalna: n 1. Liczby pierwsze z przedziału [2, n]: tablica jednowymiarowa T[2...n], w której jeśli T[i] = 1, to i jest liczbą pierwszą, natomiast jeśli T[i] = 0, to i jest liczbą złożoną. Lista kroków algorytmu: Krok 0. Wczytaj wartość danej n. Krok 1. Przypisz elementom tablicy T wartości początkowe 1. Krok 2. Przypisz najmniejszą liczbę pierwszą zmiennej i: i = 2. Krok 3. Krok 4. Krok 5. Znajdź wszystkie wielokrotności liczby i z przedziału [2·i, n] oraz oznacz je jako liczby złożone, czyli zmień tym elementom tablicy T wartość na 0. Przejdź do kolejnej liczby nieoznaczonej jako złożona większej od i z przedziału [i+1, n] oraz — jeśli zostanie znaleziona — przejdź do kroku 3., w przeciw- nym razie przejdź do kroku 5. Wypisz wszystkie liczby pierwsze z przedziału [2, n], czyli indeksy tych ele- mentów tablicy T, których wartość jest równa 1. Zakończ algorytm. 2.4. Generowanie liczb pierwszych i badanie, czy liczba jest pierwsza 101 Funkcja w języku C++ (prog2_12.cpp): void generuj (int T[], int n) { int i, m; for (i=2;i =n;i++) T[i]=1; i=2; while (i =n) { m=2*i; while (m =n) { T[m]=0; m+=i; } do i++; while (T[i]==0 i =n); } } Procedura w języku Pascal (prog2_12.pas): procedure generuj (var T: tablica; n: integer); var i, m: integer; begin for i:=2 to n do T[i]:=1; i:=2; while i =n do begin m:=2*i; while m =n do begin T[m]:=0; m:=m+i end; repeat i:=i+1 until (T[i]=1)or(i n) end end; 102 Rozdział 2. Algorytmy i ich zastosowanie P0⋅P1⋅...⋅Pk–1, Zadanie 2.35. Czy można poprawić złożoność obliczeniową przedstawionego algo- rytmu? Czy istnieje konieczność sprawdzania wszystkich liczb z przedziału [2, n]? Za- proponuj rozwiązanie i uzasadnij swoją odpowiedź. Zadanie 2.36. Liczbę naturalną większą od 1 można przedstawić jako iloczyn k liczb pierwszych (gdzie k jest liczbą naturalną większą od 0) następującej postaci: gdzie: Podaj specyfi kację zadania i skonstruuj algorytm w postaci listy kroków i programu re- alizujący rozkład liczby naturalnej na czynniki pierwsze P0, P1, ..., Pk–1. Przyjrzyj się przykładowi rozkładu liczby 100 na czynniki pierwsze: P0 ≤ P1 ≤ ... ≤ Pk–1, Pi jest liczbą pierwszą, dla i = 0, 1, ..., k–1. 100 = 2·2·5·5. Zauważ, że podany rozkład można przedstawić jako iloczyn potęg liczb pierwszych: 100 = 22·52. Wybrane zadania maturalne Na załączonej do podręcznika płycie CD zamieszczono treści wybranych zadań matu- ralnych oraz niezbędne dane. Zaproponowane zadania wymagają od ucznia znajomości zagadnień związanych z liczbami pierwszymi. • (Informator maturalny od 2009 r. Arkusz I, poziom podstawowy, zadanie 1. matura2.7.pdf ALGORYTM). matura2.8.pdf LICZBY PIERWSZE). matura2.9.pdf PÓŁPIERWSZE). matura2.10.pdf PIERWSZE). matura2.11.pdf KŁAD LICZBY). • • • • (Informator maturalny od 2009 r. Arkusz I, poziom rozszerzony, zadanie 2. (Egzamin próbny 2009 r. Arkusz II, poziom podstawowy, zadanie 5. LICZBY (Egzamin maj 2009 r. Arkusz II, poziom podstawowy, zadanie 5. LICZBY (Egzamin maj 2010 r. Arkusz I, poziom podstawowy, zadanie 2. ROZ- 2.4. Generowanie liczb pierwszych i badanie, czy liczba jest pierwsza 103 Skorowidz A Agile, 292 alfabet Morse’a, 54 algorytm, 9, 10, 11 asymetryczny, 54 blokowy, 54 delty, 22 dobrze określony, 58 efektywność, 57, 120 Euklidesa, 66, 71 Herona, 150 iteracyjny, Patrz: iteracja liniowy, 16, 104, 183 Newtona-Raphsona, 149 niestabilny równania kwadratowego, 23 optymalny, 58 podstawieniowy, 193 poprawność, 57, 58 przestawieniowy, Patrz: szyfrowanie przestawieniowe rekurencyjny, Patrz: rekurencja RSA, 200 sekwencyjny, Patrz: algorytm liniowy skończony, 57, 58 sortujący, 124, 127, 130, 140, 145, 181 stabilny równania kwadratowego, 22, 25 strumieniowy, 54 symetryczny, 54 uniwersalność, 58 z warunkami, 16, 18 zachłanny, 50, 164, 171 złożoność czasowa, 55 kwadratowa, 56 liniowa, 56 liniowo-logarytmiczna, 56 logarytmiczna, 56 obliczeniowa, 55 oczekiwana, 55 pamięciowa, 55 pesymistyczna, 55 wykładnicza, 57 algorytmika, 9 anagram, 54, 179, 181 aproksymacja, 149 B Bellman Richard Ernest, Patrz: zasada optymalności Bellmana blok decyzyjny, 13 operacyjny, 13 wejścia, 13 wyjścia, 13 błąd, 94 bezwzględny, 96 względny, 96 C całka oznaczona Riemanna, 152 całkowanie numeryczne, 153, 154 cecha, 93 ciąg liczbowy, 104, 108 Fibonacciego, 39 monotoniczny, 117 nieuporządkowany, 49 sortowanie, 119 uporządkowany, 47 D dane reprezentacja, 89 tablicowe, Patrz: tablica typ, 10, 240, 257 wejściowe, 9, 10, 16 wyjściowe, 10 Skorowidz 297 dowód poprawności, 11 drzewo algorytmu, 10, 14 binarne, 282, 283 wyrażenia, 10 E Erastotenes, 100 F Fibonacci Leonardo, 39 FIFO, 278 funkcja, 241 beztypowa, 252 definicja, 241 deklaracja, 241 iteracyjna, Patrz: iteracja logiczna, 252 matematyczna, 224 miejsce zerowe, 160 parametr aktualny, 242 parametr formalny, 242 przeciążenie, Patrz: funkcja przeładowanie przeładowanie, 252 rekurencyjna, Patrz: rekurencja struktura, 241 wywołanie, 243 zależności, 56 G gałąź, 14 generator aplikacji, 204 Delphi, 204 Visual Basic, 204 generator liczb losowych, Patrz: liczby losowe H Heron, Patrz: wzór Herona 298 Skorowidz I informacje początkowe, Patrz: dane wejściowe instrukcja break, 239 continue, 239 do-while, 236 for, 234 iteracyjna, Patrz: iteracja przypisania, 226 sterująca, 238 warunkowa, 227 while, 233 wyboru, 230 złożona, 227 interpreter, 205 inżynieria oprogramowania, 291 metodyka zwinna, 293 model kaskadowy, 291 Scrum, 293 iteracja, 28, 85, 135, 233, 252 J język programowania, 15, 203 Algol, 204 Basic, 204, 205 C++, 11, 15, 203, 204, 205 Cobol, 204 deklaratywny, Patrz: język programowania logiczny Delphi, 204 Fortran, 204 imperatywny, Patrz: język programowania statyczny Java, 204 logiczny, 205 niskiego poziomu, 203, 204 Pascal, 11, 204 Prolog, 205 Visual Basic, 204 wewnętrzny, 203 wysokiego poziomu, 15, 203, 204 zewnętrzny, 203 K klasa funkcji zależności, Patrz: funkcja zależności klucz prywatny, 54, 200 publiczny, 54, 200 kod ASCII, 54 U2, 89 uzupełnieniowy do dwóch, Patrz: kod U2 kodowanie, 54 kolejka, 278 komentarz, 226 kompilator, 205 korzeń, 14 kryptoanaliza, 53 kryptografi a, 53, 189 kryptologia, 53 L liczby Fibonacciego, 41 losowe, 225 notacja naukowa, Patrz: notacja naukowa pierwsze, 98, 100 stałopozycyjne, 90 ujemne, 89 złożone, 98, 100 zmiennopozycyjne, 93 lider, 113 lista, 279 cykliczna, 280, 282 dwukierunkowa, 280, 282 jednokierunkowa, 280 kroków, 11 numerowana, 11 Ł łańcuch, 265, 270 Łukasiewicz Jan, 186 M maksimum, 110, 135 maksymalizacja, 50 manipulator, 212 mantysa, 93, 94 metoda dziel i zwyciężaj, 47, 135 liniowa, Patrz: algorytm liniowy zachłanna, Patrz: algorytm zachłanny metody numeryczne, 149 metodyka zwinna, Patrz: inżynieria oprogramowania metodyka zwinna minimalizacja, 50 minimum, 110, 135 monotoniczność, 117 N najmniejsza wspólna wielokrotność, 66, 71 największy wspólny dzielnik, 66 notacja dużego O, 57 infi ksowa, 186 naukowa, 94 odwrotna polska, postfi ksowa, Patrz: odwrotna notacja polska Patrz: odwrotna notacja polska prefi ksowa, 186 NWD, Patrz: największy wspólny dzielnik NWW, Patrz: najmniejsza wspólna wielokrotność O odległość punktu od prostej, Patrz: punkt odległość od prostej od punktu, Patrz: punkt odległość od punktu odwrotna notacja polska, 186, 188 oktalny, Patrz: system liczbowy oktalny ONP, Patrz: odwrotna notacja polska Skorowidz 299 operacja dominująca, 55, 56 strumieniowa, 285 wejścia-wyjścia, 209, 285 operator alternatywa, 220 arytmetyczny, 218 dekrementacji, 219 dodawania, 218 dostępu, 272 dzielenia, 218 iloczyn logiczny, 220 inkrementacji, 219 koniunkcja, 220 logiczny, 220 mniejsze lub równe, 220 mniejsze, 220 mnożenia, 218 negacja, 220 odejmowania, 218 podstawienia, Patrz: operator przypisania przypisania, 217, 221 relacyjny, 220 reszty z dzielenia, 218 rozmiaru sizeof, 222 równe, 220 różne, 220 suma logiczna, 220 warunkowy, 222 większe lub równe, 220 większe, 220 zmniejszania i zwiększania, 219 optymalizacja, 50, 58 P palindrom, 175 parametr, 245 aktualny, Patrz: funkcja parametr aktualny formalny, Patrz: funkcja parametr formalny przekazywanie przez referencję, 246 300 Skorowidz przekazywanie przez wartość, 245 przekazywanie przez wskaźnik, 246 wartość domyślna, 252 pętla, Patrz: instrukcja do-while, instrukcja for, instrukcja while pierwiastek kwadratowy, 149 postać znormalizowana, 93 priorytet, 223 problem plecakowy, 164, 169, 171 wydawania reszty, 173 programowanie dynamiczne, 167, 169 zachłanne, Patrz: algorytm zachłanny prosta, 61 prostopadła, 63 równoległa, 63 przeszukiwanie binarne, 47, 56, 104 liniowe, 104 liniowe z wartownikiem, 108 pseudokod, 10 pseudorekurencja, 37 punkt odległość od prostej, 61 odległość od punktu, 63 R referencja, 217 rekurencja, 36, 40, 41, 45, 70, 138, 139, 144, 252 relacja, 217, 223 Reverse Polish Notation, Patrz: odwrotna notacja polska równanie kwadratowe, 21 S schemat blokowy, 11, 13 Hornera, 56, 84, 87 Scrum, Patrz: inżynieria oprogramowania Scrum silnia, 37 sito Eratostenesa, 100 sortowanie, Patrz też: algorytm sortujący bąbelkowe, 121 kubełkowe, 133 łańcucha znaków, 177 przez scalanie, 140 przez wstawianie, 127 przez wybór, 124 przez zliczanie, 130 szybkie, 145 w miejscu, 120 stała, 215 deklaracja, 215 steganografi a, 53 stos, 277 struktura, 271, 277, 280 dynamiczna, 276 system liczbowy, 72 addytywny, 72 binarny, Patrz: system liczbowy dwójkowy decymalny, Patrz: system liczbowy dziesiętny dwójkowy, 72, 77, 79, 88, 90, 91 dziesiętny, 9, 74, 77, 87, 88, 9
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Informatyka Europejczyka. Informatyka. Podręcznik dla szkół ponadgimnazjalnych. Zakres rozszerzony. Część 1 (Wydanie II)
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: