podr.rar

Informatyka część 1
PODRĘCZNIK dla liceum ogólnokształcącego

Spis treści:
1. Algorytmy 7
1.1. Definicja algorytmu 7
1.2. Sposoby zapisu algorytmu 9
1.3. Specyfikacja problemu algorytmicznego 11
1.4. Opis stosowanych operatorów 13
1.5. Instrukcja warunkowa - algorytmy rozgałęzione 15
1.6. Instrukcja iteracji 18
1.7. Poprawność algorytmu 23
1.8. Złożoność obliczeniowa algorytmu 24
1.9. Realizacja algorytmów w arkuszu kalkulacyjnym 28
2. Wstęp do programowania w języku C++ 35
2.1. Reprezentacja danych w komputerze - podstawowe operacje
w systemie binarnym ..35
2.2. Proces wytwarzania programu 38
2.3. Podstawowe typy danych 41
2.4. Budowa programu , 42
2.5. Instrukcje sterujące 50
2.5.1. Instrukcja warunkowa if ... else .... 51
2.5.2. Instrukcja wyboru switch 56
2.5.3. Instrukcja pętli for 59
2.5.4. Instrukcja pętli while 61
2.5.5. Instrukcja pętli do ... while 62
2.5.6. Instrukcje break i continue sterujące wykonaniem pętli 64
3. Funkcje w C++ 69
3.1. Definiowanie i wywoływanie funkcji . 69
3.2. Zakres ważności zmiennych 71
3.3. Sposoby przekazywania parametrów funkcji 73
4. Implementacja klasycznych algorytmów iteracyjnych 89
4.1. Znajdowanie najmniejszego lub największego elementu w ciągu liczb , 89
4.2. Liczba pierwsza czy złożona - algorytm testujący 91
4.3. Wyznaczanie NWD i NWW dla dwóch liczb naturalnych
(algorytm Euklidesa) 94
4.4. Obliczanie pierwiastka kwadratowego z liczby dodatniej - metoda
Newtona-Raphsona 99
4.5. Obliczanie pola obszaru ograniczonego wykresem funkcji ..... 102
4.6. Znajdowanie przybliżonej wartości miejsca zerowego funkcji ciągłej
metodą połowienia przedziałów 106
4.7. Metody Monte Carlo ... 109
4.7.1. Obliczanie wartości liczby % metodą Monte Carlo 109
4.7.2. Modelowanie ruchów Browna 113
5. Tablice danych - przykłady i wykorzystanie w algorytmach 117
5.1. Charakterystyka tablic 117
5.1.1. Tablice jednowymiarowe 118
5.1.2. Tablice wielowymiarowe . . 122
5.2. Klasyczne algorytmy działające na tablicach ..... 128
5.2.1. Przeszukiwanie liniowe tablicy jednowymiarowej 128
5.2.2. Przeszukiwanie liniowe tablicy jednowymiarowej z wartownikiem 130
5.2.3. Poszukiwanie elementu maksymalnego (minimalnego) w tablicy .. 132
5.2.4. Zapisywanie liczb w różnych systemach liczbowych 134
5.2.5. Sito Eratostenesa 140
5.3. Sortowanie tablicy .... 142
5.3.1. Sortowanie bąbelkowe 142
5.3.2. Sortowanie przez wstawianie 145
5.3.3. Sortowanie przez wybór 148
5.4. Praktyczne wykorzystanie tablicy dwuwymiarowej 150
5.5. Tablice tekstowe 152
5.5.1. Modyfikacje dokonywane na tekście 155
5.5.2. Szyfr Cezara .156
5.6. Rozwiązywanie układów równań metodą eliminacji Gaussa 159
6. Rekurencja 167
6.1. Funkcje rekurencyjne w informatyce 167
6.1.1. Silnia liczby naturalnej 167
6.1.2. Potęga o wykładniku naturalnym liczby rzeczywistej 170
6.1.3. Obliczanie wartości wyrazów ciągów zdefiniowanych rekurencyjnie 171
6.1.4. Ciąg Fibonacciego 172
6.1.5. Schemat Homera obliczania wartości wielomianu 174
6.1.6. Wieże Hanoi 175
6.1.7. Zamiana liczby na postać dwójkową - rozwiązanie rekurencyjne 178
6.1.8. Rekurencyjne odwracanie wprowadzonego ciągu znaków . 179
6.2. Metoda „dziel i zwyciężaj" 180
6.2.1. Przeszukiwanie binarne ... 181
6.2.2. Sortowanie tablicy przez scalanie 182
6.2.3. Sortowanie szybkie 187
6.3. Problem skoczka szachowego i problem ośmiu hetmanów - algorytmy
z powrotami 188
7. Struktury - typ definiowany przez użytkownika 195
7.1. Definicja struktury ! 195
7.2. Tablice o elementach typu strukturalnego 200
7.3. Struktury jako argumenty funkcji 202
8. Typ wskaźnikowy - zastosowania 207
8.1. Deklaracja zmiennej wskaźnikowej i podstawowe operacje
na wskaźnikach 207
8.2. Przekazywanie argumentów funkcji przez wskaźnik 212
8.3. Zastosowanie wskaźników w tablicach 213
9. Zmienne i struktury dynamiczne 219
9.1. Tablica dynamiczna jednowymiarowa 219
9.2. Tablica dynamiczna dwuwymiarowa 222
9.3. Lista jednokierunkowa - tworzenie listy i wprowadzanie do niej
elementów 227
9.4. Lista jednokierunkowa - usuwanie listy z pamięci 234
9.5. Lista dwukierunkowa 236
10. Zapis do plików i odczyt z plików 243
10.1. Zapis do pliku 243
10.2. Odczyt danych z pliku 246
11. Wstęp do programowania obiektowego 255
11.1. Obiekt a klasa 255
11.2. Hermetyzacja - rola metod publicznych 257
11.3. Rola konstruktora i destruktora 260