Programowanie - Wykład nr I 2024 PDF

UNIWERSYTET KOMISJI EDUKACJI NARODOWEJ w Krakowie Instytut Bezpieczeństwa i Informatyki PROGRAMOWANIE wykład nr I 2024 Algorytmika Algorytmika (dział informatyki) ”nauka” o algorytmach i ich własnościach1. Nieformalnie algorytm jest pew...

UNIWERSYTET KOMISJI EDUKACJI NARODOWEJ w Krakowie Instytut Bezpieczeństwa i Informatyki PROGRAMOWANIE wykład nr I 2024 Algorytmika Algorytmika (dział informatyki) ”nauka” o algorytmach i ich własnościach1. Nieformalnie algorytm jest pewną ściśle określoną procedurą obliczeniową, która dla właści- wych danych wejściowych wytwarza żądane dane wyjściowe - wynik działania algorytmu2. Algorytm to skończony ciąg jasno zdefiniowanych czynności przekształcających dane wejściowe w dane wyjściowe. Inaczej, algorytm to środek umożliwiający rozwiązanie danego problemu obliczeniowego. Postawienie problemu (specyfikacja problemu/zadania) polega na sprecyzowaniu wymagań dotyczących relacji między danymi wejściowymi, a wyjściowymi, algorytm natomiast opisuje właściwą procedurę obliczeniową, która zapewnia, że ta relacja zostanie osiągnięta. Egzemplarz problemu to pewien zbiór danych wejściowych (spełniający warunki podane w opisie problemu) potrzebnych do obliczania rozwiązania problemu. 1 Y. Feldman, D.Harel, Rzecz o istocie informatyki algorytmika, WNT, 2008. 2 T. Cormen, C. Leiserson, R. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012. 1 Algorytmika - od problemu do rozwiązania PROBLEM algorytm język programowania program DANE wykonanie programu WYNIKI 2 Algorytmika Podstawowe techniki budowania algorytmów: sekwencja (bezpośrednie następstwo, liniowość); wybór (decyzja); powtarzanie - iteracja. Sposoby zapisu algorytmów opis słowny; lista kroków; schemat blokowy; pseudojęzyk; język programowania. 3 Język programowania Język programowania to sformalizowany język służący do zapisu algorytmów. Jest to ”sztucz- ny” język utworzony w oparciu o przyjęte definicje, opisujące alfabet i zbiór słów tego języka, zasady składni (syntaktyka) oraz jednoznacznych reguł wyznaczających znaczenie poszczegól- nych napisów (semantyka). Postać programu wyrażona w języku programowania określana jest kod źródłowy. 4 Klasy języków programowania Języki programowania możemy podzielić ze względu na poziom zbliżenia ich budowy do dzia- łania sprzętu: Języki niskopoziomowe (symboliczne, zorientowane maszynowo, języki asemblera). Języki programowania, w którym jedna instrukcja odpowiada jednej (najwyżej kilku) operacjom maszyny (rozkazom procesora). Kody operacji w języku zastąpione tzw. mnemonikami. Języki takie są ściśle powiązane z architekturą procesora. Języki wysokiego poziomu (uniwersalne, abstrakcyjne). Języki w których jednej instrukcji odpowiada wiele operacji maszynowych. 5 Język wysokiego poziomu vs język niskopoziomowy Przykład: Program zapisujący tekst "Adam" do pliku napisany w języku C: #include int main() { x FILE * my file; x my file = fopen("test.txt","w"); x fprintf(my file, "Adam\n"); x fclose(my file); x return 0; } 6 Język wysokiego poziomu vs język niskopoziomowy Przykład: Program zapisujący tekst "Adam" do pliku napisany w języku C++: #include #include using namespace std; int main() { x ofstream myfile; x my file.open("test.txt"); x my file dołączenie innego pliku int main ( void ) nagłówek funkcji { początek funkcji (bloku) printf ( " Hello world ! " ) ; instrukcja drukowania na ekranie return 0; instrukcja wyjścia z funkcji } koniec funkcji (bloku) // koniec programu treść komentarza jednowierszowego PRZYKŁAD 1 20 Dane w języku C Programy działają w oparciu o dane takie jak np. liczby i znaki. W tym celu program korzysta ze zmiennych i stałych: zmienne – program wykorzystuje do przechowywania danych, które się zmieniają w trakcie wykonywania programu; stałe – dane, które nie zmieniają się w trakcie działania programu. 21 Deklaracje (definicje) zmiennych Ogólna postać deklaracji zmiennej: typ nazwa zmiennej; typ - typ zmiennej deklarowanej, określa rodzaj danych, które może przechowywać zmienna; nazwa zmiennej – ciąg znaków określający nazwę zmiennej (jej identyfikator), służy do ustalenia tożsamości zmiennej ; 22 Podstawowe typy danych w języku C Typy całkowite: char int long Typy zmiennoprzecinkowe: float double 23 Instrukcja przypisania Instrukcja przypisania: zmienna = wyrażenie; x = 8; y = x; y = y + 1; y = x * 3; 24 Deklaracje (definicje) zmiennych Przykłady deklaracji zmiennych typu int w języku C: int x ; // deklaracja definicyjna zmiennej int y = 143; // deklaracja def. i inicjalizacja zmiennej x y... 143 Deklaracja definicyjna rezerwuje pamięć dla zmiennej (o rozmiarze zgodnym z reprezen- tacją) oraz nadaje jej nazwę (identyfikator). Deklaracja zmiennej może zawierać oprócz samej deklaracji, także inicjalizację zmiennej, tj. nadanie zmiennej wartości początkowej. 25  Deklaracje (definicje) zmiennych Przykłady deklaracji zmiennych w języku C: deklaracja zmiennej całkowitej (int) o nazwie nazwie a: int a ; deklaracja zmiennej zmiennoprzecinkowej (float) zainicjowanej wartością 0: float x = 0.0 f ; deklaracja trzech zmiennych całkowitych typu int, zmienna c jest inicjowana wartością 1: int a , b , c = 1; deklaracja stałej Pi typu double6 const double Pi = 3.141592; 6 Stała zadeklarowana przy pomocy modyfikatora const jest realizowana jako fizyczna komórka w pamięci o pewnym adresie, która jest tylko do odczytu i do której można się odwołać używając wskaźnika. 26 Uwagi o nazewnictwie w języku C Nadając nazwę trzymamy się następujących reguł: nazwa zmiennej może składać się tylko z liter alfabetu angielskiego, cyfr i znaku pod- kreślenia; język C rozróżnia wielkość liter nazwy: np. name, Name, NAME, naMe są czterema różnymi nazwami zmiennych; nazwa zmiennej nie może zaczynać się od cyfry np.: tax2 - OK!, 2tax - ŹLE!; nazwa nie może być słowem kluczowym języka programowania np. auto - ŹLE!; nazwa zmiennej powinna kojarzyć się z przeznaczeniem tej zmiennej (idea samodoku- mentującego się kodu źródłowego); 27  Słowa kluczowe języka C auto extern short while break float signed Alignas case for sizeof Alignof char goto static Atomic const if struct Bool continue inline switch Complex default int typedef Generic do long union Imaginary double register unsigned Noreturn else restrict void Static assert enum return volatile Thread local 28 Uwagi o nazewnictwie w języku C Przykład: Pytanie: Które z poniższych identyfikatorów są poprawne w języku C? 1. name12 2. name surname 3. number of days 4. usd$ 5. 44cats 6. C++ 7. file-name 8. typedef 29 Podstawowa obsługa wejścia/wyjścia Funkcja printf() jest jedną z funkcji obsługujących standardowe wyjście. Funkcja printf() służy do wypisywania danych do standardowego wyjścia (bp. ekran monitora). Obsługuje różne formaty wyprowadzania danych: printf ( ł a ń cuch steruj ą cy , w1 , w2 , w3 ,...) ; Parametry funkcji printf(): łańcuch sterujący - składowe łańcucha sterującego to tekst (przeznaczony do wy- świetlenia) oraz specyfikatory formatu (konwersji)- ciągi znaków określających sposób wyświetlania elementów w1, w2, w3,.... ; w1, w2, w3,.... - elementy wyświetlane, mogą być to zmienne, stałe lub wyrażenia. 30 Obsługa standardowego wyjścia - funkcja printf() Wybrane specyfikatory formatu dla funkcji printf(): Specyfikator formatu Dane wyjściowe %c pojedynczy znak %d, %i liczba całkowita dziesiętna (ze znakiem) %u liczba całkowita dziesiętna (bez znaku) %o liczba całkowita w systemie ósemkowym (oktalnym) %x, %X liczba całkowita szesnastkowa (małe/wielkie litery ) %s ciąg znaków %f liczba zmiennoprzecinkowa w zapisie dziesiętnym %e, %E liczba zmiennoprzecinkowa w notacji naukowej PRZYKŁAD 2 31 Podstawowa obsługa wejścia/wyjścia Funkcja scanf() jest jedną z funkcji obsługujących standardowe wejścia. Funkcja scanf() służy do wczytywania danych ze standardowego wejścia (np. klawiatura). Obsługuje różne formaty wprowadzania danych. scanf ( ł a ń cuch steruj ą cy , w1 , w2 , w3 ,...) ; Parametry funkcji scanf(): łańcuch sterujący – ciąg znaków określający format danych składowe łańcucha ste- rującego: tekst, specyfikatory formatu (konwersji); w1, w2, w3,.... – elementy wczytywane, adresy zmiennych. 32 Obsługa standardowego wejścia - funkcja scanf() Wybrane specyfikatory formatu dla funkcji scanf(): Specyfikator formatu Dane wejściowe %c interpretuje jako pojedynczy znak %d, %i, %u interpretuje jako liczbę całkowitą %e, %f, %g, %E, %F, %G interpretuje jako liczbę zmiennoprzecinkową (float) %s linterpretuje jako ciąg znaków rozpoczynający się pierwszym zna- kiem drukowanym i kończący się znakiem drukowanym PRZYKŁAD 3 33 Pytania 1. Jakie operacje wykonuje kompilator? 2. Co to jest interpreter? Czym różni się wykonanie programu w przypadku, gdy jest on kompilowany oraz gdy jest on interpretowany? 3. Jakie są zadania linkera i jak przebiega tworzenie kodu wykonywalnego? 4. Jakie są podstawowe typy danych w języku C? Podać przykłady deklaracji zmiennych i ich inicjowania. 5. Co to jest identyfikator? Podać przykłady ciągu znaków, który jest identyfikatorem oraz ciągu znaków, który identyfikatorem nie jest. 6. Napisać deklarację zmiennej zadanego typu. 34 Pytania 7. Jak za pomocą funkcji printf() wyświetlić na ekranie wartość typu int, unsigned i float. Jak, korzystając z funkcji scanf() odczytać wartości tych typów wpisane za po- mocą klawiatury? 35 UNIWERSYTET KOMISJI EDUKACJI NARODOWEJ w Krakowie Instytut Bezpieczeństwa i Informatyki PROGRAMOWANIE wykład nr II 2024 Instrukcje sterujące i ich schematy blokowe Schemat blokowy (ang. flowchart) - jest narzędziem wykorzystywanym do prezentacji kolej- nych czynności w projektowanym algorytmie czyli graficzną prezentacją algorytmu. Schemat blokowy jest zbudowany z tzw. skrzynek (bloków ) oraz połączeń między nimi. Schemat blokowy przedstawia zbiór instrukcji (operacji, akcji) oraz wzajemnych powiązań między nimi, które określają kolejność wykonywania tych instrukcji. 1 Składowe schematów blokowych skrzynki graniczne START STOP skrzynka operacyjna instrukcja 2 Składowe schematów blokowych skrzynka warunkowa NIE TAK warunek Skrzynka wejścia/wyjścia WY/WE 3 Schemat blokowy - przykład Przykład: Pytanie: Który zestaw danych wejściowych spowoduje, że algorytm przedstawiony na sche- macie nie zakończy się na bloku końcowym (STOP)? START WE: x, y a) x = 10, y = -10 b) x = -10, y = -10 NIE (x + y) >= 0 c) x = 100, y = -1 NIE TAK TAK (x / y) = 1 d) x = 10, y = 10 NIE TAK (x · y) = 100 STOP 4 Instrukcje instrukcja warunkowa prosta: if (warunek). instrukcja; Przykład: x=7; if (x < 0). printf("Liczba ujemna"); 5 Schematy blokowe instrukcji instrukcja warunkowa prosta NIE (==0) TAK (!=0) warunek if (warunek). instrukcja; instrukcja 6 Schematy blokowe instrukcji Przykład: Pytanie: Jaką wartość będzie miała zmienna x? i = 44 k = 33 i = 44; k = 33; NIE TAK if (i > k) i > k. x = k; x = k 7 Instrukcje instrukcja warunkowa z alternatywą: if (warunek). instrukcja 1; else. instrukcja 2; Przykład: x=-9; if (x < 0). printf("Liczba jest ujemna"); else. printf("Liczba jest nieujemna"); 8 Schematy blokowe instrukcji instrukcja warunkowa z alternatywą NIE (==0) TAK (!=0) if (warunek) warunek. instrukcja 1; else instrukcja 2 instrukcja 1. instrukcja 2; 9 Schematy blokowe instrukcji Przykład: Pytanie: Jaką wartość będzie miała zmienna x? i = 55 i = 55; k = 22 k = 22; if (i < k) NIE TAK. x = k; i < k else. x = i; x = i x = k 10 Instrukcje instrukcja złożona (blokowa): {. instrukcja 1;. instrukcja 2;.... } Przykład: y=-6; x=3; if (x * y < 0) {. total = x + y;. printf("Suma x i y wynosi: %d",total); } 11 Instrukcje instrukcja pętli z warunkiem wejścia - while: while (warunek). instrukcja; Przykład: k = 1; while (k