Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00562 007430 13583380 na godz. na dobę w sumie
Informatyka Europejczyka. Informatyka. Podręcznik dla szkół ponadgimnazjalnych. Część 1 - książka
Informatyka Europejczyka. Informatyka. Podręcznik dla szkół ponadgimnazjalnych. Część 1 - książka
Autor: Liczba stron: 288
Wydawca: Helion Edukacja Język publikacji: polski
ISBN: 83-246-0925-3 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> podręczniki szkolne >> szkoła ponadgimnazjalna
Porównaj ceny (książka, ebook, audiobook).

Numer dopuszczenia MEN 60/1/09/S

Z komputerami stykamy się dziś niemal każdego dnia. Wykorzystujemy je do pracy i rozrywki, wyszukiwania informacji w sieci, komunikowania się ze znajomymi i wielu innych zadań. Jednak komputer to nie tylko gry, edytory tekstu, poczta elektroniczna, portale społecznościowe czy komunikatory -- to także wiele przydatnych narzędzi, które stają się niezbędne do codziennego funkcjonowania we współczesnym świecie.

'Informatyka Europejczyka. Informatyka. Podręcznik dla szkół ponadgimnazjalnych. Część 1' przedstawia zagadnienia związane z algorytmiką i programowaniem. Dowiesz się z tego podręcznika, jakimi prawami rządzą się algorytmy, i nauczysz się rozpoznawać ich typy. Zyskasz możliwość samodzielnego analizowania algorytmów określających najczęstsze metody numerycznego rozwiązywania problemów obliczeniowych. W dalszej części podręcznika znajdziesz informacje dotyczące programowania w języku C++ -- typy danych i instrukcji, strukturę programu, sposoby realizacji typowych zadań programistycznych oraz podstawy programowania obiektowego.

Na płycie CD-ROM dołączonej do książki znajdziesz przykłady programów napisanych w językach C++ i Pascal, uzupełniający materiał dotyczący programowania obiektowego, dane do zadań, pliki potrzebne do wykonywania ćwiczeń oraz wybrane zadania z egzaminów maturalnych.

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

Darmowy fragment publikacji:

