Informatyka_Europejczyka_Informatyka_Podrecznik_dla_szkol_ponadgimnazjalnych_Czesc_1_ponadg.pdf

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.

Pojêcie algorytmu

Sposoby przedstawiania algorytmów

Metody programowania: liniowe, warunkowe, iteracja, rekurencja,

„dziel i zwyciê¿aj”, zach³anna

Analiza i realizacja algorytmów

Podstawy kryptografii i wybrane algorytmy szyfruj¹ce

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

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 12

1.3.1. Lista kroków algorytmu 13

1.3.2. Schemat blokowy algorytmu 14

1.3.3. Drzewo algorytmu 15

1.3.4. Program w języku programowania wysokiego poziomu 16

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

i najmniejszej wspólnej wielokrotności

dwóch liczb naturalnych

2.1.1. Algorytm Euklidesa

2.1.2. Obliczanie najmniejszej wspólnej wielokrotności

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

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

za pomocą schematu Hornera

2.2.5. Zamiana liczb z dowolnego pozycyjnego

systemu liczbowego na system dziesiętny

z zastosowaniem schematu Hornera

2.2.6. Reprezentacja danych liczbowych w komputerze

2.3. Generowanie liczb pierwszych i badanie,

czy liczba jest pierwsza

2.3.1. Badanie, czy liczba jest pierwsza

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

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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: