IntroInfo.pdf

(601 KB) Pobierz
Wst ep do informatyki z przykładami
w j ezyku C
Jacek Cicho n, Przemysław Kobyla nski
WPPT, Politechnika Wrocławska
WRZESIE N 2010
Spis tresci
Spis tresci
1
1
Wprowadzenie do jezyka C
4
1.1
Pierwszy program . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2
Zmienne i wyrazenia arytmetyczne . . . . . . . . . . . . . . . . . . .
6
1.3
Konstrukcje warunkowe
. . . . . . . . . . . . . . . . . . . . . . . .
11
1.4
Parametry funkcji i wskazniki
. . . . . . . . . . . . . . . . . . . . .
15
1.5
Petle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
1.6
Tablice i ła ncuchy . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
1.7
Biblioteki
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
1.8
O stylu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.9
23
2
Algorytmy, algorytmy
26
Dodawanie i mnozenie duzych liczb
2.1
. . . . . . . . . . . . . . . . . .
26
2.2
Układ równa n liniowych
. . . . . . . . . . . . . . . . . . . . . . . .
29
2.3
Równanie kwadratowe
. . . . . . . . . . . . . . . . . . . . . . . . .
30
2.4
Liczby naturalne
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
2.5
Sortowanie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
2.6
Wyszukiwanie binarne
. . . . . . . . . . . . . . . . . . . . . . . . .
38
Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7
41
3
Bity, bajty, liczby
43
3.1
Układ dwójkowy
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
3.2
Układ szesnastkowy . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.3
Liczby ze znakiem
. . . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.4
Liczby rzeczywiste
. . . . . . . . . . . . . . . . . . . . . . . . . . .
50
3.5
Liczby zespolone
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6
58
4
Podstawowe metody
60
4.1
Rekursja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
4.2
Przeszukiwanie z nawrotami
. . . . . . . . . . . . . . . . . . . . . .
63
4.3
Dziel i rz adz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
4.4
Dynamiczne programowanie
. . . . . . . . . . . . . . . . . . . . . .
68
4.5
Stosy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
4.6
Automaty sko nczone
. . . . . . . . . . . . . . . . . . . . . . . . . .
69
4.7
Systemy przepisuj ace . . . . . . . . . . . . . . . . . . . . . . . . . .
69
Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.8
70
1
5
Granice obliczalnosci
72
5.1
Funkcje obliczalne
. . . . . . . . . . . . . . . . . . . . . . . . . . .
72
5.2
Zbiory rozstrzygalne
. . . . . . . . . . . . . . . . . . . . . . . . . .
74
5.3
Funkcja uniwersalna
. . . . . . . . . . . . . . . . . . . . . . . . . .
75
5.4
Problem zatrzymania
. . . . . . . . . . . . . . . . . . . . . . . . . .
76
5.5
Przegl ad problemów nierozstrzyganlych . . . . . . . . . . . . . . . .
76
Bibliografia
77
Indeks
78
Wstep
Ksi azka ta jest wstepem do informatyki rozumianej jako nauki o algorytmach. Ta-
kie potraktowanie informatyki jest pewnym zawezeniem dziedziny. Jednak według
autora ten fragment informatyki jest jej j adrem, najbardziej istotn a czesci a. Nauka
o algorytmach, zwana ALGORYTMIK A , odgrywa dla całej informatyki tak a role jak
logika dla dla matematyki (patrz [1]).
W ksi azce nie ma informacji o tym jak jest zbudowany rzeczywisty komputer.
Nie s a omawiane systemy operacyjne. Nie jest omawiany system plików. Zakła-
damy, ze czytelnik tej ksi azki jest srednio zaawansowanym uzytkownikiem kompu-
terów. Mimo, ze do zapisu algorytmów stosowany jest jezyk C, nie jest omawiany
zaden kompilator.
3
Rozdział 1
Wprowadzenie do jezyka C
#include <stdio.h>
int main(){
printf(”Hello world.nn”);
return(0);
}
W pierwszej czesci tej ksi azki zajmiemy sie podstawowymi technikami programo-
wania - zmiennymi i stałymi, arytmetyk a, instrukcjami steruj acymi, głównymi typami
danych oraz podstawowymi metodami wejscia i wyjscia. Programowania, tak samo
jak pływania, nie mozna nauczyc sie teoretycznie. Do jego opanowania potrzebna jest
spora ilosc praktyki i cierpliwosci.Nie spodziewaj sie, ze po samym przeczytaniu tej
ksi azki bedziesz umiał programowac. Musisz robic zadania i pisac samodzielnie jak
najwiecej programów. Wykonuj samodzielne eksperymenty i czytaj mozliwie duzo
na temat programowania.
W ksi azce tej bedziemy posługiwali sie jezykiem programowania C. Został on
stworzony w roku 1972 przez Dennisa Ritchie z Laboratorium Bella. W roku 1978 B.
K. Kernighan i D. M. Ritchie opublikowali ksi azke ”The C Programming Language”
(patrz [2]), która spowodowała spor a rewolucje w swiecie informatycznym.
Jezyk C jest baz a bardziej rozbudowanych jezyków takich jak C++, PHP oraz
Java. Jest bardzo zwiezłym jezykiem i pozwala na wykonywanie wielu niskopo-
ziomowych (bliskich sprzetu) operacji. Jego niew atpliw a zalet a jest to, ze pozwala
programiscie praktycznie na wszystko. Po pewnym czasie przekonasz sie, ze to, jak
równiez jego zwiezłosc jest równoczesnie jego wad a.
Ksi azka ta nie jest podrecznikiem programowania w jezyku C. Twoj a podstawow a
lektur a uzupełniaj ac a powinna byc klasyczna ksi azka B. K. Kernighana i D. M. Rit-
chie pt. „Jezyk ANSI C” (patrz [3]). W naszej ksi azce posługiwac sie bedziemy tylko
podstawowymi konstrukcjami tego jezyka i równie dobrze do zapisu rozwazanych al-
gorytmów moglibysmy posługiwac sie innym, tak zwanym imperatywnym jezykiem
programowania.
Mógłby byc nim na przykład Pascal, Basic, Ada, Fortran czy tez
Forth.
Program w jezyku C jest plikiem tekstowym, który przetłumaczony musi byc na
jezyk zrozumiały przez komputer. Do tego przekształcania słuz a kompilatory.
4
920642072.001.png 920642072.002.png 920642072.003.png
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin