...

informatyka-europejczyka.-informatyka.-podrecznik-dla-szkol-ponadgimnazjalnych.-czesc-i pełna wersja, ...

[ Pobierz całość w formacie PDF ]
Część 1.
Informatyka Europejczyka. Informatyka
2.2. Wyznaczanie wartości wielomianu,
pozycyjne systemy liczbowe
i reprezentacja danych liczbowych w komputerze
72
2.2.1. Systemy liczbowe
72
2.2.2. Konwersje pozycyjnych systemów liczbowych
75
2.2.3. Operacje arytmetyczne wykonywane
w różnych systemach liczbowych
81
2.2.4. Wyznaczanie wartości wielomianu
za pomocą schematu Hornera
85
2.2.5. Zamiana liczb z dowolnego pozycyjnego
systemu liczbowego na system dziesiętny
z zastosowaniem schematu Hornera
89
2.2.6. Reprezentacja danych liczbowych w komputerze
91
2.3. Generowanie liczb pierwszych i badanie,
czy liczba jest pierwsza
97
2.3.1. Badanie, czy liczba jest pierwsza
97
2.3.2. Sito Eratostenesa
100
2.4. Przeszukiwanie ciągu liczbowego — metody liniowe
103
2.4.1. Liniowe przeszukiwanie ciągu liczbowego
103
2.4.2. Liniowe przeszukiwanie
ciągu liczbowego z wartownikiem
108
2.5. Znajdowanie najmniejszego
lub największego elementu w ciągu liczbowym
110
2.6. Znajdowanie lidera w zbiorze
113
2.7. Sprawdzanie monotoniczności ciągu liczbowego
117
2.8. Sortowanie ciągu liczbowego
119
2.8.1. Metody sortowania przez porównania
121
2.8.2. Sortowanie w czasie liniowym
130
2.9. Zastosowanie metody „dziel i zwyciężaj”
136
2.9.1. Jednoczesne znajdowanie najmniejszego
i największego elementu
136
2.9.2. Sortowanie przez scalanie
140
2.9.3. Sortowanie szybkie
146
2.10. Metody numeryczne i obliczenia przybliżone
150
2.10.1. Obliczanie wartości pierwiastka kwadratowego
z liczby nieujemnej — algorytm Newtona-Raphsona
150
2.10.2. Obliczanie pola obszaru
ograniczonego wykresem funkcji
154
2.10.3. Znajdowanie przybliżonej wartości miejsca zerowego
funkcji — metoda połowienia przedziałów
162
2.11. Wyznaczanie wartości wyrażenia zapisanego
w odwrotnej notacji polskiej ONP
166
Spis treści
2.12. Zastosowanie programowania zachłannego
169
2.12.1. Problem plecakowy
169
2.12.2. Algorytm wydawania reszty
179
2.13. Wybrane algorytmy kryptograiczne
182
2.13.1. Szyfrowanie symetryczne
182
2.13.2. Szyfrowanie asymetryczne
194
 Rozdział
 
3.  Programowanie w języku C++
 
197
3.1. Języki programowania — pojęcia, klasyikacja, przykłady 198
3.2. Wprowadzenie do programowania
200
3.2.1. Struktura programu
201
3.2.2. Operacje wejścia-wyjścia
204
3.2.3. Zmienne, stałe, wskaźniki i referencje
209
3.2.4. Wyrażenia arytmetyczne, relacje i operatory logiczne
213
3.2.5. Liczby losowe
221
3.2.6. Komentarze
222
3.3. Podstawowe konstrukcje algorytmiczne
223
3.3.1. Instrukcja pusta
223
3.3.2. Instrukcja przypisania
223
3.3.3. Instrukcja złożona
224
3.3.4. Instrukcje warunkowe
224
3.3.5. Instrukcja wyboru
227
3.3.6. Instrukcje iteracyjne
230
3.3.7. Instrukcje sterujące
235
3.4. Proste typy danych
236
3.5. Strukturalizacja programu
238
3.5.1. Struktura funkcji
238
3.5.2. Zmienne lokalne i globalne
240
3.5.3. Przekazywanie parametrów w funkcjach
241
3.5.4. Przeładowanie funkcji
248
3.6. Strukturalne typy danych
254
3.6.1. Tablice
254
3.6.2. Łańcuchy
262
3.6.3. Struktury
268
3.7. Dynamiczne struktury danych
272
3.7.1. Stos
273
3.7.2. Kolejka
275
3.7.3. Lista
276
3.8. Plikowe operacje wejścia-wyjścia
279
3.8 277
Rozdział 2.
Algorytmy i ich zastosowanie
FunkcjawjęzykuPascal(
prog2_5.pas
):
function
nww (a, b: integer): integer;
begin
nww:=a*b
div
nwd(a,b)
end
;
Zadanie 2.1.
Podaj specyikację 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 specyikację 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
Systemy liczbowe
2.2.1.
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ą
systemubinarnego
, określającą liczbę cyfr, jest dwa. System ten ko-
rzysta więc z dwóch cyfr, którymi są 0 i 1.
Systemoktalny
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:
A
16
= 10
10
,
B
16
= 11
10
,
C
16
= 12
10
,
D
16
= 13
10
,
E
16
= 14
10
,
F
16
= 15
10
.
Gdybyśmy nie korzystali z liter, zapis liczby 112
16
mógłby oznaczać 112
16
lub
B
2
16
lub 1
C
16
.
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.
[ Pobierz całość w formacie PDF ]