Programowanie Proceduralne - Marek Grochowski PDF

Programowanie Proceduralne Marek Grochowski Wydział Fizyki, Astronomii i Informatyki Stosowanej UMK https://www.is.umk.pl/~grochu/pp https://github.com/IS-UMK/pp_w...

Programowanie Proceduralne Marek Grochowski Wydział Fizyki, Astronomii i Informatyki Stosowanej UMK https://www.is.umk.pl/~grochu/pp https://github.com/IS-UMK/pp_wyklad [email protected] Ostatnia aktualizacja: 4 listopada 2024  O programowaniu komputerów Programowanie to wszechstronny proces prowadzący od problemu obliczeniowego do jego rozwiązania w postaci programu. Celem programowania jest odnalezienie sekwencji instrukcji, które w sposób automatyczny wykonują pewne zadanie. Programowanie proceduralne to paradygmat programowania zalecający dzielenie kodu na procedury, czyli fragmenty wykonujące ściśle określone operacje. pl.wikipedia.org Programowanie Proceduralne 2  Przegląd zagadnień Podstawy programowania w języku C Case study - przykłady programów, demonstracje Problem → Algorytm → Program → Rozwiązanie Paradygmat programowania proceduralnego, algorytmy wydzielone w postaci uniwersalnych funkcji Reprezentacja danych w komputerze: typy proste, złożone, struktury dynamiczne,... Elementy inżynierii oprogramowania: model, projekt, analiza, implementacja, wykrywanie błędów, testowanie Laboratorium: język C, rekomendowane środowisko Visual Studio C++ Zaliczenie wykładu: pozytywna ocena z laboratorium + TEST zaliczeniowy (AiR egzamin na ocenę) Programowanie Proceduralne 3  Prolog O programowaniu komputerów Jak uczyć się programowania? pytaj czytaj podglądaj programuj, programuj, programuj,... Programowanie Proceduralne 4  Literatura Brian W. Kernighan, Dennis M. Ritchie, Język ANSI C, WNT, Warszawa, 2000. David Griffiths, Dawn Griffiths, Rusz głową! C., Helion, Gliwice, 2013. D. Harel, Rzecz o istocie informatyki. Algorytmika., WNT, Warszawa, 1992. Maciej M. Sysło, Algorytmy, WSiP, Warszawa, 2002. Programowanie Proceduralne 5  Pierwszy komputer i programistka Charles Babbage (1791–1871) 1822 Projekt maszyny różnicowej. 1837 (Parowa) maszyna analityczna - sterowanie sekwencyjne, pętle, odgałęzienia, projekt niedokończony Augusta Ada Lovelace (1815-1852) 1842 Note G, algorytm wyznaczania liczb Bernoullego. Pierwszy program komputerowy. 1979 Język ADA. Programowanie Proceduralne 6  Stempunk 1849 Difference Engine No. 2, dokładność 31 cyfr, wydruk na wyjściu 2002 Realizacja projektu rekonstrukcji maszyny różnicowej,  Computer History Museum. 2011 Początek (10 letniego) projektu rekonstrukcji maszyny analitycznej,  Plan 28. http: // www. computerhistory. org/ Programowanie Proceduralne 7  Generacje komputerów 0 mechaniczne, przekaźnikowe (do 1945) Z3 (Berlin, 1941), Harvard Mark 1 (USA, 1944), GAM-1 (Warszawa, 1950), PARK (AGH, 1957) 1 lampy elektronowe (1945-59) ABC Atanasoff-Berry Computer (USA, 1942), COLOSSUS (UK, 1943), ENIAC (USA, 1945), XYZ (Warszawa, 1957/1958) 2 tranzystory i pamięci ferrytowe (1959-64) PDP-1 (USA, 1960), ZAM-41(Polska, 1961), Odra 1204 (Polska, 1967) 3 układy scalone o małej skali integracji SSI (1965-70) IBM 360 (1965), Odra 1305 (Polska, 1973) 4 układy o wysokiej skali integracji LSI i VLSI, mikroprocesory mikroprocesor Intel 4004 z częstotliwością taktowania 0,1 MHz (1971), IBM 5150 PC (1981) 5 Komputery przyszłości: kwantowe, optyczne, biologiczne ? Programowanie Proceduralne 8  Komputery generacji 0 Mechaniczne i przekaźnikowe Konrad Zuse 1936 Mechaniczny Z1, liczby zmiennopozycyjne. 1941  Przekaźnikowy Z3, pierwszy działający programowalny komputer 5.3Hz, 64 słowa 22 bitowe (176 B). Inne komputery 0 generacji yk 1939-44 Harvard Mark 1 Howarda Aikena (IBM ASCC) Jęz alkül 1950 GAM-1, Państwowy Instytut Matematyczny w Warszawie nk 1957 PARK (Programowany Automat Rachunków Krakowianowych), AGH Pla 943 1 Programowanie Proceduralne 9  Komputery 1 generacji (1945-59) Lampy próżniowe Zastosowanie do obliczeń numerycznych (łamanie szyfrów, balistyka). Wejście: karty dziurkowane, taśmy papierowe Wyjście: wydruk, dalekopis, lampy Pamięć: dane przechowywane na dyskach magnetycznych, rtęciowe linie opóźniające Program: głównie język maszynowy 1949 (prawie) pierwszy assembler (EDSAC) se Zu il” 1952 Grace Hopper, pierwszy kompilator A-0 (UNIVAC I) K. ng ste gu 1954 Język Fortran rti lanfe „P 45 19 Programowanie Proceduralne 10  Karta perforowana 80 kolumn, 10 wierszy numerycznych + 2 wiersze strefowe (IBM, 1928) Programowanie Proceduralne 11  ENIAC (1946) Elektroniczne urządzenie numeryczne całkujące i liczące 18 000 lamp, 30 ton, 170 m2 , moc 160kW, 5000 operacji dodawania / sec. system dziesiętny, ręczne programowanie przez ustawianie 6K przełączników i wtykanie kabli Programowanie Proceduralne 12  Współczesna koncepcja komputera John von Neumann, 1945 Pamięć używana zarówno do przechowywania danych jak i samego programu, każda komórka pamięci ma unikatowy identyfikator (adres). se Zu r a d ł Ko n wa t ulo h po s oic sw w ch to t e nta !!! pa r. 36 19 w 1949 EDVAC, Electronic Discrete Variable Computer, współpracuje już z dyskami magnetycznymi. Programowanie Proceduralne 13  Komputery 2 generacji (1959-64) Tranzystory i pamięć ferrytowa 1960 PDP-1, pierwszy dostępny w sprzedaży minikomputer z monitorem i klawiaturą. Pierwsza gra wideo „Spacewar!” (Steve Russel), pierwszy edytor tekstu, interaktywny debugger, komputerowa muzyka. Programowanie Proceduralne 14  Komputery 3 generacji (1965-70) Układy scalone o małej skali integracji SSI 1970 Minikomputer K-202 (potencjalnie) wydajniejszy od IBM 5150 PC (1981 r.) Opracowany i skonstruowany przez inż. Jacka Karpińskiego. 16 bitów adresowanie stronicowe do 8MB (konkurencja max. 64kB) modularność wielodostępowość 1 mln. operacji/s. Programowanie Proceduralne 15  Komputery 4 generacji (od 1971) Układy o wysokiej skali integracji LSI i VLSI 1981 IBM 5150 PC procesor Intel 8088 (4.77 MHz) 64 kB pamięci ROM do 640 kB pamięci RAM brak dysku twardego (taśmy na kasetach, późniejsze modele dyskietki 5,25 cala) karta CGA (kolor) lub MGA (monochromatyczna), system operacyjny MS-DOS, dźwięk z PC speakera Programowanie Proceduralne 16  Rozwój języków programowania kod maszynowy, assembler lata 50-te, języki wysokiego poziomu Fortran (1955), Lisp (1955), COBOL (1959) lata 60-te, rozwój języków specjalistycznych Simula I (1960, el. obiektowości), Lisp, COBOL Pierwsze próby stworzenia języków ogólnych Algol (58/60), PL/1 (1964). lata 70-te, początek pojedynku: Pascal vs. C Zalążki obiektowości: Smalltalk (1972) lata 80-te, Dominują: C, Pascal, Basic Powstają: C++ (1980), Matlab (1984) lata 90-te, era internetu, programowanie obiektowe Java (1996), Python (1991), PHP (1995), JS (1995),.NET (C#, 2001) Żródło:  History and Evolution of Programming Languages Programowanie Proceduralne 17 Żródło: David A. Watt, ”Programming Language Design Concepts” Programowanie Proceduralne 18  Języki programowania kod maszynowy, języki symboliczne wysokiego i niskiego poziomu paradygmaty programowania: proceduralne, strukturalne, obiektowe, funkcyjne, logiczne, uniwersalne,...  Lista 2500 języków komputerowych, Bill Kinnersley Pieter Bruegel (starszy), 1563  Lista języków na Wikipedii Programowanie Proceduralne 19  Kod maszynowy Kod maszynowy ciąg instrukcji w postaci binarnej wykonywanych bezpośrednio przez procesor. rozkazy procesora i dane w postaci słów bitowych pobierane są z pamięci do rejestrów procesora nie jest przenośny, każdy procesor ma swój specyficzny zestaw instrukcji Programowanie Proceduralne 20  Assembler push rbp mov rbp , r s p Język assemblera mov = DWORD PTR [ rbp 0x4 ] , 0 x0 jmp 11 zastępuje rozkazy maszynowe add tzw. mnemonikami, zrozumiałymi przez = DWORD PTR [ rbp 0x4 ] , 0 x1 cmp człowieka słowami określającymi konkretną = DWORD PTR [ rbp 0x4 ] , 0 x9 jle d czynność procesora. pop ret rbp Assembler - program tłumaczący język asemblera na kod maszynowy (assemblacja) Deasembler - program tłumaczący kod maszynowy na jezyk asemblera Maszyna Z4 Konrada Zuse (1945 r.) posiadała moduł „Planfertigungsteil” umożliwiający wprowadzanie oraz odczyt rozkazów i adresów w sposób zrozumiały dla człowieka Programowanie Proceduralne 21  Języki wysokiego poziomu Języki wysokiego poziomu nie są bezpośrednio # include wykonywane przez procesor, int main ( ) { przez co pozwalają uniezależnić puts ( " Witaj swiecie ! " ) ; return 0 ; program od platformy } sprzętowej i systemowej składnia i instrukcje mają za zadanie maksymalizować zrozumienie kodu programu przez człowieka pozwalają skupić się na logice zadania kara za abstrakcję: kod niskiego poziomu zazwyczaj będzie bardziej efektywny od kodu wyższego poziomu Programowanie Proceduralne 22  Kompilatory i interpretatory Kompilator program tłumaczący kod napisany w jednym języku na równoważny kod w innym języku. Przykłady: kod źródłowy → kod maszynowy ( C, C++, Pascal, Fortran) kod źródłowy → byte code, kod pośredni rozumiany lub kompilowany przez maszynę wirtualną (Java,.Net) Interpreter odczytuje, analizuje i uruchamia instrukcje zawarte w kodzie źródłowym (brak procesu kompilacji). Języki skryptowe: Bash, Perl, Python Programowanie Proceduralne 23  Od pomysłu do programu D. Harel, Programowanie Proceduralne 24  Środowiska programistyczne C/C++ Wersja minimalistyczna: edytor tekstu + kompilator Linux: GCC (gcc, cc, g++) cc hello.c -o hello Windows: Borland C, Cygwin, MinGW IDE, Integrated Development Environment edytor, kompilator, deasembler, debugger,... Windows: MS Visual Studio Linux: KDevelop, Anjuta Linux/Windows: VS Code, CodeBlocks, Eclipse (CDT), NetBeans Programowanie Proceduralne 25 Algorytmy Programowanie Proceduralne 26  Przepis Warzenie piwa Brunświckiego Programowanie Proceduralne 27  Przepis Warzenie piwa Brunświckiego składniki (dane wejściowe): woda, słód, itd. wynik: beczka piwa sprzęt: beczka, piwowar (mielcarz) przepis: oprogramowanie, algorytm instrukcje: dodawanie składników, gotowanie, odlewanie, dolewanie, fermentacja, szpuntowanie,... Programowanie Proceduralne 28  Algorytm Algorytm jednoznacznie zdefiniowany ciąg operacji prowadzący w skończonej liczbie kroków do rozwiązania zadania. Algorytm Euklidesa, ok. 300 p.n.e. algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch liczb całkowitych dodatnich. Uznawany za pierwszy kiedykolwiek wymyślony niebanalny algorytm. Programowanie Proceduralne 29  Zadanie obliczeniowe Algorytmy to rozwiązania pewnych zadań - zadań algorytmicznych. Specyfikacja zadania algorytmicznego warunki jakie muszą spełniać dane wejściowe określenie oczekiwanych wyników jako funkcji danych wejściowych Dodatkowe ograniczenia algorytmu, np. dotyczące ilości operacji. Przykład specyfikacji: Algorytm Euklidesa Dane wejściowe: liczby całkowite x, y > 0 Wynik: N W D(x, y) Programowanie Proceduralne 30  Zadanie obliczeniowe D. Harel, Programowanie Proceduralne 31  Cechy algorytmów Cechy algorytmu skończoność - ograniczona liczna kroków poprawność - zgodny ze specyfikacją uniwersalność - poprawny dla klasy problemów efektywność - niska złożoność to gwarancja użyteczności określoność - zrozumiałe polecenia, możliwe do wykonania w jednoznacznej kolejności określony stan początkowy i wyróżniony koniec Programowanie Proceduralne 32  Struktury sterujące Ciąg struktur sterujących definiuje kolejność wykonywanych operacji. bezpośrednie następstwo: wykonaj A, potem B wybór warunkowy (rozgałęzienie): jeśli Q to wykonaj A, w przeciwnym razie wykonaj B iteracja ograniczona: wykonaj A dokładnie N razy iteracja warunkowa: dopóki Q, wykonuj A instrukcja skoku: skocz do G podprogram - wyodrębniony fragment programu, funkcja Struktury sterujące można dowolnie składać: np. pętle zagnieżdżone. „Nie ma granic zawiłości algorytmów”. Programowanie Proceduralne 33  Reprezentacja algorytmu Opis językiem naturalnym Lista kroków Schematy blokowe Pseudo-języki Języki wysokiego poziomu Programowanie Proceduralne 34  Algorytm Euklidesa Problem: znalezienie największej liczby całkowitej dzielącej bez reszty liczby całkowite dodatnie a i b Pomysł: Zauważmy, że N W D(a, b) = k =⇒ a = nk, b = mk =⇒ a − b = (m − n)k Stąd dla a > b zachodzi N W D(a, b) = N W D(a − b, b) = N W D(a − b, a). Programowanie Proceduralne 35 Algorytm Euklidesa Dane są dwie liczby całkowite. Odejmij od większej liczby mniejszą liczbę a większą liczbę zastąp uzyskaną różnicą. Powtarzaj tą czynność tak długo aż obie liczby będą równe. Otrzymana liczba jest największym wspólnym dzielnikiem liczb wejściowych. Specyfikacja Dane wejściowe: liczby całkowite a, b > 0 Wynik: liczba całkowita a stanowiąca największy wspólny dzielnik Lista kroków 1 jeśli a jest równe b to jest to największy dzielnik 2 jeśli a > b to zastąp a wartością a − b i wróć do punktu 1 3 jeśli a < b to zastąp b wartością b − a i wróć do punktu 1 Algorytm zakłada istnienie operacji −, = (porównanie) oraz >. Programowanie Proceduralne 36  Schematy blokowe Stan Blok graniczny: start, stop, przerwanie, opóźnienie. Blok operacyjny: zmiana wartości, postaci lub miejsca Instrukcje zapisu danych. Decyzja Blok decyzyjny, rozgałęzienie. Wejście/ Wprowadzanie danych i wyprowadzenia wyników. wyjście Łącznik Połączenie z innym fragmentem diagramu. Podprogram Wywołanie podprogramu. Programowanie Proceduralne 37  Przykład: Schemat blokowy Algorytm Euklidesa z odejmowaniem Start Wprowadź a,b tak a=b ? nie nie a>b ? b←b−a tak a←a−b Wypisz a Stop Programowanie Proceduralne 38  Pseudo-kod Algorithm Algorytm Euklidesa dopóki a ̸= b wykonuj jeżeli a > b wykonaj a←a−b w przeciwnym wypadku b←b−a struktura kodu języka wysokiego poziomu (często Pascal) uproszczona składnia na rzecz prostoty i czytelności formuły matematyczne, język naturalny, podprogramy nie zawiera szczegółów implementacji „Dla ludzi, nie dla maszyn”. Programowanie Proceduralne 39  Program w języku C 1 2 3 # include < s t d i o. h> 4 5 int main ( ) 6 { 7 int a , b ; 8 9 printf ( " Podaj dwie liczby calkowite : " ) ; 10 scanf ( "%d %d" , &a , &b ) ; 11 12 while ( a != b ) 13 if ( a > b ) a = a = b ; 14 else b = b = a; 15 16 printf ( " NWD = %d\n" , a ) ; 17 18 return 0 ; 19 }  euclid1.c Programowanie Proceduralne 40  Program w języku Pascal 1 program NWD ( input , output ) ; 2 { Algorytm E u k l i d e s a. } 3 var 4 A , B : Integer ; 5 begin 6 Writeln ( ’ Podaj dwie liczby calkowite : ’ ) ; 7 Readln ( a , b ) ; 8 9 while a b do 10 begin 11 if a > b then a := a = b 12 else b := b = a ; 13 end ; 14 Writeln ( ’NWD = ’ , a ) ; 15 end.  euclid1.pas Programowanie Proceduralne 41  Program w języku Fortran 77 1 PROGRAM EUCLID1 2 c Algorytm Euklidesa w jezyku Fortran 77 3 4 WRITE ( * , * ) ’ Podaj dwie liczby calkowite : ’ 5 READ ( * , * ) N , M 6 7 DO WHILE ( N. NE. M ) 8 IF ( N. GT. M ) THEN 9 N = N = M 10 ELSE 11 M = M = N 12 ENDIF 13 ENDDO 14 WRITE ( * , * ) ’NWD = ’ , N 15 END  euclid1.f Programowanie Proceduralne 42  Instrukcje warunkowe i pętle w C Warunek if (jeżeli) tak wyrażenie if ( wyrażenie ) instrukcja instrukcja nie Pętla while (dopóki) instrukcja while ( wyrażenie ) tak wyrażenie instrukcja nie Programowanie Proceduralne 43  Algorytm Euklidesa cd. Czy algorytm jest poprawny? Dla jakich danych? Problem stopu. Czy algorytm posiada skończoną ilość kroków? Efektywność algorytmu. Ile iteracji należy się spodziewać dla różnych danych? Programowanie Proceduralne 44  Algorytm Euklidesa z operacją modulo Algorithm Algorytm Euklidesa 1: dopóki b ̸= 0 wykonuj 2: c ← a mod b 3: a←b 4: b←c wymaga operacji dzielenie modulo oraz ̸= złożoność: dla a > b ­ 0 co najwyżej 2 log2 (a + b) iteracji Programowanie Proceduralne 45  1 # include < s t d i o. h> 2 3 int main ( ) 4 { 5 int a , b , c ; 6 7 printf ( " Podaj dwie liczby calkowite : " ) ; 8 scanf ( "%d %d" , &a , &b ) ; 9 printf ( " NWD (%d ,% d) = " , a , b ) ; 10 11 while ( b != 0 ) 12 { 13 c = a % b; 14 a = b; 15 b = c; 16 } 17 printf ( "%d\n" , a ) ; 18 19 return 0 ; 20 }  euclid2.c Programowanie Proceduralne 46  Esencja programowania proceduralnego Podprogram - funkcja lub procedura, wydzielona część programu wielokrotne użycie - moga być wywołane w różnych miejscach programu ekonomiczność - ujednolica powtarzające się bloki programu, mniej kodowania, czytelność - nawet przy złożonych i obszernych algorytmach modularny kod - podział kodu na mniejsze fragmenty, ułatwia jego rozwój i utrzymanie podprogram staje się nową instrukcją elementarną w języku C brak wbudowanych funkcji, tylko main() uproszczenie problemu poprzez rozbicie na mniejsze pod-problemy programowanie zstępujące (top-down) programowanie wstępujące (bottom-up) podprogram uruchamiający sam siebie - rekurencja Programowanie Proceduralne 47  1 int nwd ( int a , int b ) 2 { 3 int c ; 4 while ( b != 0 ) 5 { 6 c = a % b; 7 a = b; 8 b = c; 9 } 10 return a ; 11 }  euclid3.c 1 int nwd ( int a , int b ) 2 { 3 if ( b == 0 ) return a ; 4 return nwd ( b , a % b ) ; 5 }  euclid3rekurencja.c Programowanie Proceduralne 48  Przykład: Sortowanie Algorithm Sortowanie przez wybieranie (selection sort) Dane wejściowe: ciąg n liczb A = {a1 , a2 ,... , an } Wynik: uporządkowany ciąg a1 ¬ a2 ¬,... , ¬ an 1: i ← 1 2: dopóki i < n wykonuj 3: k ← minind({ai , ai+1 ,... , an }) ▷ Podprogram 4: ai ←→ ak 5: i←i+1 minind() wyszukuje indeks elementu o najmniejszej wartości. Wizualizacja algorytmów sortowania:  AlgoRythmics Programowanie Proceduralne 49  Przykład: Schemat blokowy Sortowanie przez wybieranie Start Wprowadź ciąg n liczb {a1 , a2 ,... , an } i←1 i←i+1 x ← ai nie i Dyrektywy preprocesora # define PI 3. 1 4 1 5 int main ( ) Funkcja główna { int i ; float x ; Deklaracje zmiennych i = 10 * PI ; x = 1.0; Instrukcje programu return 0 ; } Programowanie Proceduralne 61  Najkrótszy program Najkrótszy program w C main ( ) {} Witaj świecie # include int main ( ) { puts ( " Witaj swiecie !" ) ; return 0 ; } Programowanie Proceduralne 62  Język ANSI C mały język ale duże możliwości, ważna rola bibliotek pliki źródłowe *.c zawierają instrukcje programu pliki nagłówkowe *.h zawierają deklaracje typów i funkcji, nie zawierają instrukcji biblioteki: zbiory typów danych, stałych i funkcji biblioteki standardowe, np.: stdio.h, math.h dostęp do pamięci i rejestrów zwięzły kod - ale nie wolno przesadzać C nie chroni programisty przed nim samym Programowanie Proceduralne 63  Słowa kluczowe auto double int struct break else long switch case enum register typedef char extern return union const float short unsigned continue for signed void default goto sizeof volatile do if static while Programowanie Proceduralne 64  Dyrektywy preprocesora Dyrektywy to instrukcje zaczynające się od znaku #. Nie są słowami języka C, wykonywane są przed właściwą kompilacją. #include plik dołączenie pliku nagłówkowego zawierającego definicje funkcji, typów i stałych # include < s t d i o. h> # include "../ plik.h" #define nazwa wartość definiuje stałe, tworzy „przezwiska” do słów i wyrażeń (makra) # define PI 3. 1 4 1 5 # define TRUE 1 # define FALSE 0 # define r e a l float Programowanie Proceduralne 65  Proces kompilacji 1. Preprocesing 2. Kompilacja 3. Linkowanie plik przetworzony plik plik źródłowy kod obiektowy wynikowy *.c *.obj *.exe *.o a.out plik lib nagłowkowy *.h Programowanie Proceduralne 66  Ogólnie o procesie kompilacji Preprocesor wykonuje instrukcje zaczynające się znakiem # (dyrektywy preprocesora). Przygotowuje pliki do kompilacji. pliki źródłowe (*.c, *.h) ⇒ przetworzone pliki #include #define PI 3.14 Kompilacja tłumaczy instrukcje C na kod maszynowy przetworzone pliki ⇒ pliki obiektowe (*.obj, *.o) Konsolidacja (linkowanie) łączy pliki obiektowe w aplikację pliki obiektowe + biblioteki ⇒ program (*.exe , a.out) Programowanie Proceduralne 67  Zmienne w komputerze zmienne są określone przez typ i unikatową nazwę każda zmienna zajmuje pamięć: 1B, 2B, 4B, 8B,... adres zmiennej określa jej położenie w pamięci binarna reprezentacja zmiennych skończoność - liczby są reprezentowane poprawnie w pewnym przedziale rozdzielczość - liczby rzeczywiste są reprezentowane z pewną dokładnością char a=’C’; &a 0 1 0 0 0 0 1 1 = 67 Programowanie Proceduralne 68  Podstawowe typy danych typ reprezentacja zakres wartości char znaki (character ), kod ASCII [−127, 128] int liczby całkowite (integer ) [−231 , 231 − 1] float liczby rzeczywiste (floating point) [−3.4 × 1038 , reprezentacja zmiennoprzecinkowa +3.4 × 1038 ] najmniejsza dodatnia wartość 1.17 × 10−38 logiczny brak typu logicznego wartość całkowita 0 to fałsz a wartość różna od 0 to prawda void typ pusty, brak typu Programowanie Proceduralne 69  Deklaracje zmiennych Deklaracja występuje na początku bloku instrukcji typ identyfikator; typ identyfikator1, identyfikator2, identyfikator3; powiązanie zmiennej, stałej lub funkcji danego typu z identyfikatorem (unikatową nazwą) Przykład: int i ; float x , y ; char c , d , e ; Programowanie Proceduralne 70  Identyfikatory dozwolone znaki: litery a-z, A-Z, cyfry 0-9, podkreślnik cyfra nie może być pierwszym znakiem małe i duże litery są rozróżniane: a ̸= A zarezerwowane słowa nie mogą wystąpić w roli identyfikatorów: zadeklarowane wcześniej identyfikatory (nazyw zmiennych i funkcji), słowa kluczowe Przykład: int a , b , c ; int 0 abc ; float srednica_kola ; float ś rednica ; char PewienZnak ; float x1 , x2 , x3 ; Źle char pewien znak ; int wazna =zmienna ; Programowanie Proceduralne 71 !  Instrukcje Instrukcja prosta wyrażenie ; a = x + 1; Instrukcja prosta jest zawsze zakończona średnikiem. Instrukcja złożona (blok instrukcji) { { instrukcja 1 float x , y ; instrukcja 2 x = 1.0; y = 2.4; x = x + y; instrukcja 3 } } Instrukcje sterujące if else do while for goto Programowanie Proceduralne 72  Zakres dostępu zmiennej zmienna globalna int x = 1 ; dostępna w zakresie całego pliku int main ( ) { zmienna lokalna int x = 2 ; dostępna w zakresie funkcji main przysłania zmienną globalną x { int x = 3 ; zmienna lokalna } dostępna w zakresie bloku instrukcji {} przysłania zmienną x z funkcji main } W języku C zmienne deklaruje się na samym początku bloku (czyli przed pierwszą instrukcją). Od C99 można deklarować w dowolnym miejscu przed użyciem zmiennej Programowanie Proceduralne 73  Operatory Operatory arytmetyczne * / % + - Operatory relacji < > = == != Operatory logiczne ! && || Operator przypisania = Programowanie Proceduralne 74  Operacja przypisania wartości zmienna = wyrażenie; int i , j , k; Deklaracje zmiennych float x = 1.5; float y = 1. 5 e = 5; Inicjalizacja char znak = ’A ’ ; brak inicjalizacji i = i + 3; 3 = x; zła kolejność x + y = x = y; znak = 6 5 ; błąd Język C nie inicjuje zmiennych lokalnych - jeśli nie przypiszesz wartości to zmienna będzie posiadała pewną (losową) wartość. Dlatego warto zawsze inicjować wartości zmiennych. przypisanie porównanie C a = 3 a == 3 Pascal a := 3 a = 3 pseudo-kod a ← 3 Programowanie a = 3Proceduralne 75  Operatory arytmetyczne * mnożenie x * y x·y x / dzielenie x / y y + dodawanie x + y x+y - odejmowanie x - y x−y % reszta z dzielenia (modulo) x % y x mod 2 Reszta z dzielenia (modulo, %) określona jest tylko dla argumentów całkowitych Operator dzielenia / dla argumentów całkowitych realizuje dzielenie bez reszty! 1 / 2→0 1 / 2.0 → 0.5 1.0 / 2 → 0.5 Programowanie Proceduralne 76  Kolejność obliczeń Priorytety operatorów * / % wyższy priorytet + - niższy priorytet Dla operatorów o takim samym priorytecie obliczenia są wykonywane od lewej do prawej. x z = x / 2 * y; z= 2y z = x / (2 * y ) ; x−y z = x = y / x + y; z= x+y z = (x = y) / (x + y) ; W razie wątpliwości użyj nawiasów okrągłych. Programowanie Proceduralne 77  Komunikacja ze światem # include stdio.h - Standard input/output, biblioteka obsługująca komunikację ze standardowym wejściem i wyjściem aplikacji. printf() formatowane wyjście (wyświetlanie w terminalu) printf ( " format " , arg1 , arg2 ,... ) scanf() formatowane wejście (odczyt z klawiatury) scanf ( " format " , adres1 , adres2 ,... ) Programowanie Proceduralne 78  Specyfikacja formatu Format specyfikator znaczenie przykład wynik %f zmiennoprzecinkowa printf("%f",3.14); 3.140000 %.2f 2 miejsca po przecinku printf("%.2f",3.14); 3.14 %d dziesiętna printf("%d",75); 75 %c znak printf("%c",75); K %x szesnastkowy printf("%x",75); 4b Przykład z większą liczbą argumentów int a =2; int b =3; printf ( " Liczba %d plus %d wynosi %d\n" , a , b , a + b ) ; Wynik: Liczba 2 plus 3 wynosi 5 Programowanie Proceduralne 79  Symbole specjalne Symbole specjalne symbol znaczenie przykład wynik \n nowa linia printf("n\nn") n n \t tabulator printf("t\tt") t t \" " printf("raz \"dwa\"") raz "dwa" \\ ukośnik \ printf("C:\\Users\\") C:\Users\ %% % printf("%d%%", 5) 5% \? ? printf("Jeszcze raz\?") Jeszcze raz? Przykład printf ( "P\ tj \ tz \ nr \ te \ ta \ no \ ts \ tb \ ng \ tt \ ta \ nr \t \t" ) ; printf ( "w\ na \t \ tn \ nm \t \ te \ no \ nw \ na \ nn \ ni \ ne \n" ) ;  printf–specjalne.c Programowanie Proceduralne 80  scanf - kilka ważnych uwag specyfikator formatu powinien pasować do typu zmiennej int a ; scanf ( "%f" , &a ) ; problem !!! drugim argumentem funkcji scanf jest adres zmiennej (pamiętaj o &) formaty %f i %d pomijają początkowe białe znaki aż do napotkania wartości liczbowej znak niepasujący do formatu przerywa wczytywanie i pozostaje w strumieniu wejściowym char a ; float x , y ; wcztywanie 2 wartości scanf ( "%f%f" , &x , &y ) ; scanf ( "%c" ,&a ) ; czyta pojedynczy znak Programowanie Proceduralne 81  Przykład: pole i obwód koła Problem: wyznacz pole i obwód koła o promieniu r. r P◦ = πr2 O◦ = 2πr Programowanie Proceduralne 82  Przykład: pole i obwód koła 1 # include < s t d i o. h> 2 # define PI 3. 1 4 1 5 9 3 4 int main ( ) 5 { 6 float r , pole , obw ; 7 8 printf ( " Podaj promien kola \ nr = " ) ; 9 scanf ( "%f" , &r ) ; 10 11 pole = PI * r * r ; 12 obw = 2 * PI * r ; 13 14 printf ( " Pole kola o promieniu %f wynosi %f\n" , r , pole ) ; 15 printf ( " Obwod kola o promieniu %f wynosi %f\n" , r , obw ) ; 16 17 return 0 ; 18 }  kolo.c Programowanie Proceduralne 83  Instrukcja warunkowa if else Składnia instrukcji if tak wyrażenie if ( wyrażenie ) instrukcja instrukcja nie Przykład: if ( x > 0 ) printf ( " liczba dodatnia " ) ; if ( x % 2 == 0 ) { printf ( " liczba parzysta " ) ; x=x = 1; } Programowanie Proceduralne 84  Instrukcja warunkowa if else Składnia instrukcji if else tak nie if ( wyrażenie ) wyrażenie instrukcja 1 instrukcja 1 instrukcja 2 else instrukcja 2 Przykład: if ( x % 2 ) printf ( " liczba nieparzysta " ) ; else printf ( " liczba parzysta " ) ; if ( x > 0 ) { printf ( " liczba dodatnia " ) ; x=x = 1; } else x =0; Programowanie Proceduralne 85  Operatory relacji operator znaczenie przykład mat. < mniejszy niż x < y x większy niż x > y x>y = y x­y == równy x == y x=y != różny x != y x ̸= y Programowanie Proceduralne 86  Operatory logiczne operator znaczenie przykład mat. ! negacja (NOT) !x ¬x && koniunkcja (AND) x>1 && y1∧y 0 ) if ( x < 10 ) printf ( " liczba wieksza od 0 i mniejsza niz 10 " ) ; if ( x > 0 && x < 10 ) printf ( " liczba wieksza od 0 i mniejsza niz 10 " ) ; if ( ! ( x > 0 ) ) printf ( " liczba ujemna lub zero " ) ; if ( ! x > 0 ) printf ( " \? " ) ; if ( x+1 > y =1 ) printf ( " \? " ) ; if ( x | | ! y && z ) printf ( " \? " ) ; Kolejność operatorów: !, arytmetyczne, relacji, &&, || W razie wątpliwości użyj nawiasów okrągłych. Programowanie Proceduralne 88  Przykład: Równanie z jedną niewiadomą Problem: znajdź miejsce zerowe funkcji liniowej f (x) = ax + b Algorithm Równanie z jedną niewiadomą Dane wejściowe: współczynniki a, b ∈ R Wynik: miejsce zerowe x0 ∈ R lub informacja o braku rozwiązania 1: jeżeli a ̸= 0 wykonaj 2: x0 ← − ab 3: wypisz: x0 4: w przeciwnym wypadku 5: wypisz: Brak rozwiązania Programowanie Proceduralne 89  1 # include < s t d i o. h> 2 3 int main ( ) 4 { 5 float a , b , x0 ; 6 7 printf ( " Podaj wspolczynniki rownania \n" ) ; 8 printf ( "a = " ) ; scanf ( "%f" , &a ) ; 9 printf ( "b = " ) ; scanf ( "%f" , &b ) ; 10 11 if ( a != 0. 0 ) 12 { 13 x0 = =b / a ; 14 printf ( " x0 = %.4 f\n" , x0 ) ; 15 } 16 else printf ( " Brak rozwiazan \n" ) ; 17 18 return 0 ; 19 }  linia.c Programowanie Proceduralne 90  Pętla while Składnia pętli while (dopóki) instrukcja tak while ( wyrażenie ) wyrażenie instrukcja nie Przykład int n = 1 0 ; while ( n > 0 ) Pętla nieskonczona { printf ( "%d\n" , n ) ; while ( 1 ) printf ( "C" ) ; n = n = 1; } Programowanie Proceduralne 91  Przykład: wyznaczanie silni n! Problem: wyznaczenie wartości silni n! = 1 · 2 · 3 ·... · n Algorithm Silnia Dane wejściowe: liczba całkowita n ­ 0 Wynik: wartość x = n! 1: i ← 2 2: x ← 1 3: dopóki i ¬ n wykonuj 4: x←x·i 5: i←i+1 6: wypisz x Programowanie Proceduralne 92  1 # include 2 3 int main ( ) 4 { 5 int x , i , n ; 6 7 printf ( "n = " ) ; 8 scanf ( "%d" , &n ) ; 9 10 if ( n 0 √ Wynik: wartość przybliżona x ≈ a z dokładnością ϵ 1: x ← x0 2: wykonuj 3: x0 ← x  4: x ← 12 x0 + xa0 5: dopóki |x − x0 | > ϵ 6: wypisz x Programowanie Proceduralne 121  1 # include 2 3 int main ( ) 4 { 5 const float eps = 1e = 4; 6 float x , a , x0 ; 7 8 printf ( "a = " ) ; scanf ( "%f" , &a ) ; 9 10 if ( a < 0 ) printf ( " Zle dane : a < 0\ n" ) ; 11 else 12 { 13 x0 = 1 ; 14 x = x0 ; 15 do 16 { 17 x0 = x ; 18 x = ( x0 + a/ x0 ) / 2 ; 19 } while ( x = x0 > eps | | x = x0 < =eps ) ; 20 21 printf ( " pierwiastek z %f wynosi %f ( eps = %f )\ n" , a , x , eps ) ; 22 } 23 return 0 ; 24 }  heron.c Programowanie Proceduralne 122  Pętla for for ( wyrażenie 1 ; wyrażenie 2 ; wyrażenie 3 ) instrukcja wyrażenie 1 int s=1 , n =100 , i ; for ( i =1; i 2 3 int main ( ) 4 { 5 int n ; 6 int stop = 0 ; 7 8 while ( stop == 0 ) 9 { 10 printf ( " Podaj liczbe z zakresu od 1 do 10\ n" ) ; 11 scanf ( "%d" , &n ) ; 12 if ( n >= 1 && n 2 3 int main ( ) 4 { 5 int i , j , n ; 6 7 printf ( " Podaj zakres : " ) ; 8 scanf ( "%d" , &n ) ; 9 10 printf ( " Liczby pierwsze w zakresie od 1 do %d\n" , n ) ; 11 12 for ( i =2; i 42 ) goto koniec ; 10 } 11 } 12 } 13 14 koniec :  goto4.c przykładowe uzasadnienie użycia instrukcji skoku - zakończenie zagnieżdonej pętli ale zagnieżdzone pętle to też oznaka złych praktyk Programowanie Proceduralne 134 http://xkcd.com/292/ Programowanie Proceduralne 135  Switch Instrukcja warunkowa switch porównuje wyrażenie z listą wartości i wykonuje instrukcje pasującego przypadku (case). switch( wyrażenie ) { case wartość 1: instrukcja 1 break; case wartość 2: instrukcja 2 break;... default : instrukcja n } Programowanie Proceduralne 136  1 # include 2 3 int main ( ) 4 { 5 float x , y ; 6 char op ; 7 8 scanf ( "%f %c%f" ,&x , &op , &y ) ; 9 10 switch ( op ) 11 { 12 case ’+ ’ : 13 printf ( "%f\n" , x+y ) ; 14 break ; 15 case ’-’ : 16 printf ( "%f\n" , x=y ) ; 17 break ; 18 case ’* ’ : 19 printf ( "%f\n" , x * y ) ; 20 break ; 21 case ’/ ’ : 22 printf ( "%f\n" , x/y ) ; 23 break ; 24 default : 25 printf ( " Nieznana operacja : %c\n" , op ) ; 26 } 27 return 0 ; 28 }  switch.c Programowanie Proceduralne 137  Switch Dopasowanie przypadków tylko dla zmiennych całkowitych (int, char, enum) break konczy działanie instrukcji switch instrukcje break i default są opcjonalne Po dopasowaniu właściwego przypadku wykonywane są WSZYSTKIE instrukcje aż do napotkania pierwszego wystąpienia brake (lub do końca bloku switch). Pominięcie instrukcji break spowoduje więc wykonanie instrukcji dla kolejengo przypadku. Programowanie Proceduralne 138  1 # include 2 3 int main ( ) 4 { 5 int n ; 6 7 printf ( " Podaj liczbe od 1 do 4\ n" ) ; 8 scanf ( "%d" , &n ) ; 9 10 switch ( n ) 11 { 12 case 1 : 13 printf ( " Przypadek 1\ n" ) ; 14 case 2 : Podaj liczbe od 1 d 15 printf ( " Przypadek 2\ n" ) ; 2 16 case 3 : Przypadek 2 17 printf ( " Przypadek 3\ n" ) ; Przypadek 3 18 break ; 19 case 4 : 20 printf ( " Przypadek 4\ n" ) ; 21 break ; 22 default : 23 printf ( " Nieznana operacja.\ n" ) ; 24 } 25 return 0 ; 26 } Programowanie Proceduralne 139  Podsumowanie Instrukcje warunkowe: if, else, switch Pętle: while, do while, for Operator inkrementacji ++ i dekrementacji -- Instrukcja skoku goto (lepiej nie używać) Instrukcja przerwania break oraz kontynuacji pętli continue Instrukcja wielokrotnego wyboru switch Programowanie Proceduralne 140  Literatura dodatkowa David Griffiths, Dawn Griffiths „Rusz głową! C.”, Helion, Gliwice, 2013. „Kurs programowania w C”, WikiBooks, http://pl.wikibooks.org/wiki/C Programowanie Proceduralne 141  Funkcje czyli jak programować proceduralne. Programowanie Proceduralne 142  Struktura programu w C # include < s t d i o. h> # define PI 3. 1 4 1 5 Dyrektywy preprocesora float g = 2. 5 ; Zmienne globaln float kwadrat ( float x ) { return x * x ; } Definicja funkcji Funkcja główna int main ( ) { float x , y ; Zmienne lokalne x = PI * g ; y = kwadrat ( x ) ; Instrukcje programu return 0 ; } Programowanie Proceduralne 143  Funkcje = podprogramy Podprogram wydzielony fragment programu (kodu) zawierający instrukcje do wielokrotnego użytku Dekompozycja złożonego problemu na prostsze Przejrzystość Unikanie powtórzeń kodu Uniwersalność - jak najmniejszy związek z konkretnym kodem Biblioteki funkcji - zbiory funkcji ogólnego zastosowania Rekurencja(Rekurencja(Rekurencja(Rekurencja(...)))) Nic za darmo - wywołanie funkcji to dodatkowy koszt czasu i pamięci Programowanie Proceduralne 144  Anatomia funkcji Deklaracja funkcji (prototyp) Zapowiedź użycia funkcji - określenie nazwy funkcji, typów argumetów i typu wartości zwracanej typ identyfikator(typ arg1, typ arg2,... ); Definicja funkcji Deklaracja parametrów i instrukcje podprogramu (ciało funkcji). typ identyfikator(typ arg1, typ arg2,... ) { deklaracje zmiennych lokalnych instrukcje return wartość; } Programowanie Proceduralne 145  Przykłady deklaracji Deklaracje Wywołanie float sin ( float x ) ; y = sin ( x ) ; float pierwiastek ( float x ) ; y = pierwiastek ( 5. 0 ) ; void wypiszmenu ( void ) ; wypiszmenu ( ) ; int random ( void ) ; i = random ( ) ; int nwd ( int a , int b ) ; i = nwd ( 1 4 4 , a + 1 ) ; char getchar ( void ) ; z = getchar ( ) ; int fff ( int z , char z , float a ) ; i = fff ( 3 , ’A ’ , 3. 1 4 ) ; Programowanie Proceduralne 146  Przykład funkcji NWD 1 # include < s t d i o. h> 2 3 int nwd ( int a , int b ) 4 { 5 int c ; 6 while ( b != 0 ) 7 { 8 c = a % b; 9 a = b; 10 b = c; 11 } 12 return a ; 13 } 14 15 int main ( ) 16 { 17 int a , b ; 18 19 printf ( " Podaj dwie liczby calkowite : " ) ; 20 scanf ( "%d %d" , &a , &b ) ; 21 printf ( " NWD (%d ,% d) = %d\n" , a , b , nwd ( a , b ) ) ; 22 23 return 0 ; 24 } Programowanie Proceduralne 147  Parametry formalne i aktualne funkcji Parametry formalne int nwd ( int a , int b ) { int c ;... } Parametry aktualne float x , y ; int a=1 , b=2 , c ; x = sin ( 1 ) ; c = nwd ( 1 4 4 , b ) ; y = sin ( x * nwd (1+a , nwd ( 1 0 0 , b ) ) ) ; W języku C argumenty są przekazywane wyłącznie przez wartość, tzn. wartość argumentu jest kopiowana do parametru formalnego. Programowanie Proceduralne 148  Funkcje a procedury Funkcja bez wartości zwracanej - procedura void wypisz ( int n ) { while ( n>0 ) { printf ( " Programowaie proceduralne \n" ) ; n = n = 1; } } Funkcja z wartością zwracaną int silnia ( int n ) { int i =2; x =1; while ( i 2 # include 3 # define EPS 0. 0 0 0 0 0 1 4 5 int main ( ) 6 { 7 float x = 0. 1 ; 8 9 if ( fabs ( x = 0.1) < EPS ) 10 printf ( "OK , %f jest rowne 0.1\ n" , x ) ; 11 else 12 printf ( " Nie OK , %f nie jest rowne 0.1\ n" , x ) ; 13 14 return 0 ; 15 }  prec2.c Programowanie Proceduralne 315  1 # include < s t d i o. h> 2 # include 3 4 int main ( ) 5 { 6 printf ( " Limity typu float :\ n" ) ; 7 printf ( " sizeof ( float ) : % lu \n" , sizeof ( float ) ) ; 8 printf ( " Najwieksza wartosc : %e\n" , FLT_MAX ) ; 9 printf ( " Najmniejsza dodatnia : %e\n" , FLT_MIN ) ; 10 printf ( " Epsilon maszynowy : %e\n" , FLT_EPSILON ) ; 11 printf ( " Cyfry znaczace : %d\n" , FLT_DIG ) ; 12 13 printf ( "\ nLimity typu double :\ n" ) ; 14 printf ( " sizeof ( double ) : % lu \n" , sizeof ( double ) ) ; 15 printf ( " Najwieksza wartosc : %e\n" , DBL_MAX ) ; 16 printf ( " Najmniejsza dodatnia : %e\n" , DBL_MIN ) ; 17 printf ( " Epsilon maszynowy : %e\n" , DBL_EPSILON ) ; 18 printf ( " Cyfry znaczace : %d\n" , DBL_DIG ) ; 19 20 printf ( "\ nLimity typu long double :\ n" ) ; 21 printf ( " sizeof ( long double ) : % lu \n" , sizeof ( long double ) ) ; 22 printf ( " Najwieksza wartosc : % Le \n" , LDBL_MAX ) ; 23 printf ( " Najmniejsza dodatnia : % Le \n" , LDBL_MIN ) ; 24 printf ( " Epsilon maszynowy : % Le \n" , LDBL_EPSILON ) ; 25 printf ( " Cyfry znaczace : %d\n" , LDBL_DIG ) ; 26 27 return 0 ; 28 }  float.c Programowanie Proceduralne 316  Wartości mogą się różnić zależnie od imple 1 # include < s t d i o. h> 2 # include Limity typu float: 3 sizeof(float) : 4 4 int main ( ) Najwieksza wartosc : 3.402823e+3 5 { Najmniejsza dodatnia : 1.175494e-3 6 printf ( " Limity typu float :\ n" ) ; Epsilon maszynowy : 1.192093e-0 7 printf ( " sizeof ( float ) : % lu \n" , sizeof ( float ) ) ; 8 printf ( " Najwieksza wartosc : %e\n" , FLT_MAX ) ; Cyfry znaczace : 6 9 printf ( " Najmniejsza dodatnia : %e\n" , FLT_MIN ) ; 10 printf ( " Epsilon maszynowy : %e\n" , FLT_EPSILON Limity ); typu double: 11 printf ( " Cyfry znaczace : %d\n" , FLT_DIG ) ; sizeof(double) : 8 12 Najwieksza wartosc : 1.797693e+3 13 printf ( "\ nLimity typu double :\ n" ) ; Najmniejsza dodatnia : 2.225074e-3 14 printf ( " sizeof ( double ) : % lu \n" , sizeof ( double ) ) ; maszynowy Epsilon : 2.220446e-1 15 printf ( " Najwieksza wartosc : %e\n" , DBL_MAX ) ; Cyfry znaczace : 15 16 printf ( " Najmniejsza dodatnia : %e\n" , DBL_MIN ) ; 17 printf ( " Epsilon maszynowy : %e\n" , DBL_EPSILON Limity ); typu long double: 18 printf ( " Cyfry znaczace : %d\n" , DBL_DIG ) ; sizeof(long double) : 16 19 20 printf ( "\ nLimity typu long double :\ n" ) ; Najwieksza wartosc : 1.189731e+4 21 printf ( " sizeof ( long double ) : % lu \n" , sizeof ( longNajmniejsza double ) ) ; dodatnia : 3.362103e-4 22 printf ( " Najwieksza wartosc : % Le \n" , LDBL_MAX ) Epsilon ; maszynowy : 1.084202e-1 23 printf ( " Najmniejsza dodatnia : % Le \n" , LDBL_MIN ) Cyfry ; znaczace : 18 24 printf ( " Epsilon maszynowy : % Le \n" , LDBL_EPSILON ) ; 25 printf ( " Cyfry znaczace : %d\n" , LDBL_DIG ) ; 26 27 return 0 ; 28 }  float.c Programowanie Proceduralne 317  Inne możliwe problemy nadmiar (overflow ) - przekroczenie zakresu (+Inf, -Inf) niedomiar (underflow ) - zaokrąglenie bardzo małej liczby do 0 redukcja cyfr przy odejmowaniu bardzo bliskich sobie liczb dodawanie (lub odejmowanie) dużej i małej liczby kolejność operacji może mieć wpływ na wynik (a + b) + c ̸= a + (b + c) zaokrąglenia, np. liczby 0.1 nie można dokładnie reprezentować w systemie binarnym 25 luty 1991 r., wojna w zatoce perskiej, awaria systemu antyrakietowego Patriot (zegar rakiety tykał co 0.1 s.), zginęło 28 amerykańskich żołnierzy a 100 zostało rannych. Programowanie Proceduralne 318  Przykład: szereg harmoniczny Problem: wyznaczyć sumę pierwszych n elementów szeregu harmonicznego n X 1 1 1 =1+ + +... −−−→ ∞ i=1 n 2 3 n→∞ Programowanie Proceduralne 319  1 # include < s t d i o. h> 2 n=66 3 int main ( ) x=4.774428 4 { y=4.774427 5 float x =0.0 , y = 0. 0 ; 6 int i=1 , n ; n=600 7 x=6.974980 8 printf ( "n=" ) ; scanf ( "%d" , &n ) ; y=6.974978 9 10 for ( i =1; i=1; i ==) y=8.178370 14 y = y + 1.0/ i ; 15 n=500000 16 printf ( "x =% f\ ny =% f\n" , x , y ) ; x=13.690692 17 return 0 ; y=13.699607 18 } n=1000000  szereg.c x=14.357358 y=14.392652 Programowanie Proceduralne 320  Podsumowanie Typy całkowite: char, short, int, long Typy całkowite bez znaku: unsigned Typy zmiennopozycyjne: float, double Nadmiar, niedomiar i inne efekty wynikające z bitowej reprezentacji liczb 3/2 wynosi 1, zaś 3/2.0 wynosi 1.5 Porównywanie wartości zmiennopozycyjnych fabs(a-b)= ’a ’ && x int getchar() 2 # include zwraca pojedynczy 3 znak ze standardowego 4 int main ( ) wejścia lub EOF 5 { 6 int a ; void putchar(int c) 7 8 while ( ( a = getchar ( ) ) != EOF ) wypisuje znak 9 putchar ( toupper ( a ) ) ; 10 EOF (end of file) 11 return 0 ; bajt końca pliku 12 } toupper2 < plik.txt  toupper2.c EOF w terminalu: Ctrl+Z (Windows) Ctrl+D (Unix/Linux) Programowanie Proceduralne 330  Teoria łańcuchów Łańcuch znakowy (string, napis) - skończony ciąg symboli alfabetu W języku C brak typu string, występuje w C++ Łańcuch to tablica zawierająca ciąg znaków zakończony znakiem ’\0’ (wartość liczbowa zero) A l a m a k o t a \0 Dostęp do znaku jak w tablicach: t[i] Stała napisowa (literał znakowy): "Ala ma kota" Stała znakowa ’A’ to liczba 65 Stała napisowa "A" to tablica A \0 Programowanie Proceduralne 331  Inicjowanie stałych napisowaych Zmienna wskaźnikowa wskazująca na stały napis (nie można go zmodyfikować) char * s1 = " nieciekawy fragment tekstu." ; Tablica zawierająca napis (może być modyfikowana) char s2 [ ] = " Ala ma kota " ; Tablica zawierająca napis "Ala" char s3 [ ] = { ’A ’ , ’l ’ , ’a ’ , ’\0 ’ } ; Programowanie Proceduralne 332  Przykład w C # include int main ( ) { char * s1=" nieciekawy fragment tekstu." ; char s2 [ ] = " Ala ma kota " ; s1 [ 0 ] = ’N ’ ; s2 [ 0 ] = ’E ’ ; printf ( s1 ) ; printf ( " %s\n" , s2 ) ; printf ( "\ nBardzo %s\n" , s1 +3); staly n a p is e ! Źl return 0 ; s1 to } Programowanie Proceduralne 333  Wczytywanie łańcucha scanf("%s",...); # include int main ( ) { char text [ 1 0 ] ; scanf ( "%s" , text ) ; } niebezpieczeństwo przepełnienia tablicy scanf("%10s", text); poprawnie, wczyta max. 10 znaków odczytuje tylko pierwszy wyraz napisu, do wystąpienia białego znaku Programowanie Proceduralne 334  Wczytywanie łańcucha char *gets(char *s); funkcja gets() czyta linię tekstu ze standardowego wejścia i umieszcza ją w tablicy s Uwaga: brak zabezpieczenia przed przepełnieniem tablicy, nie należy stosować tej funkcji # include int main ( ) { char text [ 1 0 ] ; gets ( text ) ; } Programowanie Proceduralne 335  Wczytywanie łańcucha char *fgets(char *s, int n, FILE *f); czyta linię tekstu (ale nie więcej niż n znaków) ze strumienia f i umieszcza tekst w tablicy s obowiązkowe podanie parametru n - użycie funkcji jest bezpieczne standardowy strumień wejściowy to stdin znak ’\n’ również umieszczony jest na końcu napisu # include int main ( ) { char text [ 1 0 ] ; fgets ( text , 1 0 , stdin ) ; } Programowanie Proceduralne 336  Wypisywanie łańcucha znakowego int puts(char *s); wypisuje łańcuch i dodaje znak nowej lini int printf(char *s,...); wypisuje napis zgodnie z zadanym formatem Programowanie Proceduralne 337  printf Specyfikacja formatu %[flagi][szerokość][.precyzja][długość]specyfikator http://wikipedia.org Programowanie Proceduralne 338 %[flagi][szerokość][.precyzja][długość]specyfikator specyfikator znaczenie przykład wynik d lub i liczba całkowita ze znakiem printf("%d", -123) -123 u liczba całkowita bez znaku printf("%u", 123) 123 o liczba całkowita bez znaku ósemkowa printf("%o", 123) 173 x lub X liczba całkowita bez znaku szesnastkowo printf("%o", 123) 7b f lub F zmiennopozycyjna w zapisie dziesiętnym printf("%f", 12.6) 12.600000 e lub E notacja naukowa printf("%e", 12.6) 1.260000e+01 g lub G krótszy zapis %f lub %e printf("%g", 12.6) 12.6 c pojedynczy znak (ASCII) printf("%c", ’a’) a s łańcuch znakowy printf("%s", "Ala ma kota") Ala ma kota p adres (wskaźnik), szesnastkowo printf("%p", &a) ff01ffab % wypisuje znak % printf("%%") % Programowanie Proceduralne 339 %[flagi][szerokość][.precyzja][długość]specyfikator szerokość znaczenie przykład wynik liczba minimalna ilość znaków (szerokość pola), brakujące miej- printf("_%5d_", 42) _ 42_ sca są dopełniane spacjami. Jeżeli szerokość pola jest za mała to wynik nie jest obcinany. * szerokość zależna od argumentu funkcji printf printf("_%*d_", 5, 42) _ 42_ flaga znaczenie przykład - wyrównanie do lewej (względem podanej szerokości) printf("_%-5d_", 42) _42 _ + liczby dodatnie poprzedzone znakiem + printf("_%-+5d_", 42) _+42 _ spacja wstawia spację zamiast znaku + printf("_%- 5d_", 42) _ 42 _ 0 wypełnia podaną szerokość znakiem 0 printf("_%05d_", 42) _00042_ # liczby ósemkowe i szesnastkowe poprzedza 0, 0x, 0X printf("%#x, 42) 0x2a Programowanie Proceduralne 340 %[flagi][szerokość][.precyzja][długość]specyfikator precyzja znaczenie przykład wynik.liczba ilość cyfr wypisywanych po przecin- printf("%.2f", 1.66666) 1.67 ku. Dla napisów oznacza maksymal- ną liczbę wypisanych znaków (łańcuch jest obcinany).* precyzja liczby zmiennopozycyjnej nie printf("%.*f", 2, 1.66666) 1.67 jest podawana w formacie lecz po- przez argument funkcji printf. długość znaczenie przykład brak typy char, short, int, double, float printf("%f", x) l typ long int printf("%ld", x) ll typ long long int printf("%lld", x) L typ long double printf("%Lf", x) Programowanie Proceduralne 341  1 # include < s t d i o. h> 2 3 int main ( ) 4 { 5 printf ( " Znaki : %c %c \n" , ’A ’ , 6 5 ) ; 6 printf ( " Liczby calkowite : %d \n" , 1 2 3 ) ; 7 printf ( " ze znakiem : %+ d \n" , 1 2 3 ) ; 8 printf ( " szesnastkowo : %x %# x \n" , 1 2 3 , 1 2 3 ) ; 9 printf ( " dopelnienie spacjami : %20 d \n" , 1 2 3 ) ; 10 printf ( " dopelnienie zerami : %020 d \n" , 1 2 3 ) ; 11 printf ( " Zmienopozycyjne : %f \n" , 3. 1 4 1 6 ) ; 12 printf ( " notacja naukowa : %e \n" , 3. 1 4 1 6 ) ; 13 printf ( " precyzja : %.3 f \n" , 3. 1 4 1 6 ) ; 14 printf ( " dopelnienie : %20.3 f \n" , 3. 1 4 1 6 ) ; 15 printf ( " Szerokosc pola * : %* d \n" , 2 0 , 1 2 3 ) ; 16 printf ( " Precyzja.* : %20.* f \n" , 3 , 3. 1 4 1 6 ) ; 17 printf ( " Napis : %s \n" , " Ala ma kota " ) ; 18 printf ( " dopelnienie : %20 s \n" , " Ala ma kota " ) ; 19 printf ( " obciecie : %20.5 s \n" , " Ala ma kota " ) ; 20 21 return 0 ; 22 }  printf.c Programowanie Proceduralne 342  1 # include < s t d i o. h> 2 3 int main ( ) 4 { 5 printf ( " Znaki : %c %c \n" , ’A ’ , 6 5 ) ; 6 printf ( " Liczby calkowite : %d \n" , 1 2 3 ) ; 7 printf ( " ze znakiem : %+ d \n" , 1 2 3 ) ; 8 printf ( " szesnastkowo : %x %# x \n" , 1 2 3 , 1 2 3 ) ; 9 printf ( " dopelnienie spacjami : %20 d \n" , 1 2 3 ) ; 10 printf ( " dopelnienie zerami : %020 d \n" , 1 2 3 ) ; 11 printf ( " Zmienopozycyjne : %f \n" , 3. 1 4 1 6 ) ; 12 printf ( " notacja naukowa : %e \n" , 3. 1 4 1 6 ) ; 13 printf ( " precyzja : %.3 f \n" , 3. 1 4 1 6 ) ; 14 printf ( " dopelnienie : %20.3 f \n" , 3. 1 4 1 6 ) ; 15 printf ( " Szerokosc pola * : %* d \n" , 2 0 , 1 2 3 ) ; 16 printf ( " Precyzja.*Znaki A A, 3 , 3. 1 4 1 6 ) ; : %20.* f : \n" 17 printf ( " Napis : %s \n" :, 123 Liczby calkowite " Ala ma kota " ) ; 18 printf ( " dopelnienie ze znakiem : %20 s \n" , " Ala ma kota " ) ; : +123 19 printf ( " obciecie szesnastkowo: %20.5 s : \n" , " Ala ma kota " ) ; 7b 0x7b 20 dopelnienie spacjami : 123 21 return 0 ; dopelnienie zerami : 00000000000000000123 22 } Zmienopozycyjne : 3.141600 notacja naukowa : 3.141600e+00 precyzja : 3.142  printf.c... Programowanie Proceduralne 343... Zmienopozycyjne : 3.141600 1 # include < s t d i o. h> notacja naukowa : 3.141600e+00 2 precyzja : 3.142 3 int main ( ) dopelnienie : 3.142 4 { Szerokosc pola * : 123 5 printf ( " Znaki.* %c \n" , ’A Precyzja: %c : ’ , 65) ; 3.142 6 printf ( " Liczby calkowite Napis : %d \n" , 1 2 3 ):; Ala ma kota 7 printf ( " ze znakiem : %+ d \n" , 1 2 3:) ; dopelnienie Ala ma kota 8 printf ( " szesnastkowo : %x %# x \n" , :1 2 3 , 1 2 3 ) ; obciecie Ala m 9 printf ( " dopelnienie spacjami : %20 d \n" , 1 2 3 ) ; 10 printf ( " dopelnienie zerami : %020 d \n" , 1 2 3 ) ; 11 printf ( " Zmienopozycyjne : %f \n" , 3. 1 4 1 6 ) ; 12 printf ( " notacja naukowa : %e \n" , 3. 1 4 1 6 ) ; 13 printf ( " precyzja : %.3 f \n" , 3. 1 4 1 6 ) ; 14 printf ( " dopelnienie : %20.3 f \n" , 3. 1 4 1 6 ) ; 15 printf ( " Szerokosc pola * : %* d \n" , 2 0 , 1 2 3 ) ; 16 printf ( " Precyzja.* : %20.* f \n" , 3 , 3. 1 4 1 6 ) ; 17 printf ( " Napis : %s \n" , " Ala ma kota " ) ; 18 printf ( " dopelnienie : %20 s \n" , " Ala ma kota " ) ; 19 printf ( " obciecie : %20.5 s \n" , " Ala ma kota " ) ; 20 21 return 0 ; 22 }  printf.c Programowanie Proceduralne 344  Podstawowe operacje na łańcuchach Plik nagłówkowy string.h długość łancucha s int strlen ( const char * s ) ; łączenie dwóch łańcuchów, do dest doklej src char * strcat ( char * dest , const char * src ) ; porównywanie łańcuchów int strcmp ( const char * s1 , const char * s2 ) ; wynik 0 gdy s1 i s2 są takie same, wynik -1 gdy s1 < s2, lub 1 gdy s1 > s2 kopiowanie łańcuchów, umieszcza src w tablicy dest char * strcpy ( char * dest , const char * src ) ; wyszukiwanie wzorca wzor w tekscie napis char * strstr ( const char * napis , const char * wzor ) ; wynikiem jest adres pierwszego Programowanie wsytąpienia wzorca lub NULL345 Proceduralne  Wyszukiwanie wzorca Problem: wyszukiwanie podciągu (pattern matching ). W ciągu T znajdź wystąpienie wzorca W. Tekst T = "programowanie" p r o g r a m o w a n i e \0 Wzorzec W = "gra" g r a \0 Programowanie Proceduralne 346 Algorithm Naiwne wyszukiwanie wzorca Dane wejściowe: łańcuch znaków T , wzorzec W Wynik: pozycja tekstu W w T lub wartość -1, gdy brak 1: dla każdego i = 0, 1, 2,... , |T | − |W| wykonuj 2: k←0 3: dopóki T [i + k] = W[k] i k < |W| wykonuj 4: k ←k+1 5: jeżeli k = |W| wykonaj 6: zwróć i 7: zwróć −1 |W| oznacza długość łańcucha W Programowanie Proceduralne 347  Algorytm naiwny Tekst T = "programowanie" Wzorzec W = "mowa" i= 0 1 2 3 4 5 6 7 8 9 10 11 12 p r o g r a m o w a n i e 1: m o w a 2: m o w a 3: m o w a 4: m o w a 5: m o w a 6: m o w a 7: m o w a k= 0 1 2 3 Programowanie Proceduralne 348  Przykłady w C 1 int strindex ( char t [ ] , char w [ ] ) 2 { 3 int i , k ; 4 5 i =0; 6 while ( t [ i ] != ’\0 ’ ) 7 { 8 k =0; 9 while ( t [ i+k ] == w [ k ] && w [ k ] != ’\0 ’ ) 10 { 11 k = k + 1; 12 } 13 if ( w [ k ] == ’\0 ’ ) return i ; 14 i = i + 1; 15 } 16 return = 1; 17 }  strindex.c Programowanie Proceduralne 349  Przykłady w C To samo z użyciem wskaźników 1 int strindex ( char * t , char * w ) 2 { 3 char * pt , * pw , * pt2 ; 4 5 for ( pt=t ; * pt != ’\0 ’ ; pt++) 6 { 7 pw=w ; 8 pt2=pt ; 9 while ( * pt2 == * pw && * pw != ’\0 ’ ) 10 { 11 pw++; 12 pt2++; 13 } 14 if ( * pw == ’\0 ’ ) return pt=t ; 15 } 16 return = 1; 17 }  strindex3.c Programowanie Proceduralne 350  Podsumowanie Typ znakowy jest liczbą całkowitą Łańcuch to tablica znaków zakończona znakiem ’\0’ Stała znakowa w apostrofach ’A’ Stała napisowa w cudzysłowach "A" jest tablicą Porównywanie łańcuchów: t == "napis" źle, trzeba znak po znaku (funkcja strcmp()) Kopiowanie napisów: t = "napis" źle, kopiowanie tablic (funkcja srtcpy()) Programowanie Proceduralne 351  Literatura dodatkowa Linux Programmer’s Manual man 7 ascii unicode codepages iso 8859-2 http://www.unix.com/man-page/ Wikipedia:  Kodowanie polskich znaków diakrycznych Jerzy Wałaszek, „Algorytmy. Struktury danych.”,  Łańcuchy znakowe. R.S. Boyer, J. Strother Moore, A Fast String Searching Algorithm Communications of the Association for Computing Machinery, 20(10), 1977, pp. 762-772. www.cs.utexas.edu/~moore/publications/fstrpos.pdf Programowanie Proceduralne 352  Operatory Operatory bitowe i uzupełnienie informacji o pozostałych operatorach. Programowanie Proceduralne 353  Przypomnienie: operatory Operator przypisania = przypisanie x = y x←y Operatory arytmetyczne * mnożenie x * y x·y x / dzielenie x / y y + dodawanie x + y x+y - odejmowanie x - y x−y % reszta z dzielenia (modulo) x % y x mod 2 ++ inkrementacja x++ x←x+1 -- dekrementacja x-- x←x−1 Operatory relacji < mniejszy niż x < y x większy niż x > y x>y = y x­y == równy x == y x=y != różny x != y x ̸= y Operatory logiczne ! negacja (NOT) !x ¬x && koniunkcja (AND) x>1 && y1∧y a = 9 2 b = 12 3 int main ( ) ~a = 4294967286 4 { ~b = 4294967283 5 unsigned int a = 9 ; a & b = 8 6 unsigned int b = 1 2 ; a | b = 13 7 8 printf ( "a = %u\ nb = %u\n" ,a a^, bb )=; 5 9 printf ( "~a = %u\n~b = %u\n" , ˜a , ˜b ) ; 10 printf ( "a & b = %u\n" , a & b ) ; 11 printf ( "a | b = %u\n" , a | b ) ; 12 printf ( "a ^ b = %u\n" , a ˆ b ) ; 13 14 return 0 ; 15 }  bitowe1.c Programowanie Proceduralne 357  Przykład a 9 00000000000000000000000000001001 ~a 4294967286 11111111111111111111111111110110 a 9 00000000000000000000000000001001 b 12 00000000000000000000000000001100 a & b 8 00000000000000000000000000001000 a 9 00000000000000000000000000001001 b 12 00000000000000000000000000001100 a | b 13 00000000000000000000000000001101 a 9 00000000000000000000000000001001 b 12 00000000000000000000000000001100 a ^ b 5 00000000000000000000000000000101 Programowanie Proceduralne 358  Szyfrowanie XOR Operacja XOR jest wykorzystywana np. w funkcjach haszujących i algorytmach szyfrujących. A ^ B ^ B −→ A 1 # include 2 3 int main ( ) 4 { 5 unsigned char klucz = 1 3 ; 6 char znak ; 7 8 while ( ( znak=getchar ( ) ) != EOF ) 9 putchar ( znak ˆ klucz ) ; 10 11 return 0 ; 12 }  szyfr–xor.c Programowanie Proceduralne 359  Przesunięcie bitowe operator znaczenie przykład przesunięcie bitowe w prawo x >> y pozycje wszystkich bitów są przesuwane bity skrajne są tracone, puste miejsca są zastępowane zerami odpowiada do mnożeniu/dzieleniu całkowitemu przez 2 Programowanie Proceduralne 360  Przykład a = 5 1 # include < s t d i o. h> a 1 = 2 4 { a >> 2 = 1 5 unsigned int a = 5 ; 6 7 printf ( "a = %u\n" , a) ; 8 printf ( "a 1 = %u\n" , a >> 1) ; 11 printf ( "a >> 2 = %u\n" , a >> 2) ; 12 13 return 0 ; 14 }  bitowe2.c Programowanie Proceduralne 361  Przykład a = 5 00000000000000000000000000000101 a 1 = 2 00000000000000000000000000000010 a >> 2 = 1 00000000000000000000000000000001 Programowanie Proceduralne 362  Maski bitowe Maska bitowa: słowo (wartość) używane w operacjach bitowych do ustawienia, zmiany lub odczytu poszczególnych bitów. Ustawienie pojedyńczego bitu na 1 operatorem OR 10011101 10010101 | 00001000 00001000 = 10011101 10011101 int zapal_bit ( int x , int n ) { return x | 1 c ) ? b : c ; Wartość absolutna: a = ( a a = student. nazwisko ; b = wskaznik =>nazwisko Programowanie Proceduralne 374  Priorytety i kolejność operatorów Priorytet operatora decyduje o kolejności wykonywania operacji, np. mnożenie przed dodawaniem. a = 3; x = a + a * a; Łączność operatora (lewostronna lub prawostronna) decyduje o kolejności wykonywania obliczeń dla operatorów o takim samym priorytecie a = 1; x = a = a = a; Programowanie Proceduralne 375  Operator Łączność () wywołanie funkcji przyrostkowe []. -> () ++ -- lewostronna jednoargumentowe przedrostkowe ! ~ + - * & sizeof() ++ -- () prawostronna rzutowanie * / % lewostronna + - lewostronna priorytet > lewostronna = lewostronna == != lewostronna & lewostronna ^ lewostronna | lewostronna && lewostronna || lewostronna ?: prawostronna = += -= *= /= %= &= |= ^= prawostronna , lewostronna Programowanie Proceduralne 376  Przykład int a , b=1 , c =2; a = =b++ + ++c plik2.txt < przekierowanie strumienia wejściowego > przekierowanie strumienia wyjściowego Potoki ls | wc Strumienie to podstawowy sposób komunikacji miedzy procesami. Unix/Linux: zbiór małych narzędzi o wielkich możliwościach Programowanie Proceduralne 411  Standardowe strumienie Strumienie FILE* dostępne w stdio.h 0 stdin standardowe wejście, domyślnie klawiatura getchar(), scanf(),... 1 stdout standardowe wyjście, domyślnie ekran putchar(), printf(),... 2 stderr standardowe wejście diagnostyczne, domyślnie ekran perror(),... Programowanie Proceduralne 412  Standardowe strumienie z=getchar ( ) ; z=fgetc ( stdin ) ; putchar ( z ) ; fputc ( z , stdout ) ; printf ( "x =% d\n" , x ) ; fprintf ( stdout , "x =% d\n" , x ) ; scanf ( "%f" , &y ) ; fscanf ( stdin , "%f" , &y ) ; gets ( tab ) ; fgets ( tab , n , stdin ) ; Żródło: http: // upload. wikimedia. org/ Programowanie Proceduralne 413  Inne sytuacje wyjątkowe DOS/Windows: konwersja plików tekstowych Nowy wiersz: \r\n ⇐⇒ \n Niepoprawny format danych dla scanf(), fscanf() Wartość zwracana to ilość wczytanych elementów. if ( scanf ( "%d" , &x ) > 0 ) { / * OK * / } Ostrożnie z mieszaniem odczytu formatowanego z nieformatowanym scanf ( "%d" , &x ) ; getchar ( ) ; / * w c z y t a co z o s t a w i l s c a n f ( ) * / Jednoczesny zapis i odczyt może wymagać dodatkowych zabiegów (np. czyszczenie bufora) W Unix/Linux wielkość liter w ścieżkach ma znaczenie plik.txt PLIK.TXT Plik.txt Plik.TXT W razie niepewności zajrzyj do dokumentacji Programowanie Proceduralne 414  Literatura dodatkowa Wikipedia:  Plik,  List of file signatures,  File format.  System plików,  List of file systems,  Comparison of file systems,  Standardowe strumienie The GNU C Library:  Input/Output Overview,  Input/Output on Streams Programowanie Proceduralne 415