Informatyka Europejczyka. Informatyka. Podrêcznik dla szkó³ ponadgimnazjalnych. Czêœæ I Autor: Gra¿yna Zawadzka ISBN: 978-83-246-0925-3 Format: 170×240, stron: 288 Z komputerami stykamy siê dziœ niemal ka¿dego dnia. Wykorzystujemy je do pracy i rozrywki, wyszukiwania informacji w sieci, komunikowania siê ze znajomymi i wielu innych zadañ. Jednak komputer to nie tylko gry, edytory tekstu, poczta elektroniczna, portale spo³ecznoœciowe czy komunikatory – to tak¿e wiele przydatnych narzêdzi, które staj¹ siê niezbêdne do codziennego funkcjonowania we wspó³czesnym œwiecie. „Informatyka Europejczyka. Informatyka. Podrêcznik dla szkó³ ponadgimnazjalnych. Czêœæ I” przedstawia zagadnienia zwi¹zane z algorytmik¹ i programowaniem. Dowiesz siê z tego podrêcznika, jakimi prawami rz¹dz¹ siê algorytmy, i nauczysz siê rozpoznawaæ ich typy. Zyskasz mo¿liwoœæ samodzielnego analizowania algorytmów okreœlaj¹cych najczêstsze metody numerycznego rozwi¹zywania problemów obliczeniowych. W dalszej czêœci podrêcznika znajdziesz informacje dotycz¹ce programowania w jêzyku C++ – typy danych i instrukcji, strukturê programu, sposoby realizacji typowych zadañ programistycznych oraz podstawy programowania obiektowego. Na p³ycie CD-ROM do³¹czonej do ksi¹¿ki znajdziesz przyk³ady programów napisanych w jêzykach C++ i Pascal, uzupe³niaj¹cy materia³ dotycz¹cy programowania obiektowego, dane do zadañ, pliki potrzebne do wykonywania æwiczeñ oraz wybrane zadania z egzaminów maturalnych. (cid:129) Pojêcie algorytmu (cid:129) Sposoby przedstawiania algorytmów (cid:129) Metody programowania: liniowe, warunkowe, iteracja, rekurencja, „dziel i zwyciê¿aj”, zach³anna (cid:129) Analiza i realizacja algorytmów (cid:129) Podstawy kryptografii i wybrane algorytmy szyfruj¹ce (cid:129) Podstawy jêzyka C++: struktura programu, operacje wejœcia i wyjœcia, typy instrukcji, proste i z³o¿one typy danych, strukturalizacja programu, dynamiczne struktury danych, plikowe operacje wejœcia i wyjœcia oraz programowanie obiektowe Spis treści Spis treści Od autorek 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 elementó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. Kryptografia 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. Wyznaczanie największego wspólnego dzielnika 2.1.1. Algorytm Euklidesa 2.1.2. Obliczanie najmniejszej wspólnej wielokrotności i najmniejszej wspólnej wielokrotności dwóch liczb naturalnych 7 9 10 11 12 13 14 15 16 17 17 20 23 31 40 41 43 47 51 52 55 55 57 60 60 63 64 65 66 67 71  Część 1. Informatyka Europejczyka. Informatyka 2.2. Wyznaczanie wartości wielomianu, pozycyjne systemy liczbowe i reprezentacja danych liczbowych w komputerze 2.2.1. Systemy liczbowe 2.2.2. Konwersje pozycyjnych systemów liczbowych 2.2.3. Operacje arytmetyczne wykonywane w różnych systemach liczbowych 2.2.4. Wyznaczanie wartości wielomianu 2.2.5. Zamiana liczb z dowolnego pozycyjnego 2.2.6. Reprezentacja danych liczbowych w komputerze systemu liczbowego na system dziesiętny z zastosowaniem schematu Hornera za pomocą schematu Hornera 2.3. Generowanie liczb pierwszych i badanie, czy liczba jest pierwsza 2.3.1. Badanie, czy liczba jest pierwsza 2.3.2. Sito Eratostenesa 2.4. Przeszukiwanie ciągu liczbowego — metody liniowe 2.4.1. Liniowe przeszukiwanie ciągu liczbowego 2.4.2. Liniowe przeszukiwanie ciągu liczbowego z wartownikiem 2.5. Znajdowanie najmniejszego lub największego elementu w ciągu liczbowym 2.6. Znajdowanie lidera w zbiorze 2.7. Sprawdzanie monotoniczności ciągu liczbowego 2.8. Sortowanie ciągu liczbowego 2.8.1. Metody sortowania przez porównania 2.8.2. Sortowanie w czasie liniowym 2.9. Zastosowanie metody „dziel i zwyciężaj” 2.9.1. Jednoczesne znajdowanie najmniejszego 2.9.2. Sortowanie przez scalanie 2.9.3. Sortowanie szybkie i największego elementu z liczby nieujemnej — algorytm Newtona-Raphsona 2.10. Metody numeryczne i obliczenia przybliżone 2.10.1. Obliczanie wartości pierwiastka kwadratowego 2.10.2. Obliczanie pola obszaru 2.10.3. Znajdowanie przybliżonej wartości miejsca zerowego funkcji — metoda połowienia przedziałów ograniczonego wykresem funkcji 2.11. Wyznaczanie wartości wyrażenia zapisanego w odwrotnej notacji polskiej ONP  72 72 75 81 85 89 91 97 97 100 103 103 108 110 113 117 119 121 130 136 136 140 146 150 150 154 162 166 Spis treści 2.12. Zastosowanie programowania zachłannego 2.12.1. Problem plecakowy 2.12.2. Algorytm wydawania reszty 2.13. Wybrane algorytmy kryptograficzne 2.13.1. Szyfrowanie symetryczne 2.13.2. Szyfrowanie asymetryczne  Rozdział  3.  Programowanie w języku C++  3.1. Języki programowania — pojęcia, klasyfikacja, 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. Liczby losowe 3.2.6. Komentarze 3.3. Podstawowe konstrukcje algorytmiczne 3.3.1. Instrukcja pusta 3.3.2. Instrukcja przypisania 3.3.3. Instrukcja złożona 3.3.4. Instrukcje warunkowe 3.3.5. Instrukcja wyboru 3.3.6. Instrukcje iteracyjne 3.3.7. 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 3.7. Dynamiczne struktury danych 3.7.1. Stos 3.7.2. Kolejka 3.7.3. Lista 3.8. Plikowe operacje wejścia-wyjścia 3.8 277 169 169 179 182 182 194 197 198 200 201 204 209 213 221 222 223 223 223 224 224 227 230 235 236 238 238 240 241 248 254 254 262 268 272 273 275 276 279  Rozdział 2. Algorytmy i ich zastosowanie Funkcja w języku Pascal (prog2_5.pas): function nww (a, b: integer): integer; begin nww:=a*b div nwd(a,b) end; Zadanie 2.1. Podaj specyfikację zadania i skonstruuj algorytm w postaci schematu bloko- wego i programu wykonujący skracanie ułamków zwykłych. Licznik i mia- nownik ułamka wprowadź z klawiatury. Zadanie 2.2. Podaj specyfikację zadania i skonstruuj algorytm w postaci programu wy- konujący podstawowe operacje arytmetyczne na ułamkach zwykłych, w tym dodawanie, odejmowanie, mnożenie, dzielenie. Wynik wykonanej opera- cji powinien być przedstawiony w postaci skróconej, z wyłączeniem części całkowitej. 2.2. Wyznaczanie   wartości wielomianu,   pozycyjne systemy liczbowe   i reprezentacja danych   liczbowych w komputerze 2.2.1. Systemy liczbowe Systemem liczbowym nazywamy zbiór zasad określających sposób zapi- sywania 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 nazywa- my pozycją. 2 2.2. Wyznaczanie wartości wielomianu Do najważniejszych pozycyjnych systemów liczbowych wykorzystywanych w informatyce 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 ko- rzysta 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. Wykorzystanie liter w zapisie cyfr podyktowane jest konieczno- ścią jednoznacznej notacji liczby w tym systemie. Litery odpowiadają cyfrom, których wartości zapisane w układzie dziesiętnym są liczbami dwucyfrowymi: A16 = 1010, B16 = 1110, C16 = 1210, D16 = 1310, E16 = 1410, F16 = 1510. Gdybyśmy nie korzystali z liter, zapis liczby 11216 mógłby oznaczać 11216 lub B216 lub 1C16. Przy realizacji konwersji i działań arytmetycznych w różnych syste- mach liczbowych można zastosować udostępnioną w systemie Win- dows aplikację Kalkulator. Program ten umożliwia realizację obliczeń w następujących systemach: decymalnym (czyli dziesiętnym), binar- nym, oktalnym i heksadecymalnym. Wykonywać można zarówno konwersję pomiędzy wymienionymi systemami, jak i operacje aryt- metyczne. Aby uzyskać dostęp do tych systemów, należy po urucho- mieniu aplikacji Kalkulator wybrać w menu polecenie Widok-Naukowy. Najbardziej znanym systemem liczbowym, który nie jest pozycyjny, jest system rzymski. Zaliczany jest on do systemów zwanych addytywnymi. Charaktery- zują się one tym, że mają symbole dla kilku małych liczb oraz ich wielokrotności.  Rozdział 2. Algorytmy i ich zastosowanie W przypadku systemu rzymskiego dotyczy to wielokrotności liczb 5 i 10. Do- stępnych jest razem siedem znaków: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. Zapisywanie liczby w tym systemie polega na składaniu jej przez dodawanie lub odejmowanie kolejnych symboli o określonej wartości. Liczba reprezentu- jąca dany symbol odejmowana jest wówczas, gdy następny symbol ma większą od niej wartość. W przeciwnym 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.3. Zamień liczby podane w systemie rzymskim na system dziesiętny: a) MXLVIII, b) MCMLXXXIV, c) CMXLVII, d) DXLIX, e) MMMCDI. Zadanie 2.4. Zamień liczby podane w systemie dziesiętnym na system rzymski: a) 199910, b) 18410, c) 287610, d) 301210, e) 48810. Zadanie 2.5. Podaj specyfikację zadania i skonstruuj algorytm w postaci schematu blokowego i programu realizujący konwersję liczb z systemu rzymskiego na dziesiętny.  2.2. Wyznaczanie wartości wielomianu Zadanie 2.6. Podaj specyfikację zadania i skonstruuj algorytm w postaci programu realizu- jący konwersję liczb z systemu dziesiętnego na rzymski. 2.2.2. Konwersje pozycyjnych   systemów liczbowych Konwersja systemu dziesiętnego   na inny pozycyjny system liczbowy Aby zamienić liczbę nieujemną zapisaną w systemie decymalnym na wartość w systemie binarnym, należy powtarzać dzielenie z resztą tej liczby przez podstawę sytemu dwójkowego, dopóki w wyniku dzielenia nie uzyska- my 0. Wówczas otrzymane reszty z dzielenia stanowią rozwiązanie. Przykład 2.3. 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 reszta 1 31 reszta 0 15 reszta 1 7 reszta 1 3 reszta 1 1 reszta 1 0 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. Wygodniejszy jest następujący zapis konwersji tych liczb: 1 0 1 1 1 1 1 125 62 31 15 7 3 1 0  Rozdział 2. Algorytmy i ich zastosowanie Opracujmy algorytm wykonujący zamianę liczb zapisanych w systemie de- cymalnym na liczby binarne w postaci schematu blokowego (patrz rysunek 2.2) oraz programów w językach C++ (patrz punkt 3.6.1, „Tablice”) i Pascal. S p e c y f i k a c j a : Dane: Wynik: Liczba całkowita: liczba ≥ 0 (liczba w systemie dziesiętnym). Liczba całkowita: i 0 (liczba cyfr wartości otrzymanej po za- mianie 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 na- leży odczytać w kolejności W[i–1], W[i–2], …, W[0]). Rysunek 2.2.   Schemat blokowy algorytmu realizującego konwersję liczb z systemu dziesiętnego na dwójkowy START wczytaj: liczba i=0 W[i]=liczba 2 liczba=liczba / 2 i=i+1 NIE liczba!=0 TAK wypisz: W[0...i-1] STOP 6 2.2. Wyznaczanie wartości wielomianu Funkcja w języku C++ (prog2_6.cpp): void oblicz (long liczba, int i, int W[]) { i=0; do { W[i]=liczba 2; liczba=liczba/2; i++; } while (liczba!=0); } Procedura w języku Pascal (prog2_6.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; Omówioną metodę konwersji liczb z systemu decymalnego na binarny moż- na zastosować 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ą podsta- wę. Na przykład, zamieniając liczby systemu decymalnego na system oktalny, będziemy dzielić przez osiem, na system szesnastkowy — przez szesnaście itd. Przykład 2.4. Zapiszmy liczbę 45910 w systemie szesnastkowym. Zwróć uwagę na cyfry, któ- rych wartość jest większa niż 9. 28 1 0 reszta 11 = B reszta 12 = C reszta 1 = = = 459 : : 28 1 : 16 16 16 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.  Rozdział 2. Algorytmy i ich zastosowanie Zadanie 2.7. Przekonwertuj podane liczby całkowite z systemu dziesiętnego na systemy o podstawach 2, 4, 8, 9, 16: a) 123410, b) 99910, c) 138010, d) 4910, e) 213510. Zadanie 2.8. Podaj specyfikację zadania i skonstruuj algorytm w postaci listy kroków i pro- gramu realizujący konwersję liczb zapisanych w systemie dziesiętnym na licz- by w systemie o podstawie z zakresu [2; 9]. Zadanie 2.9. Podaj specyfikację zadania i skonstruuj algorytm w postaci programu rea- lizujący konwersję liczb zapisanych w systemie dziesiętnym na system szesnastkowy. Konwersja innych pozycyjnych   systemów liczbowych na system dziesiętny Aby zamienić liczbę zapisaną w systemie binarnym na decymalny, należy wyznaczyć wartość sumy cyfr tej liczby pomnożonych przez kolejne potęgi podstawy systemu, czyli 2. Przykład 2.5. Przeanalizujmy przebieg działania tej metody na przykładzie liczbowym. Wyko- najmy 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 8 2.2. Wyznaczanie wartości wielomianu Następnie wyznaczamy wartość sumy iloczynów: + ⋅ 1 2 1 + ⋅ 1 2 + ⋅ 0 2 + ⋅ 0 2 + ⋅ 1 2 6 ⋅ 1 2 2 5 4 + ⋅ 1 2 3 0 = . 91 10 Uzyskana wartość 9110 to liczba dziesiętna będąca wynikiem zamiany syste- mów. Mamy więc 10110112 = 9110. W przypadku, gdy chcemy zamieniać liczby z innych systemów pozycyj- nych na decymalny, postępujemy podobnie. Musimy jednak pamiętać o tym, by kolejne cyfry konwertowanej liczby mnożyć przez potęgi podstawy syste- mu, w którym jest zapisana. Przykład 2.6. Zapiszmy liczbę 1A0B12 w systemie decymalnym: A B 1 123 122 121 120 0 1⋅123+10⋅122+0⋅121+11⋅120 = 317910 Otrzymaliśmy wynik: 1A0B12 = 317910. Zadanie 2.10. 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, j) ABCDE16, k) FFFF16, l) 1A17B016. 9 Rozdział 2. Algorytmy i ich zastosowanie Konwersje między systemami niedziesiętnymi 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. Z kolei systemy ósemkowy i szesnastkowy to syste- my, których podstawy są potęgami liczby 2. Wynika stąd możliwość wykonywania bezpośredniej konwersji między tymi systemami a sy- stemem binarnym. Liczba binarna zapisana na trzech miejscach ma wartości w zakresie [0; 111], co w systemie dziesiętnym wynosi [0; 7]. Liczby zawarte w tym zakresie to wszystkie cyfry systemu ósemkowego. Wykorzystajmy tę własność przy kon- wersji liczb między systemami binarnym i oktalnym. Przykład 2.7. Wykonajmy konwersję liczby 10111011112 na system oktalny. Najpierw należy zamienianą 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: 0 0 21 211 2101 2111 = ⋅ = 1 2 1 1 = ⋅ + ⋅ = 3 1 2 1 2 1 + ⋅ + ⋅ = ⋅ 1 2 1 2 0 2 0 1 = ⋅ + ⋅ + ⋅ 1 2 1 2 1 2 2 2 0 = = 5 7 Uzyskujemy wynik: 10111011112 = 13578. Zamianę liczby zapisanej w systemie oktalnym na binarny realizujemy po- dobnie. 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 zakresie [0; 1111], co w systemie dziesiętnym daje [0; 15]. Tym razem są to wszystkie cyfry systemu szesnastkowego. 80 2.2. Wyznaczanie wartości wielomianu Przykład 2.8. Przekonwertujmy liczbę 1100110112 na system szesnastkowy: = ⋅ 1 2 1 21 1001 2 1011 2 1001 0 = 1 3 = ⋅ 1 2 1011 + ⋅ 0 2 2 + ⋅ + ⋅ 1 2 1 0 2 0 = 9 = ⋅ 1 2 3 + ⋅ 1 2 2 + ⋅ + ⋅ 1 2 1 0 2 0 = 11 B = Po wykonaniu konwersji otrzymujemy: 1100110112 = 19B16. Zadanie 2.11. Zamień podane liczby całkowite z systemu dziesiętnego na ósemkowy i szes- nastkowy z wykorzystaniem systemu dwójkowego: a) 52310, b) 45810, c) 39910, d) 87810, e) 100110, f) 111210, g) 205610. 2.2.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 sy- stemu 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 przenosi- my wynik dzielenia całkowitego tej liczby przez 2. 81 Rozdział 2. Algorytmy i ich zastosowanie Przykład 2.9. Obliczmy sumę liczb w systemie binarnym: 110112+1111102. Pogrubieniem wyróżnione są wartości przenoszone w lewo. 1 1 1 1 1 1 1 0 1 1 + 1 1 1 1 1 0 1 0 1 1 0 0 1 Otrzymany wynik to: 110112+1111102 = 10110012. Przykład 2.10. Wyznaczmy sumę czterech liczb zapisanych w systemie binarnym: 1111112+ 11102+101112+1101112. Ten przykład wydaje się trudniejszy, jednak jego rea- lizacja opiera się na dokładnie tych samych zasadach. 1 2 2 2 3 2 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 + 1 1 0 1 1 1 1 0 0 1 1 0 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 odej- mowanie. W tym przypadku problem pojawia się w sytuacji, gdy chcemy wykonać operację odejmowania, a liczba, od której odejmujemy, jest zbyt mała. Wówczas należy pobrać wartość 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.11. Obliczmy różnicę liczb zapisanych w systemie binarnym: 1101102–10102. Pogrubieniem wyróżnione są wartości uzyskane po pobraniu z lewej strony. 0 2 1 1 0 1 1 0 – 1 0 1 0 1 0 1 1 0 0 Wynikiem wykonanego działania jest: 1101102–10102 = 1011002. 82 2.2. Wyznaczanie wartości wielomianu Przykład 2.12. Wyznaczmy różnicę liczb binarnych: 1000002–1112. Ten przykład jest trud- niejszy, ale zasady identyczne. Dokładnie przeanalizuj wykonane działanie. 1 1 1 1 0 2 2 2 2 2 1 0 0 0 0 0 1 1 1 – 1 1 0 0 1 Uzyskaliśmy następujący wynik: 1000002–1112 = 110012. Mnożenie jest działaniem, które łączy w sobie operacje mnożenia i dodawa- nia. Najpierw wykonujemy mnożenie kolejnych cyfr jednej liczby przez drugą, a następnie uzyskane wyniki w odpowiedni sposób dodajemy. Przykład 2.13. Obliczmy iloczyn dwóch liczb w systemie binarnym: 1101112⋅10112. Porównaj wykonanie tego działania w systemie dwójkowym z mnożeniem w systemie dziesiętnym. × 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 + 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 1 Po wykonaniu obliczeń otrzymujemy: 1101112⋅10112 = 10010111012. Zadanie 2.12. Wykonaj następujące działania arytmetyczne w systemie binarnym: a) b) c) d) e) f) 2 2 2 ⋅ 2 + ⋅ 1101 111 10110 , 2 2 2 ⋅ − + 111000 11 101100 110 2 2 − + 10 11011 101 1100 2 2 − − 10011 101110 111 , 2 2 − 110 11001 110111 2 2 11111111 2 + 1+ . 11 , 2 ⋅ 2 , 2 , 2 8 Rozdział 2. Algorytmy i ich zastosowanie Zadanie 2.13. Podaj specyfikację zadania i skonstruuj algorytm w postaci programu wyko- nujący dodawanie dwóch wprowadzonych z klawiatury nieujemnych liczb całkowitych zapisanych w systemie binarnym. Przeanalizowaliśmy dokładnie realizację podstawowych działań arytmetycz- nych w systemie binarnym. Znając zasady wykonywania tych operacji, można przenieść je na płaszczyznę innych pozycyjnych systemów liczbowych. Na- leży jednak pamiętać, aby w tych systemach stosować właściwą im podstawę. Na przykład w oktalnym — 8, w heksadecymalnym — 16. Przykład 2.14. Wyznaczmy wartość wyrażenia: 3234⋅324–2134. 3 2 3 3 2 × 1 3 1 2 + 2 3 0 1 3 0 3 2 2 1 6 3 0 3 2 2 2 1 3 3 0 1 0 3 – Uzyskaliśmy następujący wynik: 3234⋅324–2134 = 301034. Zadanie 2.14. Wykonaj następujące działania arytmetyczne w podanych systemach liczbowych: 3 − a) b) c) d) ⋅ 1100 112 222 , 3 3 ⋅ + 302 31 4430 , 5 5 − + ⋅ 12 707 1066 45 , 8 8 8 FF C AB ⋅ − + . 1 10 16 16 16 5 8 16 Zadanie 2.15. Podaj, w jakich systemach pozycyjnych zostały wykonane następujące działania: a) 1001+10–1010 = 1, b) 244∙2–14 = 474, 8 2.2.4. 2.2. Wyznaczanie wartości wielomianu 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? Zadanie 2.16. Podaj specyfikację zadania i skonstruuj algorytm w postaci programu wyko- nujący dodawanie dwóch wprowadzonych z klawiatury nieujemnych liczb całkowitych zapisanych w systemie liczbowym o podstawie z zakresu [2; 9], również wprowadzonej z klawiatury. Wynik niech będzie wypisany w tym sa- mym systemie. Wyznaczanie wartości wielomianu   za pomocą schematu Hornera Schemat Hornera jest najszybszym sposobem obliczania wartości wielomia- nu. Przeanalizujmy działanie tej metody, przekształcając ogólny wzór na war- tość wielomianu stopnia n. Dany mamy wielomian stopnia n, gdzie n ≥ 0: . n (2.4) W omawianym algorytmie należy stosować grupowanie wyrazów tak długo, aż pozostanie jednomian. a x 1 + +  n − 2 + a x a n ( ) w x n ( ) w x n a x 0 a x 1 = =  = + + + + = − 1 − 1 n n n n 2 n − − 1 + n − 1 a x 1 a x 1 +  +  a x 0 ( a x 0 ( ( a x 0 =  ( ( ) ( ( a x a x a x  0 ) + + + − n 3 1 2 = = = a x a + = n n ) x a + + n ) x a + n − 1 a n − 1 a n + − 2 +  + a n − ) 2 x a + n ) − 1 x a + n = (2.5) ) − 1 ) − 1 x a + n x a + . n (2.6) Schemat Hornera ma więc następującą postać: a ) ( ( a x a x a x 0 ( ) w x n  ) + = + + + ( (  2 1 n ) 2 − x a + n Porównując wzory 2.4 i 2.6 na obliczanie wartości wielomianu, łatwo zauwa- żyć, że w schemacie Hornera wykonywana jest mniejsza liczba mnożeń. 8 Rozdział 2. Algorytmy i ich zastosowanie Przykład 2.15. Obliczmy wartość wielomianu w(x) = 2x3+4x2–3x+7 dla x = 3, wykorzystując schemat Hornera. Współczynnikami wielomianu są tutaj a0 = 2, a1 = 4, a2 = –3, a3 = 7, a stopień wielomianu n wynosi 3. ( ) w x = = 3 x 2 ( ( 2 2 x + 4 ) x + 4 x − + = 3 ) x x − 3 7 7 + Stąd dla x = 3 mamy: w ( ) 3 3 2 = ⋅ − ⋅ + = + ⋅ 2 3 3 3 7 4 3 ) ( ) ( = ⋅ + ⋅ − ⋅ + = 2 3 4 3 3 3 7 ( ) ⋅ − ⋅ + = = 10 3 3 3 7 ⋅ + = = 27 3 7 = 88 Porównajmy liczbę działań wykonywanych przy obliczaniu wartości wielo- mianu po wybraniu każdego ze wzorów: ) x 3 x x ⋅ + − ⋅ + . 7 ( ) w x ⋅ + ⋅ 4 x x x ⋅ = ⋅ 2 ( W powyższym przykładzie wykonano sześć operacji mnożenia oraz trzy ope- racje dodawania. W przypadku schematu Hornera wzór można przedstawić następująco: ( ) w x = ( ( 2 x ⋅ + 4 ) ) ) ( x x ⋅ + . ⋅ + − 7 3 Liczba wykonanych działań jest tutaj znacznie mniejsza: trzy mnożenia i trzy dodawania. Zadanie 2.17. Opierając się na powyższej analizie, wyznacz ogólną liczbę operacji mnoże- nia 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 x a + x a + = + + a  , n ( (  ( ) w x n ( ) ( a x a x a x 0 należy wykonać następujące operacje: ) + + 2 1 ) n − 2 ) n − 1 86 2.2. Wyznaczanie wartości wielomianu 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 zdefiniować wzór iteracyjny tego algorytmu: w a = 0  = w wx a  i + dla i = 1,2,  , n (2.7) (2.8) Na podstawie otrzymanego wzoru 2.8 konstruujemy algorytm iteracyjny w postaci listy kroków, schematu blokowego (patrz rysunek 2.3) oraz progra- mów w językach C++ i Pascal. S p e c y f i k a c j a : Dane: Wynik: Liczba całkowita: n ≥ 0 (stopień wielomianu). n+1-elementowa tablica liczb rzeczywistych: A[0...n] (współ- czynniki wielomianu). Liczba rzeczywista: x (wartość argumentu). Wartość rzeczywista wielomianu stopnia n dla wartości argu- mentu x. L i s t a k r o k ó w : Krok 0. Wczytaj wartości danych n, A[0...n], x. Krok 1. Krok 2. Krok 3. Krok 4. Wypisz wartość wielomianu: w. Zakończ algorytm. Przypisz w = A[0]. Dla kolejnych wartości i: 1, 2, …, n, wykonuj krok 3. Przypisz w = wx+A[i]. 8 Rozdział 2. Algorytmy i ich zastosowanie Rysunek 2.3.   Schemat blokowy algorytmu iteracyjnego wyznaczającego wartość wielomianu schematem Hornera START wczytaj: n, A[0...n], x w=A[0] i=1 NIE i =n TAK wypisz: w w=wx+A[i] STOP i=i+1 Funkcja w języku C++ (prog2_7.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_7.pas): function oblicz (A: tablica; n: integer; x: real): real; var w: real; i: integer; begin w:=A[0]; for i:=1 to n do w:=w*x+A[i]; oblicz:=w end; Przedstawiony algorytm można wykonać również rekurencyjnie. Nie jest trudne zauważenie zależności rekurencyjnej, na podstawie której obliczana jest wartość wielomianu stopnia n. ( ) w x = n ( ) x x a a x a n x a + a x 0 a x 1  w n + + + + n − 1 ) ( a x − 0 1   + + a − n n 2 = = n + n − 1 − 1 n n a x 1 w n − 1 + ( ) x − 1 n (2.9) 88 2.2. Wyznaczanie wartości wielomianu Na podstawie wzoru 2.9 tworzymy definicję rekurencyjną, która wygląda następująco: ( ) w x n (2.10) dla n dla n = 0 0  =   a 0 w n ( ) x x a n ⋅ + − 1 2.2.5. Zastosowanie schematu Hornera nie ogranicza się do wyznaczania wartości wielomianu stopnia n. Algorytm ten wykorzystywany jest rów- nież do:    konwersji liczb z dowolnego pozycyjnego systemu liczbowego na system dziesiętny; szybkiego obliczania wartości potęgi; jednoczesnego obliczania wartości wielomianu i jego pochodnej. Zadanie 2.18. Napisz program obliczający rekurencyjnie wartość wielomianu stopnia n z wykorzystaniem schematu Hornera zgodny z podaną powyżej specyfikacją algorytmu iteracyjnego. 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 systemach liczbowych na system dziesiętny. Przypomnijmy, w jaki sposób do- konujemy takiej zamiany w systemie binarnym, co zostało omówione w punk- cie 2.2.2, „Konwersje pozycyjnych systemów liczbowych”. Zamieńmy liczbę 10111012 na wartość w systemie decymalnym: + ⋅ 1 2 + ⋅ + ⋅ 1 2 + ⋅ 0 2 = ⋅ 1 2 + ⋅ 1 2 + ⋅ 1 2 3 1 0 2 1011101 2 = . 93 10 5 6 4 2 0 Łatwo zauważyć, że zapis liczby podczas obliczeń przypomina wielomian. Cyfry zamienianej liczby można więc potraktować jak współczynniki wie- lomianu, a podstawę systemu jak wartość argumentu x. W tym przypadku mamy następującą sytuację: n = 6, a0 = 1, a1 = 0, 89 Rozdział 2. Algorytmy i ich zastosowanie a2 = 1, a3 = 1, a4 = 1, a5 = 0, a6 = 1, x = 2. Taka interpretacja konwersji liczb na system dziesiętny umożliwia zastosowa- nie do jej realizacji schematu Hornera. Skonstruujmy więc algorytm wykonu- jący zamianę liczb z systemu dwójkowego na dziesiętny. S p e c y f i k a c j a : Dane: Wynik: Liczba całkowita: n ≥ 0 (stopień wielomianu). n+1-elementowa tablica liczb rzeczywistych: A[0...n] (współ- czynniki wielomianu, czyli cyfry liczby zapisanej w systemie binarnym). Wartość wielomianu stopnia n dla argumentu 2 (liczba w sys- temie dziesiętnym). Funkcja w języku C++ (prog2_8.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_8.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; Zadanie 2.19. Podaj specyfikację zadania i skonstruuj rekurencyjny algorytm w postaci pro- gramu realizujący konwersję liczb zapisanych w systemie o podstawie zawartej w zakresie [2; 9] na system dziesiętny z zastosowaniem schematu Hornera. 90 2.2. Wyznaczanie wartości wielomianu Zadanie 2.20. Podaj specyfikację zadania i skonstruuj iteracyjny algorytm w postaci progra- mu realizujący konwersję liczb zapisanych w systemie szesnastkowym na sy- stem dziesiętny z zastosowaniem schematu Hornera. 2.2.6. Reprezentacja danych liczbowych   w komputerze Binarna reprezentacja liczb ujemnych Dane w komputerze zapisywane są w postaci liczb binarnych. Wynika to stąd, że najmniejsza jednostka pamięci, którą jest bit, służy do zapisu jednej cyfry systemu dwójkowego: 0 lub 1. Dotychczas poznaliśmy reprezentację binarną liczb całkowitych nieujemnych. Wartości ujemne zapisuje się, używając kodu uzupełniającego do dwóch, zwanego kodem U2. Ogólny zapis liczby w ko- dzie U2 można przedstawić za pomocą następującego wzoru: y  =   x 2 n + dla x dla x x ≥ 0 0 (2.11) 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 bitó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 rozumieć na dwa równoważne sposoby: reprezentuje on znak liczby x w kodzie U2, a zarazem jest pierw- szym (najbardziej znaczącym) bitem nieujemnej liczby y w zwykłym ukła- dzie dwójkowym. Wartość kodowanej liczby x zawiera się więc w zakresie [–2n–1; 2n–1). Przykład 2.16. Załóżmy, że dysponujemy 1 bajtem (czyli 8 bitami) przeznaczonym do za- pisania liczby. Stąd n = 8, a wartość kodowanej liczby x musi zawierać się 91 Rozdział 2. Algorytmy i ich zastosowanie w zakresie [–2n–1; 2n–1) = [–27; 27) = [–12810; 12810). Korzystając z wzoru, wyznaczmy wartość liczby x = –56 w kodzie U2. Musimy wykonać następują- ce obliczenia: 8 2 256 56 y = − = ( + − 56 ) = 200 10 . Następnie konwertujemy uzyskaną wartość z systemu dziesiętnego na dwójkowy: 200 10 = 11001000 . 2 Uzyskana liczba, y = 110010002, to zakodowana wartość liczby x = –5610. Zadanie 2.21. 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 zapisywa- nej liczby. Powoduje to, że taki zapis liczby jest dokładny tylko wtedy, gdy dana liczba nie wykracza poza zakres miejsca, jakie zostało przeznaczone do jej zapisu. Załóżmy, że mamy do dyspozycji 2 bajty (czyli 16 bitów) do zapisania liczby w reprezentacji stałopozycyjnej. Wówczas podział na część całkowitą i ułam- kową może przedstawiać się jak na rysunku 2.4. znak liczby (1 bit) część całkowita (8 bitów) część ułamkowa (7 bitów) Rysunek 2.4.    Przykładowy podział na część całkowitą i ułamkową w stałopozycyjnej reprezentacji liczb W reprezentacji stałopozycyjnej liczba zapisywana jest w kodzie uzupełniają- cym do dwóch. 92 2.2. Wyznaczanie wartości wielomianu Potrafimy już wykonywać konwersję liczby całkowitej pomiędzy systemami bi- narnym i decymalnym. Jednak aby przedstawić liczbę rzeczywistą, wykorzystu- jąc reprezentację stałopozycyjną, trzeba uwzględnić również część ułamkową. Konwertując liczby z systemu binarnego na decymalny, mnożymy kolej- ne cyfry tej liczby przez potęgi dwójki. W części ułamkowej mnożnikiem są ujemne potęgi liczby 2. Przykład 2.17. Zapiszmy liczbę rzeczywistą 101111,011012 w systemie dziesiętnym. Zaczyna- my od dopasowania potęg liczby 2 do kolejnych cyfr podanej wartości: 1 25 0 24 1 23 1 22 1 21 1 20 , 1 0 1 2–1 2–2 2–3 2–4 2–5 1 0 Następnie obliczamy wartość konwertowanej liczby w systemie dziesiętnym: 13 32 101111,01101 2 1 + ⋅ 1 2 + ⋅ 0 2 + ⋅ 0 2 + ⋅ 1 2 3 = ⋅ 1 2 5 + ⋅ 1 2 0 + ⋅ 1 2 2 + ⋅ 0 2 + ⋅ 1 2 = 47 − 5 4 − 1 + ⋅ 1 2 − 2 + ⋅ 1 2 − 3 − 4 . 10 Zamiana liczby ułamkowej z systemu dziesiętnego na dwójkowy wykony- wana 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.18. 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 0,375∙2 = 0,75 = 1,5 0,75∙2 0,5∙2 = 1,0 Rozwiązaniem jest ułamek skończony. Widać to po wartości ostatniego wyni- ku 1,0, w którym część ułamkowa wynosi zero. Uzyskaliśmy więc następujące rozwiązanie: 0,182510 = 0,00112. 9 Rozdział 2. Algorytmy i ich zastosowanie Poniżej pokazany został czytelniejszy zapis konwersji liczb ułamkowych z sy- stemu decymalnego na binarny: 0 0 0 1 1 1825 375 75 5 0 Przykład 2.19. Przekonwertujmy liczbę 0,210 na system binarny. Rozwiązaniem będzie uła- mek 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.22. 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.23. Przekonwertuj podane liczby rzeczywiste na system binarny: a) 852,687510, b) 620,0937510, 9 2.2. Wyznaczanie wartości wielomianu c) 612,0312510, d) 1536,992187510, e) 2707,773437510. Zadanie 2.24. Wykonaj następujące operacje arytmetyczne w systemie binarnym: a) 1110,0112∙10001,001112, b) 1111,0012+100000,110112, c) 10011,010112–100,10112. Zmiennopozycyjna reprezentacja liczb Zmiennopozycyjna reprezentacja liczb charakteryzuje się zmiennym położe- niem przecinka, które zależy od zapisywanej liczby. Ogólny wzór na wartości w tej reprezentacji przedstawia się następująco: liczba = m⋅2c, (2.12) 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 kodowa- na liczba jest w postaci znormalizowanej. Aby wyznaczyć wartość liczby zapisanej w reprezentacji zmiennopozycyjnej, trzeba znać wartość mantysy i cechy. Na rysunku 2.5 przedstawiono graficz- nie zapis zmiennopozycyjny, z uwzględnieniem podziału na cechę i mantysę. Cecha i mantysa zapisywane są jako liczby stałopozycyjne w kodzie U2. cecha mantysa znak cechy (1 bit) znak mantysy (1 bit) Rysunek 2.5.   Przykładowy podział na cechę i mantysę w zmiennopozycyjnej reprezentacji liczb 9 Rozdział 2. Algorytmy i ich zastosowanie Przykład 2.20. Załóżmy, że daną mamy liczbę 0000111011100001 zapisaną w reprezentacji zmiennopozycyjnej. Podana liczba zajmuje 2 bajty (czyli 16 bitów), z czego 7 bitów to cecha, a pozostał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: = 7 10 1 + ⋅ 1 2 = ⋅ 1 2 + ⋅ 1 2 0 , c = 111 2 2 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.12, obliczamy wartość zakodowa- nej liczby: liczba m = ⋅ 2 c = 225 256 7 ⋅ 2 = ⋅ 0,87890625 2 7 = 112,5 10 . W reprezentacji zmiennopozycyjnej nie każdą liczbę rzeczywistą można zapi- sać dokładnie. 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.25. Wyznacz wartości dziesiętne liczb podanych w reprezentacji zmiennopozycyj- nej (cecha i mantysa oddzielone są odstępem): a) 000000010 0110011, b) 0001010 c) 0000011 010000101, 010100001. MATURA — egzamin styczeń 2006 r. Arkusz I, zadanie 3. MATURA — Sylabus od 2009 r. Arkusz I poziom podstawowy, zadanie 2. KRAJE MATURA — Sylabus od 2009 r. Arkusz II poziom podstawowy, zadanie 5. DODAWANIE LICZB TRÓJKOWYCH 96
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Informatyka Europejczyka. Informatyka. Podręcznik dla szkół ponadgimnazjalnych. Część 1
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ą: