ANSI C

Celem zajęć jest nauka programowania strukturalnego w języku ANSI C.

Literatura

Literatura papierowa:

  • B.W.Kernighan, D.M.Ritchie: Język ANSI C. WNT, Warszawa 1994.
  • S.Oualline: Język C. Programowanie. Wydawnictwo Helion, Gliwice 2003.

Literatura elektroniczna:

Terminarz
  • wykład: środa 16-18 s.25 (M.Piotrów)
  • laboratorium: (P.Rzechonek)
    czwartek 14-16 s.110
    czwartek 18-20 s.108

powrót na początek strony


Ogłoszenia

11.02.2010
Połowa osób ma już wpisane oceny z ćwiczeń. Pozostałe osoby muszą mi dostarczyć indeks, najlepiej w najbliższy poniedziałek. Gdyby komuś nie udało się zastać mnie w biurze (pok.339), to nie powinien o sobie myśleć "pechowiec", tylko zostawić indeks na półce koło portierni.
Są jeszcze osoby, które do tej pory nie zaprezentowały swojego projektu. To poważniejszy przypadek, a nawet wykroczenie! Te osoby powinny niezwłocznie się ze mną skontaktować i umówić na prezentację (można przyjśc bez zapowiedzi w godzinach konsultacji, które są obwieszczone na mojej stronie głównej). Proszę się pospieszyć, bo sesja już się kończy...
10.02.2010
Jeśli komuś brakuje kilku punktów do lepszej (o połowę) oceny, to można zgłosić się po dodatkowe indywidualne zadanie do zaprogramowania (zrobione na miejscu za 20 punktów, w domu za 10).
9.02.2010
Po chorowitym ubiegłym tygodniu wracam do pracy. Będę dostępny dla studentów pragnących oddać poprawione projekty w tym tygodniu w dniach wtorek-czwartek w godzinach przedpołudniowych.
Co do ocen - uzupełniony ranking ukaże się jeszcze dziś. Może się tak zdarzyć, że zostaną w nim pominięte punty z zadań domowych wysłanych do mnie na maila (zamiast umieszczonych na stronie kno.ii.uni.wroc.pl), dlatego proszę to uważnie sprawdzić.
1.02.2010
Trochę się rozchorowałem, więc w tym tygodniu (1-5 lutego) nie będzie mnie w pracy. Pojawię się na chwilę we czwartek, ale w pełni sił będę dostępny dopiero w następnym tygodniu.
18.01.2010
Procedura oddawania zadań projektowych jest następująca: najpierw prezentacja zadania, potem ewentualne poprawki i uzupełnienia i znowu prezentacja, a na końcu wysyłacie mi mailem gotowy program.
7.01.2010
Dzisiejsze zajęcia (7 stycznia 2010) będą miały charakter konsultacyjny. Z powodów organizacyjno-administracyjnych zostaną one przesunięte o 1 godzinę: pierwsza grupa rozpocznie godzinę poźniej, czyli o 15:15, a druga grupa o godzine wcześniej, czyli o 17:15.
2.11.2009
Najbliższe czwartkowe (5 listopada 2009) zajęcia laboratoryjne nie odbędą się z powodu organizowanych przez nasz Instytut zawodów programistycznych CEPC'09.
14.10.2009
Uwaga, zmieniły się zasady punktowania zadań na pracowni. Szczegóły podane zostaną na wykładzie, a ja zmienię je na tej stronie w najbliższym czasie. Podstawowy cel ćwiczeń nie uległ jednak żadnym zmianom - studenci rozwiązują zadania na pracowni a ja je oceniam; kto nie zdąży będzie mógł je dokończyć w domu za połowę punktów; dochodzą zadania domowe. Powodzenia!
8.10.2009
Zmieniłem nieznacznie punktację zadań na pierwszej liście.
23.09.2009
Na pierwszych zajęciach nie będzie listy zadań do zaprogramowania. Będziemy się zapoznawać ze zintegrowanym środowiskiem do programowania w języku C (edycja, kompilacja, uruchamianie i poprawianie programów). Na zajęciach tych będzie można dostać dodatkowe punkty za aktywność!
23.09.2009
Tutaj będą umieszczene informacje dotyczące organizacji zajęć w moich grupach. Proszę zaglądać do ogłoszń co najmniej raz w tygodniu przed laboratorium.

powrót na początek strony


Laboratorium

Zasady zaliczania przedmiotu
Ogólnie:
Ćwiczenia laboratoryjne będą podzielone na dwie części: zadaniową i projektową. Część zadaniowa będzie obejmować 10 pierwszych ćwiczeń a projektowa 5 ostatnich.
Laboratorium na części zadaniowej będzie przebiegać według następującego scenariusza. Tuż przed ćwiczeniami pojawi się w internecie (na tej stronie) lista z zadaniami laboratoryjnymi, którą należy rozwiązać w czasie trwania zajęć; za poprawne i samodzielne rozwiązanie tych zadań będzie można otrzymać do 5 punktów. Kto nie zdąży zrobić zadań na ćwiczeniach może dokończyć je w domu i zaprezentować na początku następnych zajęć; za zadania zrobione w domu będzie można otrzymać maksymalnie połowę punktów.
Część projektowa będzie polegać na zrealizowaniu jednego większego zadania, obejmującego cały przerobiony na części laboratoryjnej materiał. Za samodzielne i poprawne napisznie programu na tej części będzie można dostać do 25 punktów.
Prezentacje:
Zadania można prezentować tylko w czasie trwania pracowni. W trakcie prezentacji programu trzeba się liczyć z pytamiami dotyczącymi zadania: metoda rozwiązania, zastosowane konstrukcje językowe, itp.
Obecności:
Zadania do zaprogramowania będą ogłaszane w internecie tuż przed zajęciami, dlatego obecność na ćwiczeniach jest obowiązkowa. Kto nie zdąży zrobić wszystkich zadań, może zrobić je w domu i oddać tydzień później na następnych zajęciach, ale tylko za połowę punktów.
Oceny:
Ocena końcowa będzie zależeć od zdobytych w semestrze punktów. Maksymalnie będzie można zdobyć 100 punktów: 50 z części zadaniowej, 25 z części projektowej i 25 z kolokwium (kolokwium zorganizuje wykładowca pod koniec semestru). Aby zaliczyć laboratorium na ocenę dostateczną trzeba będzie uzyskać 50 punktów; na ocenę bardzo dobrą trzeba będzie uzyskać 90 punktów; oceny pośrednie pozostają w liniowej zależności od przedstawionych wymagań granicznych. Warunkiem koniecznym uzyskania zaliczenia jest aktywna obecność na co najmniej połowie ćwiczeń laboratoryjnych i zaprogramowanie zadania projektowego.
Laboratorium 0

Zapoznanie się ze środowiskiem zintergowanym do programowania w języku ANSI C

Wpisz się na listę obecności (imię, nazwisko i nr indeksu). Lista obecności będzie na każdych zajęciach. Kto ma niewyraźne pismo powinien pisać DUŻYMI LITERAMI. Potem wysłuchaj uważnie wszystkich informacji organizacyjnych na temat zajęć laboratoryjnych z kursu języka ANSI C. Jeśli coś będzie niezrozumiałe poproś o wyjaśnienie. Następnie zaloguj się na swoje konto w sieci instytutowej i zaprogramuj zadanie umieszczone poniżej. Gdybyś miał kłopoty z logowaniem poproś o pomoc administratora systemu.

Laboratorium 0 - czwartek 14:15 i 18:15,

    zadanie laboratoryjne

  1. (10 pkt.)
    Napisz program powitalny w języku ANSI C, skompiluj go i uruchom w środowisku Bloodshed Dev C++ albo Code Blocks. Program ma wypisać na standardowym wyjściu komunikat zachęcający do nauki języka C, na przykład "Witaj na kursie ANSI C".
Laboratorium 1

Formatowane wejście/wyjście + instrukcje warunkowe

W poniższych programach dane należy wczytywać ze standardowego wejścia za pomocą funkcji scanf(). Wyniki należy wypisywać na standardowym wyjściu za pomocą funkcji printf(). Po wczytaniu każdej liczby sprawdź, czy operacja czytania powiodła się.

Laboratorium 1 - czwartek 14:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który wczyta trzy liczby całkowite a, b i c i wypisze wartość środkową co do wielkości.
  2. (10 pkt.)
    Napisz program, który wczyta trzy dodatnie liczby rzeczywiste a, b i c będące długościami boków trójkąta, a następnie wyliczy i wypisze powierzchnię tego trójkąta z dokładnością do 3 miejsc po kropce dziesiętnej.
    Uwaga! Skorzystaj ze wzoru Herona.
  3. (10 pkt.)
    Napisz program, który wczytuje liczbę rzeczywistą oznaczającą prędkość pojazdu liczoną w [km/h]. Oblicz i wypisz, ile wynosi ta prędkość liczona w [mi/h] i [m/s].
    Uwaga! 1[km]=0.621371[mi]. W swoim programie zdefiniuj odpowiednią stałą symboliczną o wartości 0.621371 za pomocą dyrektywy #define i wykorzystaj ją do obliczeń.
  4. zadanie domowe

  5. (15 pkt.)
    Dany jest układ równań liniowych postaci  ax+by = c  oraz  dx+ey = f . Napisz program, który wczyta sześć liczb rzeczywistych a, b, c, d, e i f będących parametrami tego układu równań, a następnie wyliczy i wypisze jego rozwiązanie (o ile istnieje) z dokładnością do 6 miejsc po kropce dziesiętnej.

Laboratorium 1 - czwartek 18:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który wczyta dwie liczby całkowite a i b i wypisze ich sumę, różnicę, iloczyn, iloraz oraz resztę z dzielenia. Pamiętaj, że nie dzielimy przez zero. Jeżeli użytkownik poda wartotość 0 jako drugą liczbę, program nie powinien wyliczać ani ilorazu ani reszty.
  2. (10 pkt.)
    Napisz program, który wczyta dwie dodatnie liczby rzeczywiste a i b będące długościami boków przyprostokątnych w trójkącie prostokątnym, a następnie wyliczy i wypisze długość boku przeciwprostokątnego w tym trójkącie z dokładnością do 3 miejsc po kropce dziesiętnej.
  3. (10 pkt.)
    Napisz program, który wczytuje liczbę rzeczywistą oznaczającą odległość pomiędzy dwoma punktami liczoną w metrach. Oblicz i wypisz, ile wynosi ta odległość liczona w calach i stopach.
    Uwaga! 1[in]=25.3995[mm] oraz 1[ft]=12[in]. W swoim programie zdefiniuj odpowiednie stałe symboliczne o wartościach 0.0253995 i 0.304794 za pomocą dyrektyw #define i wykorzystaj je do bliczeń.
  4. zadanie domowe

  5. (15 pkt.)
    Dane jest równanie kwadratowe postaci  ax2+bx+c = 0 . Napisz program, który wczyta trzy liczby rzeczywiste a≠0 oraz b i c będące parametrami tego równania, a następnie wyliczy i wypisze jego rozwiązania rzeczywiste z dokładnością do 6 miejsc po kropce dziesiętnej.
Laboratorium 2

Formatowane wejście/wyjście + instrukcje pętli

Programy powinny wypisywać na standardowe wyjście dla błędów komunikaty informujące użytkownika o tym, kiedy progam oczekuje na wprowadzenie danych. Po wczytaniu każdej liczby sprawdź, czy operacja czytania powiodła się.

Laboratorium 2 - czwartek 14:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który wczyta liczbę naturalną n a potem wydrukuje na standardowym wyjściu używając znaku * (gwiazdka) romb o wysokości n. Na przykład dla n=5 na ekranie powinna się pokazać następująca figura:
            * * * * *
          *       *
        *       *
      *       *
    * * * * *
  2. (10 pkt.)
    Napisz program, który wypisze w słupku kolejne potęgi 2 zaczynając od 20 a kończąc na 2-15. Kropki dziesiętne mają się znajdować w tej samej kolumnie dla wszystkich wypisywanych liczb. Nie wolno wypisywać nieznaczących zer pojawiających się na końcu liczby.
  3. (10 pkt.)
    Napisz program, który wczyta liczbę całkowitą x i sprawdzi czy liczba ta jest pierwsza; jeśli nie jest, to wypisz na standardowe wyjście jej podzielnik >1 (dla liczb ≤1 wypisz 0).
    Uwaga! Liczba pierwsza p to liczba naturalna większa od 1, która ma tylko dwa dzielniki naturalne: 1 i p. Jeśli liczba naturalna jest większa od 1 i nie jest pierwsza, to nazywamy ją liczbą złożoną. Oto kilka początkowych liczb pierwszych: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
  4. zadanie domowe

  5. (15 pkt.)
    Napisz program, który wydrukuje w estetyczny sposób tabelę z kodami dla znaków ASCII (należy wypisać kod znaku w postaci dziesiętnej i szestnaskowej a potem sam znak). Program powinien wydrukować tabelę tylko dla znaków o kodach od 32 do 126 (19 wierszy po 5 znaków). Znaki należy wydrukować w taki sposób, aby kolejność ich kodów była uporządkowana kolumnami.
    Uwaga! Można założyć że szerokość konsoli to 80 znaków.

Laboratorium 2 - czwartek 18:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który wczyta liczbę naturalną n a potem wydrukuje na standardowym wyjściu używając znaku * (gwiazdka) trójkąt równoramienny o wysokości n. Na przykład dla n=5 na ekranie powinna się pokazać następująca figura:
            *
          *   *
        *       *
      *           *
    * * * * * * * * *
  2. (10 pkt.)
    Napisz program, który wypisze w słupku kolejne potęgi 2 zaczynając od 20 a kończąc na 250. Cyfry jedności mają się znajdować w tej samej kolumnie dla wszystkich wypisywanych liczb.
  3. (10 pkt.)
    Napisz program, który wczyta dwie liczby całkowite x i y i sprawdzi czy są one względnie pierwsze; jeśli nie są, to wypisz na standardowe wyjście ich podzielnik >1.
    Uwaga! Dwie liczby są względnie pierwsze, jeśli ich największy wspólny dzielnik jest równy 1. Do wyliczenia NWD(x,y) wykorzystaj algorytm Euklidesa.
  4. zadanie domowe

  5. (15 pkt.)
    Napisz program, który wydrukuje w estetyczny sposób tabelę z kodami dla znaków ASCII (należy wypisać kod znaku w postaci dziesiętnej i szestnaskowej a potem sam znak). Program powinien wydrukować tabelę tylko dla znaków o kodach od 32 do 126 (19 wierszy po 5 znaków). Znaki należy wydrukować w taki sposób, aby kolejność ich kodów była uporządkowana kolumnami.
    Uwaga! Można założyć że szerokość konsoli to 80 znaków.
Laboratorium 3

Funkcje i rekurencja. Pliki nagłówkowe i źródłowe.

Każdy program podziel na pliki nagłówkowe i źródłowe. Funkcje, które będziesz definiował nie powinny korzystać z żadnych funkcji z biblioteki standardowej. Zabezpiecz swoje programy przed podaniem nieprawidłowych danych.

Laboratorium 3 - czwartek 14:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który wczyta liczbę naturalną n, potem n liczb rzeczywistych (umieszczając je w automatycznie utworzonej tablicy) a na koniec wyznaczy i wypisze wartość minimalną, maksymalną i średnią arytmetyczną spośród tych liczb. Do wyliczenia średniej oraz wyznaczenia minimum i maksimum zdefiniuj osobne funkcje.
  2. (10 pkt.)
    Napisz program, który wczyta dwie liczby naturalne n i k a następnie wyliczy i wypisze wartość symbolu Newtona (nk). Do wyliczenia symbolu Newtona zdefiniuj funkcję rekurencyjną zgodnie z wzorem:
    (n0) = (nn) = 1 dla n≥0
    (nk) = (n-1k-1) + (n-1k) dla 0<k<n
  3. (10 pkt.)
    Napisz program, który wczyta dwie liczby naturalne p i r a następnie wyliczy i wypisze wartość pr. Do wyliczenia pr zdefiniuj osobną funkcję rekurencyjną, implementującą algorytm szybkiego potęgowania.
  4. zadanie domowe

  5. (15 pkt.)
    Napisz program, który będzie sortował nieuporządkowany ciąg liczb umieszczonych w tablicy. Twój program najpierw powinien wczytać dane: liczbę naturalną n a potem n liczb całkowitych (umieszczając je w automatycznie utworzonej tablicy). Następnie liczby w tej tablicy należy posortować a na koniec wydrukować zawartość uporządkowanej tablicy. Zdefiniuj osobne funkcje do wczytywania danych, prezentacji wyników oraz do samego sortowania (algorytm sortowania też podziel na małe podprogramy).
    Uwaga! Zaimplementuj algorytm sortowania przez wybieranie ale użyj rekurencji zamiast iteracji.

Laboratorium 3 - czwartek 18:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który wczyta liczbę naturalną n, potem n liczb rzeczywistych (umieszczając je w automatycznie utworzonej tablicy) a na koniec obliczy i wypisze sumę i iloczyn tych liczb. Do wyliczenia sumy i iloczynu zdefiniuj osobne funkcje.
  2. (10 pkt.)
    Napisz program, który wczyta liczbę naturalną n a następnie wyliczy i wypisze wartość n-tego wyrazu w ciągu Fibonacciego Fn. Do wyliczenia n-tego wyrazu ciągu Fibonacciego zdefiniuj funkcję rekurencyjną zgodnie z wzorem:
    F0 = 0
    F1 = 1
    Fn = Fn-1 + Fn-2 dla n≥2
  3. (10 pkt.)
    Napisz program, który wczyta dwie liczby naturalne p i d a następnie wyliczy i wypisze wartość ⌊logp d⌋. Do wyliczenia logarytmu ⌊logp d⌋ zdefiniuj osobną funkcję rekurencyjną.
  4. zadanie domowe

  5. (15 pkt.)
    Napisz program, który będzie sortował nieuporządkowany ciąg liczb umieszczonych w tablicy. Twój program najpierw powinien wczytać dane: liczbę naturalną n a potem n liczb całkowitych (umieszczając je w automatycznie utworzonej tablicy). Następnie liczby w tej tablicy należy posortować a na koniec wydrukować zawartość uporządkowanej tablicy. Zdefiniuj osobne funkcje do wczytywania danych, prezentacji wyników oraz do samego sortowania (algorytm sortowania też podziel na małe podprogramy).
    Uwaga! Zaimplementuj algorytm sortowania przez wybieranie ale użyj rekurencji zamiast iteracji.
Laboratorium 4

Operacje bitowe. Binarna reprezentacja liczb całkowitych.

Wszystkie wartości liczbowe są we współczesnych komputerach pamiętane w postaci dwójkowej, zwanej też postacią binarną (system dwójkowy został wybrany ze względów technologicznych). Liczba całkowita ze znakiem typu int jest zapisywana na 32 bitach (4 bajty), przy czym najbardziej znaczący bit determinuje znak liczby (kodowanie w systemie U2).

W systemie tym występują tylko dwie cyfry: 0 i 1. Gdy liczbę zapiszemy binarnie, to pozycja każdej cyfry jest związana z określoną potęgą 2: ostatnia pozycja to jedności czyli 20 (najmniej znaczący bit), przedostatnia to dwójki czyli 21, przedprzedostatnia to czwórki czyli 22, itd. Niech dana będzie liczba b. Liczbę tą można zapisać za pomocą k cyfr dwójkowych (dla odpowiednio dobranego parametru k):
    b = (bk-1bk-2...b1b0)
Wówczas wartość liczby b można wyznaczyć w następujący sposób:
    b = ∑i=0k-1(bi·2i)
W przypadku gdy liczba b jest typu int, to jej wartość wylicza się następująco:
    b = -b31·231+∑i=030(bi·2i)

Każdy program podziel na pliki nagłówkowe i źródłowe. Funkcje, które będziesz definiował nie powinny korzystać z żadnych funkcji z biblioteki standardowej. Zabezpiecz swoje programy przed podaniem nieprawidłowych danych.

Laboratorium 4 - czwartek 14:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą a następnie wypisze ją na standardowym wyjściu w postaci binarnej (zacznij od wypisania bitu wiodącego w nawiasach a potem pozostałe kończąc na najmniej znaczącym bicie).
    Uwaga! Zdefiniuj funkcję czytajbit(), która odczyta z zadanej liczby wartość zadanego bitu. W funkcji tej zastosuj operator przesunięć bitowych << albo >>. Wykorzystaj tę funkcję w swoim programie.
  2. (10 pkt.)
    Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a następnie wyliczy i wypisze na standardowym wyjściu przez jaką największą potęgę 2 dzieli się ta liczba (co jest równoznaczne z wyliczeniem jak długi jest ciąg zer na końcu tej liczby).
    Uwaga! Zastosuj strategię "dziel i zwyciężaj" do rozwiązania tego zadania.
  3. zadania domowe

  4. (10 pkt.)
    Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą n i odwróci w niej wszystkie bity (najmniej znaczący bit zamieni z najbardziej znaczącym itd).
    Uwaga! Program ma wypisać najpierw pierwotną wartość liczby n w postaci dziesiętnej i dwójkowej (wszystkie bity) a potem w taki sam sposób nową wartość po transformacji.
  5. (15 pkt.)
    Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą n oraz s i przesunie cyklicznie wszystkie bity n o s pozycji w prawo.
    Wskazówka! Gdy przesuwamy liczbę o jedną pozycję w prawo, to bit z pozycji 0 zostanie przeniesiony na pozycję 1, bit z pozycji 1 zostanie przeniesiony na pozycję 2, itd, a bit najbardziej znaczący zostanie przeniesiony na pozycję 0. Gdy s<0 to tak, jakbyśmy ją przesuwali w lewo.
    Uwaga! Program ma wypisać najpierw pierwotną wartość liczby n w postaci dwójkowej (wszystkie bity) a potem w taki sam sposób nową wartość po przesunięciu o s pozycji.
    Uwaga! Zdefiniuj funkcje ustawbit() i zerujbit(), która wpisze do zadanej liczby na zadanej pozycji bit o wartości odpowiednio 1 albo 0. Wykorzystaj te funkcje w swoim programie.

Laboratorium 4 - czwartek 18:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą a następnie wypisze ją na standardowym wyjściu w postaci binarnej (wypisz wszystkie bity tej liczby zaczynając od najbardziej znaczącego).
    Uwaga! Zdefiniuj funkcję czytajbit(), która odczyta z podanej liczby wartość określonego bitu. W funkcji tej zastosuj operator przesunięć bitowych << albo >>. Wykorzystaj tę funkcję w swoim programie.
  2. (10 pkt.)
    Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a następnie wyliczy i wypisze na standardowym wyjściu ile w tej liczbie jest zer/jedynek wiodących (w zależności od znaku liczby).
    Uwaga! Zastosuj strategię "dziel i zwyciężaj" do rozwiązania tego zadania.
  3. zadania domowe

  4. (10 pkt.)
    Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą n i odwróci w niej wszystkie bity (najmniej znaczący bit zamieni z najbardziej znaczącym itd).
    Uwaga! Program ma wypisać najpierw pierwotną wartość liczby n w postaci dziesiętnej i dwójkowej (wszystkie bity) a potem w taki sam sposób nową wartość po transformacji.
  5. (15 pkt.)
    Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą n oraz s i przesunie cyklicznie wszystkie bity n o s pozycji w prawo.
    Wskazówka! Gdy przesuwamy liczbę o jedną pozycję w prawo, to bit z pozycji 0 zostanie przeniesiony na pozycję 1, bit z pozycji 1 zostanie przeniesiony na pozycję 2, itd, a bit najbardziej znaczący zostanie przeniesiony na pozycję 0. Gdy s<0 to tak, jakbyśmy ją przesuwali w lewo.
    Uwaga! Program ma wypisać najpierw pierwotną wartość liczby n w postaci dwójkowej (wszystkie bity) a potem w taki sam sposób nową wartość po przesunięciu o s pozycji.
    Uwaga! Zdefiniuj funkcje ustawbit() i zerujbit(), która wpisze do zadanej liczby na zadanej pozycji bit o wartości odpowiednio 1 albo 0. Wykorzystaj te funkcje w swoim programie.
Laboratorium 5

Operacje logiczne.

Każdy program podziel na pliki nagłówkowe i źródłowe. Funkcje, które będziesz definiował nie powinny korzystać z żadnych funkcji z biblioteki standardowej. Zabezpiecz swoje programy przed podaniem nieprawidłowych danych.

Laboratorium 5 - czwartek 14:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który sprawdzi czy podany rok jest przestępny. Program ma najpierw wczytać ze standardowego wejścia rok (liczbę całkowitą) a następnie wyliczyć i wypisać na standardowym wyjściu informację o przestępności tego roku.
    Uwaga! Do testowania przestępności zdefiniuj osobną funkcję, która zwróci 1 gdy rok jest przestępny albo 0 gdy nie jest przestępny:
        int przestepny (int rok);
  2. (10 pkt.)
    Napisz program, który sprawdzi czy podana data jest prawidłowa w kalendarzu Gregoriańskim. Program ma najpierw wczytać datę (trzy liczby całkowite reprezentujące kolejno dzień, miesiąc i rok) a następnie sprawdzić i wypisać informację o tym, czy podana data jest prawidłowa (miesiąc z zakresu 1...12 oraz dzień z zakresu 1...28/29/30/31 w zależności od miesiąca i roku). Należy wziąć pod uwagę fakt, że kalendarz Gregoriański obowiązuje od 15 października 1582 roku.
    Uwaga! Do sprawdzenia poprawności daty zdefiniuj osobną funkcję, która odpowie wartością 1 gdy data jest poprawna albo wartością 0 w przeciwnym przypadku:
        int poprawna (int dz, int mies, int rok);
    Do obliczeń skorzystaj ze statycznej dwuwymiarowej tablicy dniWMiesiacu[2][13], w której będą zapisane liczby dni w poszczególnych miesiącach - osobno dla lat zwykłych i przestępnych. Do tablicy tej powinieneś się odwoływać w nastepujacy sposób:
        dniWMiesiacu[czyPrzestepny(rok)][mies]
  3. (10 pkt.)
    Napisz program, który wyliczy ile dni upłynęlo od początku roku i ile dni poostało do Sylwestra. Program ma najpierw wczytać datę (trzy liczby całkowite reprezentujące kolejno dzień, miesiąc i rok), potem sprawdzić czy jest ona poprawna a następnie wyliczyć i wypisać informację o tym, który to jest dzień w roku (licząc od 1 stycznia do podanedo dnia włącznie) oraz ile dni pozostało do Sylwestra (od podanego dnia do 31 grudnia).
    Uwaga! Luty ma różną liczbę dni w zależności od roku. Do obliczeń skorzystaj ze statycznej dwuwymiarowej tablicy dniWMiesiacach[2][13], w której będą zapisane liczby dni od początku roku do końca poprzedniego miesiąca - osobno dla lat zwykłych i przestępnych. Do tablicy tej powinieneś się odwoływać w nastepujacy sposób:
        dniWMiesiacach[czyPrzestepny(rok)][mies]
    Do wyliczenia liczby dni jakie upłynęły od początku roku do zadanego dnia zdefiniuj osobne funkcje pomocnicze:
        int od1stycznia (int dz, int mies, int rok);
        int do31grudnia (int dz, int mies, int rok);
  4. zadanie domowe

  5. (15 pkt.)
    Napisz program, który wczytuje dwie daty i wylicza ich różnicę mierzoną w dniach. Program ma najpierw wczytać dwie daty (sześć liczb całkowitych reprezentujących kolejno dzień, miesiąc i rok pierwszej daty oraz dzień, miesiąc i rok drugiej daty) a następnie wyliczyć i wypisać ile dni upłynęło od pierwszej daty do drugiej. Liczba tych dni ma wynieść 0 gdy obie daty są takie same a w przypadku gdy pierwsza data jest późniejsza niż druga program powinien wypisać liczbę ujemną.
    Uwaga! W swoim programie zaimplementuj funkcję wyliczającą ile dni upłynęło od wirtualnej daty 1 stycznia 1 roku:
        int od1roku (int dz, int mies, int rok);
    Funkcja ta powinna wykonywać obliczenia bez używania pętli czy rekurencji (do wyliczenia liczby lat przestępnych od wspomnianej daty granicznej do zadanej wykorzystaj zasadę włączeń i wyłączeń).

Laboratorium 5 - czwartek 18:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który sprawdzi czy podany rok jest przestępny. Program ma najpierw wczytać ze standardowego wejścia rok (liczbę całkowitą) a następnie wyliczyć i wypisać na standardowym wyjściu informację o przestępności tego roku.
    Uwaga! Do testowania przestępności zdefiniuj osobną funkcję, która zwróci 1 gdy rok jest przestępny albo 0 gdy nie jest przestępny:
        int przestepny (int rok);
  2. (10 pkt.)
    Napisz program, który sprawdzi czy podana data jest prawidłowa w kalendarzu Gregoriańskim. Program ma najpierw wczytać datę (trzy liczby całkowite reprezentujące kolejno dzień, miesiąc i rok) a następnie sprawdzić i wypisać informację o tym, czy podana data jest prawidłowa (miesiąc z zakresu 1...12 oraz dzień z zakresu 1...28/29/30/31 w zależności od miesiąca i roku). Należy wziąć pod uwagę fakt, że kalendarz Gregoriański obowiązuje od 15 października 1582 roku.
    Uwaga! Do sprawdzenia poprawności daty zdefiniuj osobną funkcję, która odpowie wartością 1 gdy data jest poprawna albo wartością 0 w przeciwnym przypadku:
        int poprawna (int dz, int mies, int rok);
    Do obliczeń skorzystaj ze statycznej dwuwymiarowej tablicy dniWMiesiacu[2][13], w której będą zapisane liczby dni w poszczególnych miesiącach - osobno dla lat zwykłych i przestępnych. Do tablicy tej powinieneś się odwoływać w nastepujacy sposób:
        dniWMiesiacu[czyPrzestepny(rok)][mies]
  3. (10 pkt.)
    Napisz program, który wczytuje dwie daty i porównuje je ze sobą w kolejności chronologicznej. Program ma najpierw wczytać dwie daty (sześć liczb całkowitych reprezentujących kolejno dzień, miesiąc i rok pierwszej daty oraz dzień, miesiąc i rok drugiej daty), potem sprawdzić czy są one poprawne a następnie porównać je ze sobą i wypisać w kolejności niemalejącej.
    Uwaga! Do porównania dat zdefiniuj osobną funkcję pomocniczą:
        int porownaj (int dz1, int mies1, int rok1, int dz2, int mies2, int rok2);
  4. zadanie domowe

  5. (15 pkt.)
    Napisz program, który wczytuje dwie daty i wylicza ich różnicę mierzoną w dniach. Program ma najpierw wczytać dwie daty (sześć liczb całkowitych reprezentujących kolejno dzień, miesiąc i rok pierwszej daty oraz dzień, miesiąc i rok drugiej daty) a następnie wyliczyć i wypisać ile dni upłynęło od pierwszej daty do drugiej. Liczba tych dni ma wynieść 0 gdy obie daty są takie same a w przypadku gdy pierwsza data jest późniejsza niż druga program powinien wypisać liczbę ujemną.
    Uwaga! W swoim programie zaimplementuj funkcję wyliczającą ile dni upłynęło od wirtualnej daty 1 stycznia 1 roku:
        int od1roku (int dz, int mies, int rok);
    Funkcja ta powinna wykonywać obliczenia bez używania pętli czy rekurencji (do wyliczenia liczby lat przestępnych od wspomnianej daty granicznej do zadanej wykorzystaj zasadę włączeń i wyłączeń).
Laboratorium 6

Struktury, unie, pola bitowe.

Uwzględnij w swoich programach możliwość podania nieprawidłowych danych (jako warunek zakończenia pętli). W każdym programie zdefiniuj w zakresie globalnym nowy typ danych, który jest strukturą lub unią (wykorzystaj instrukcję typedef).

Laboratorium 6 - czwartek 14:15 i 18:15,

    zadania laboratoryjne

  1. (15 pkt.)
    Część A.
    Zdefiniuj unię, która będzie zawierała pole typu int oraz pole będące tablicą znakową char[sizeof(int)]. Następnie napisz krótki program testowy, który w pętli najpierw wczyta liczbę całkowitą typu int zapisując ją w unii a następnie wypisze bitowo zawartość tablicy znakowej w tej unii. Korzystając z tego programu sprawdź, czy liczby na twoim komputerze są zapisywane w systemie little-endian czy big-endian.
    Część B.
    Zdefiniuj unię, która będzie zawierała pole typu double oraz pole będące tablicą znakową char[sizeof(double)]. Następnie napisz krótki program testowy, który w pętli najpierw wczyta liczbę rzeczywistą typu double zapisując ją w unii a następnie wypisze wszystkie bity binarnej reprezentacji tej liczby wykorzystując zawartość tablicy znakowej w tej unii. Programując to zadanie wykorzystaj wiedzę z poprzedniej części.
  2. (10 pkt.)
    Część A.
    Zdefiniuj unię, która będzie zawierała pole bitowe typu unsigned int oraz pole typu float (pole bitowe ma zawierać 3 składniki odpowiadające cesze, mantysie i znakowi zapisanych w liczbie typu float). Następnie napisz krótki program testowy korzystający ze wspomnianej unii, który w pętli najpierw wczyta liczbę rzeczywistą typu float a następnie wypisze w znormalizowanej postaci tę liczbę - będzie to więc iloczyn znaku (liczba +1 albo -1), potęgi 2 do cechy i mantysy (mantysę wypisz w postaci binarnej).
    Liczba rzeczywista typu float w standardzie IEEE-754 ma 23 najmniej znaczące bity przeznaczone na zapamiętanie mantysy, potem jest 8 bitów cechy i 1 najbardziej znaczący bit to znak. Wartość cechy oblicza się w taki sposób, że od odczytanej 8-bitowej wartości z pola cechy odejmujemy 127 (dostaniemy więc liczbę z zakresu od -127 do 128). Mantysa to liczba stałopozycyjna z przedziału [1,2) ale w 23-bitowym polu mantysy pamiętana jest tylko część ułamkowa.
    Część B.
    Zrób to samo co w poprzedniej części ale dla liczb typu double.
  3. zadanie domowe

  4. (20 pkt.)
    Zdefiniuj strukturę z polami bitowymi do zapamiętywania godziny (5 bitów na godziny, 6 bitów na minuty i 6 bitów na sekundy). Napisz też funkcję, która podane wartości typu unsigned int reprezentujące określoną godzinę upakuje do pola bitowego:
        godzina upakuj (int g, int m, int s);
    Potem zdefiniuj strukturę opisująca rozmowę telefoniczną: numer dzwoniącego, numer odbierającego oraz godzina rozpoczęcia i zakończenia rozmowy (skorzystaj ze struktury godzina z polami bitowymi do pamiętania czasu).
        typedef struct { /*...*/ } polaczenie;
    Następnie napisz program, który dla wczyta ze standardowego wejścia liczbę całkowitą n>0 oznaczającą ilość rozmów, potem utworzy automatyczną n-elementową tablicę struktur i wczyta do niej informacje o n rozmowach telefonicznych prowadzonych w pewnym dniu za pośrednictwem jakiejś centrali. Po wczytaniu danych program ma posortować struktury w tablicy ze względu na długość połączeń. Zaimplementuj do tego celu algorytm sortowania przez wybieranie.
        void sortuj_przez_wybor (polaczenie p[], int n);
    Algorytm ten wykorzystuje porównania długości rozmów; zdefiniuj więc funkcję, która oblicza w sekundach czas jaki upłynął od jednej godziny do drugiej:
        int czas (godzina pocz, godzina kon);
    Na koniec program powinien obliczyć i wypisać średnią długość połączenia telefonicznego oraz wypisać pełną informację o najkrótszym i najdłuższym połączeniu.
Laboratorium 7

Grafika - pliki postscriptowe.

Wykorzystaj w swoich programach pliki (autorstwa Tomasza Wierzbickiego i zaktualizowane przeze mnie) źródłowe i nagłówkowe, w których zdefiniowano zbiór prostych funkcji służących do obliczania współrzędnych punktów w~przestrzeni dwu- i trójwymiarowej geometry.h i geometry.c oraz pliki źródłowe i nagłówkowe, w których zdefiniowano kilka funkcji umożliwiających tworzenie prostych plików graficznych w języku Postscript postscript.h i postscript.c. Oto kilka przykładowych programów, które korzystając z funkcji zdefiniowanych w wymienionych plikach tworzą proste rysunki:

Laboratorium 7 - czwartek 14:15 i 18:15,

    zadania laboratoryjne

  1. (10 pkt.)
    Napisz program, który wygenereuje plik postscriptowy z 2-wymiarowym rysunkiem spirali. Wynik działania twojego programu powinien być podobny do takiego rysunku.
  2. (15 pkt.)
    Napisz program, który wygenereuje plik postscriptowy z 3-wymiarowym i kolorowym rysunkiem zębatki. Wynik działania twojego programu powinien być podobny do takiego rysunku.
  3. zadanie domowe

  4. (20 pkt.)
    Napisz program, który wygenereuje plik postscriptowy z kolorowym 3-wymiarowym rysunkiem kostki Mengera. Kostka Mengara jest fraktalem postałym przez drążenie sześcianu wzdłuż wszystkich trzech kierunków i rekurencyjnie poskładanym z mniejszych kostek tego samego typu. Twój rysunek powinien być oczywiście zrobiony kreskami a nie ścianami - będzie więc "przeszklony" w przeciwieństie do tego z przykładu. Rysunek ma być też kolorowy - cała kostka ma być obwiedziona jednolitym kolorem (krawędzie największego sześciamu powinny więc zostać narysowane na samym końcu); kolory dobierz losowo.
    Uwaga! Rysowanie kostki zaprogramuj jako procedurę rekurencyjną. Warunkiem zakończenia rekurencji niech będzie długość boku kostki <10mm.
    Wskazówka! Aby kolory były losowe, zdefiniuj sobie tablicę z 7 kolorami i losowo wybieraj kolor do bieżącego rysowania linii. Posłuż się w tym celu generatorem liczb pseudolosowych z biblioteki stdlib.h (będzie ci też potrzebna biblioteka time.h do inicjalizacji generatora). Na początku programu (w funkcji main() ) zainicjalizuj generator, wywołując jednokrotnie funkcję srand(time(0)). Potem możesz używać funkcji rand() do losowania liczb całkowitych nieujemnych (wyrażenie rand()%7 da w wyniku losową wartość z zakresu 0-6).
Laboratorium 8

Wskaźniki i tablice.

We wszystkich definiowanych przez ciebie funkcjach posługuj się wskaźnikami, przesunięciami wskaźników, porównywaniem wskaźników, ich różnicą, operatorem wyłuskania itp, ale nie wykorzystuj operatora indeksowania o ile to nie jest konieczne!

Laboratorium 8 - czwartek 14:15 i 18:15,

    zadania laboratoryjne

  1. (15 pkt.)
    Zdefiniuj funkcję obliczającą długość ciągu znakowego (liczba znaków w ciągu z pominęciem znaku kończącego '\0') oraz funkcję odwracającą znaki w ciągu (zamiana pierwszego znaku z ostatnim, drugiego z przedostatnim, itd):
        int dlugosc (const char *p);
        void odwroc (char *p);
    Funkcja dlugosc() powinna używać tylko jednego pomocniczego wskaźnika a funkcja odwroc() dwóch wskaźników i jednej zmiennej znakowej. W funkcji odwroc() wykorzystaj funkcję dlugosc() do inicjalizacji drugiego wskaźnika (na początku pierwszy wskaźnik pokazuje na pierwszy znak w ciągu a drugi na ostani znak).
    Następnie zdefiniuj funkcję do kopiowania oraz do porównywania ciągów znakowych:
        int kopiuj (const char *skad, char *dokad);
        int porownaj (const char *jeden, const char *drugi);
    Na koniec wykorzystaj te funkcje do sprawdzenia, czy wczytany ciąg znaków jest palindromem. Twój program powinien najpierw wczytać ze standardowego wejścia linię tekstu (nie dłuższą niż 79 znaków), potem wypisać na standardowe wyjście jego długość, następnie napis odwrócony a na końcu informację o tym czy ten napis jest palindromem.
    Uwaga! Podziel swój program na pliki nagłówkowe i źródłowe.
    Wskazówka! Zakładamy, że długość linii tekstu nie przekroczy 79 znaków. Użyj więc 80-znakowego bufora i funkcji fgets() do wczytania linii ze standardowego wejścia stdin.
  2. (10 pkt.)
    Zdefiniuj funkcję zamieniającą wartości w dwóch komórkach typu int oraz funkcję sortującą dane typu int zapisane w tablicy (zaimplementuj sortowanie przez wstawianie):
        void zamien (int *p, int *q);
        void sortuj (int t[], int n);
    Funkcja zamien() powinna używać tylko jednej zmiennej pomocniczej typu int a funkcja sortuj() tylko dwóch wskaźników.
    Następnie napisz program testujący twoje funkcje, który wczyta ze standardowego wejścia liczby całkowite n>0 i z>1 a następnie utworzy automatyczną n-elementową tablicę liczb typu int, wypełni ją losowymi wartościami z zakresu od -z do z a potem posortuje dane zapisane w tej tablicy. Twój program powinien wypisać zawartość tablicy przed sortowaniem i po tej czynności.
    Wskazówka! Wykorzystaj funkcję rand(), która zwraca losową wartość całkowitą nieujemną (funkcja ta jest zdefiniowana w pliku nagłówkowym stdlib.h). Pamiętaj, aby na początku zainicjalizować generator liczb pseudolosoych wywołując jednokrotnie funkcję srand(time(0)) (funkcja time() jest zdefiniowana w pliku nagłówkowym time.h). Do losowania wartości z podanego zakresu [a,b] napisz własną funkcję (która oczywiście korzysta z funkcji rand()):
        int losuj (int a, int b);
  3. zadanie domowe

  4. (20 pkt.)
    Napisz program, który wczyta dodatnią liczbę całkowite N a potem wylosuje N dat D0, D1, ..., DN-1. Każda data to struktura z trzema polami do zapamiętania dnia, miesiąca i roku (daty mają być prawidłowe - niewcześniejsze niż 15 października 1582 i niepóźniejsze niż data bieżąca). Wszystkie daty należy umieścić w automatycznie utworzonej tablicy. Następnie posortuj te daty chronologicznie używając funkcji qsort() z biblioteki standardowej. Następny krok, to utworzenie automatycznej N-elementowej tablicy ze wskaźnikami do tych dat. Tablicę tych wskaźników należy tak uporządkować, aby wskazywane przez nie daty były posortowane ze względu na dzień w roku. Do posortowania tablicy wskaźników także użyj funkcji qsort(). Na końcu twój program ma wypisać wszystkie zapamiętane daty najpierw uporządkowane chronologicznie a poten ze zwględu na dzień w roku.
    Uwaga: Datę bieżącą możesz odczytać używając funkcji localtime() z biblioteki standardowej.
Laboratorium 9

Zarządzanie pamięcią wolną (stertą).

Programy mają być podzielone na pliki źródłowe i nagłówkowe. Pamiętaj aby na końcu zawsze zwolnić pamięć zaalokowaną na strecie.

Laboratorium 9 - czwartek 14:15,

    zadanie laboratoryjne

  1. (20 pkt.)
    Część A.
    W pliku nagłówkowym zdefiniuj strukturę reprezentującą węzeł uporządkowanej listy dwukierunkowej struct Element, w której będzie pole nast wskazujące na następny element na liście, pole poprz wskazujące na poprzedni element na liście oraz pole wartosc przechowujące pewną wartość typu TYP (nazwę TYP zdefiniuj za pomocą dyrektywy #define):
        struct Element
        {
            struct Element *nast, *poprz;
            TYP wartosc;
       };
    Oprócz struktury zadeklaruj również funkcję wstaw() wstawiającą nowy element do listy w takim miejscu aby zachowany był porządek niemalejący, ile() liczącą ile jest elementów na liście oraz wypisz() wypisującą kolejno wszystkie wartości zapamiętane w liście. Pierwszym argumentem tych funkcji powinien być wskaźnik do wskaźnika na początek listy. W pliku źródłowym napisz definicje tych funkcji (zaimplementuj je iteracyjnie).
    Uwaga! Do drukowania wartości typu TYP zdefiniuj osobną makrodefinicję z parametrem. W podobny sposób rozwiąż problem porównywania - zdefiniuj makrodefinicję z dwoma parametrami typu TYP, która będzie zwracała wartość -1, 0 lub 1 w zależności od tego czy odpowiednio parametr pierwszy będzie mniejszy od drugiego, czy będą równe czy też pierwszy będzie większy od drugiego.
    Część B.
    Napisz program testujący zaprogramowaną przez Ciebie listę. Program ma działać interaktywnie w pętli, czyli realizować wydawane na konsoli polecenia do czasu, aż zostanie wydane polecenie kończące działanie programu.
    Część C.
    Uzupełnij wcześniejszy program o możliwość usunięcia z listy elementu o zadanej wartości funkcją usun_wartosc(), usunięcia z listy elementu umieszczonego na zadanej pozycji funkcją usun_pozycje(), sprawdzenia gdzie w liście znajduje się element o zadanej wartości funkcją szukaj_wartosci() oraz sprawdzenia jaka wartość znajduje się na zadanej pozycji w liście funkcją szukaj_pozycji().
    Uwaga! Zmodyfikuj program testowy, tak aby uzwględniał wymienione funkcje.
  2. zadanie domowe

  3. (25 pkt.)
    Część A.
    Zdefiniuj strukturę reprezentującą węzeł drzewa binarnych poszukiwań BST struct Element, w której będą pola lewe i prawe wskazujące odpowiednio na lewe i prawe poddrzewo zaczepione w danym węźle oraz pole wartosc przechowujące pewną wartość typu TYP (nazwę TYP zdefiniuj za pomocą dyrektywy #define):
        struct Element
        {
            struct Element *lewe, *prawe;
            TYP wartosc;
        };
    Oprócz struktury zadeklaruj i zdefiniuj funkcje wstaw() (wstawienie nowego elementu do drzewa), ile() (policzenie ile jest elementów w drzewie) oraz wypisz() (wypisanie wszystkich wartości zapamiętanych w drzewie w porządku inorder). Pierwszym argumentem tych funkcji powinien być wskaźnik do wskaźnika na korzeń drzewa (lub poddrzewa). Wszystkie wymienione funkcje zaimplementuj rekurencyjnie.
    Uwaga! Do drukowania wartości typu TYP zdefiniuj osobną makrodefinicję z parametrem. W podobny sposób rozwiąż problem porównywania - zdefiniuj makrodefinicję z dwoma parametrami typu TYP, która będzie zwracała wartość -1, 0 lub 1 w zależności od tego czy odpowiednio parametr pierwszy będzie mniejszy od drugiego, czy będą równe czy też pierwszy będzie większy od drugiego.
    Część B.
    Napisz program testujący zaprogramowane przez Ciebie drzewo BST. Program ma działać interaktywnie w pętli, czyli realizować wydawane na konsoli polecenia do czasu, aż zostanie wydane polecenie kończące działanie programu.
    Część C.
    Uzupełnij wcześniejszy program dopisując funkcje usun_min() (usunięcie elementu minimalnego z drzewa), usun_max() (usunięcie elementu maksymalnego z drzewa) i usun() (usunięcie z drzewa elementu o zadanej wartości).
    Uwaga! Zmodyfikuj program testowy tak, aby uzwględniał wymienione funkcje.
    Część D.
    Uzupełnij wcześniejszy program dopisując funkcję drukuj() (wyświetlenie struktury drzewa wraz z wartościami w węzłach). Przykładowe wywołanie tej funkcji w programie testującym może wygenerować następujący wynik dla drzewa BST z wartością 37 w korzeniu:
              + - - * 11
              |     + - - * 13
        + - - * 17
        |     + - - * 23
        * 37
        + - - * 43
              |     + - - * 47
              + - - * 53
                    + - - * 57

    Uwaga! Zmodyfikuj program testowy tak, aby uzwględniał wymienioną funkcję.

Laboratorium 9 - czwartek 18:15,

    zadanie laboratoryjne

  1. (20 pkt.)
    Część A.
    W pliku nagłówkowym zdefiniuj strukturę reprezentującą węzeł nieuporządkowanej listy dwukierunkowej struct Element, w której będzie pole nast wskazujące na następny element na liście, pole poprz wskazujące na poprzedni element na liście oraz pole wartosc przechowujące pewną wartość typu TYP (nazwę TYP zdefiniuj za pomocą dyrektywy #define):
        struct Element
        {
            struct Element *nast, *poprz;
            TYP wartosc;
       };
    Oprócz struktury zadeklaruj również funkcję wstaw() wstawiającą nowy element do listy na zadaną pozycję, wstaw_na_pocz() i wstaw_na_kon() wstawiającą nowy element odpowiednio na początku listy i na jej końcu, ile() liczącą ile jest elementów na liście oraz wypisz() wypisującą kolejno wszystkie wartości zapamiętane w liście. Pierwszym argumentem tych funkcji powinien być wskaźnik do wskaźnika na początek listy. W pliku źródłowym napisz definicje tych funkcji (zaimplementuj je iteracyjnie).
    Uwaga! Do drukowania wartości typu TYP zdefiniuj osobną makrodefinicję z parametrem. W podobny sposób rozwiąż problem porównywania - zdefiniuj makrodefinicję z dwoma parametrami typu TYP, która będzie zwracała wartość 0 lub 1 w zależności od tego czy odpowiednio parametr pierwszy różni się od drugiego czy też oba parametry są równe.
    Część B.
    Napisz program testujący zaprogramowaną przez Ciebie listę. Program ma działać interaktywnie w pętli, czyli realizować wydawane na konsoli polecenia do czasu, aż zostanie wydane polecenie kończące działanie programu.
    Część C.
    Uzupełnij wcześniejszy program o możliwość usunięcia z listy elementów o zadanej wartości funkcją usun_wartosc(), usunięcia z listy elementu umieszczonego na zadanej pozycji funkcją usun_pozycje(), sprawdzenia gdzie w liście znajduje się element o zadanej wartości funkcją szukaj_wartosci() oraz sprawdzenia jaka wartość znajduje się na zadanej pozycji w liście funkcją szukaj_pozycji().
    Uwaga! Zmodyfikuj program testowy tak, aby uzwględniał wymienione funkcje.
  2. zadanie domowe

  3. (25 pkt.)
    Część A.
    Zdefiniuj strukturę reprezentującą węzeł drzewa binarnych poszukiwań BST struct Element, w której będą pola lewe i prawe wskazujące odpowiednio na lewe i prawe poddrzewo zaczepione w danym węźle oraz pole wartosc przechowujące pewną wartość typu TYP (nazwę TYP zdefiniuj za pomocą dyrektywy #define):
        struct Element
        {
            struct Element *lewe, *prawe;
            TYP wartosc;
        };
    Oprócz struktury zadeklaruj i zdefiniuj funkcje wstaw() (wstawienie nowego elementu do drzewa), ile() (policzenie ile jest elementów w drzewie) oraz wypisz() (wypisanie wszystkich wartości zapamiętanych w drzewie w porządku inorder). Pierwszym argumentem tych funkcji powinien być wskaźnik do wskaźnika na korzeń drzewa (lub poddrzewa). Wszystkie wymienione funkcje zaimplementuj rekurencyjnie.
    Uwaga! Do drukowania wartości typu TYP zdefiniuj osobną makrodefinicję z parametrem. W podobny sposób rozwiąż problem porównywania - zdefiniuj makrodefinicję z dwoma parametrami typu TYP, która będzie zwracała wartość -1, 0 lub 1 w zależności od tego czy odpowiednio parametr pierwszy będzie mniejszy od drugiego, czy będą równe czy też pierwszy będzie większy od drugiego.
    Część B.
    Napisz program testujący zaprogramowane przez Ciebie drzewo BST. Program ma działać interaktywnie w pętli, czyli realizować wydawane na konsoli polecenia do czasu, aż zostanie wydane polecenie kończące działanie programu.
    Część C.
    Uzupełnij wcześniejszy program dopisując funkcje usun_min() (usunięcie elementu minimalnego z drzewa), usun_max() (usunięcie elementu maksymalnego z drzewa) i usun() (usunięcie z drzewa elementu o zadanej wartości).
    Uwaga! Zmodyfikuj program testowy tak, aby uzwględniał wymienione funkcje.
    Część D.
    Uzupełnij wcześniejszy program dopisując funkcję drukuj() (wyświetlenie struktury drzewa wraz z wartościami w węzłach). Przykładowe wywołanie tej funkcji w programie testującym może wygenerować następujący wynik dla drzewa BST z wartością 37 w korzeniu:
              + - -(11)
              |     + - -(13)
        + - -(17)
        |     + - -(23)
       (37)
        + - -(43)
              |     + - -(47)
              + - -(53)
                    + - -(57)

    Uwaga! Zmodyfikuj program testowy tak, aby uzwględniał wymienioną funkcję.
Laboratorium 10

Czytanie z i pisanie do pliku.

Programując te zadania zawsze sprwdzaj w programie czy udało się otworzyć plik a na końcu po przeczytaniu/zapisaniu danych zamknij go.

Laboratorium 10 - czwartek 14:15,

    zadanie laboratoryjne

  1. (20 pkt.)
    Część A.
    Napisz program, który wypisze zawartość pliku tekstowego, o ile podany plik istnieje, na standardowym wyjściu. Nazwę pliku przekaż do programu poprzez parametry wywołania. Plik należy napierw otworzyć do czytania, potem przeczytać linia po linii, a na końcu zamknąć. Twój program ma kompresować spójne ciągi białych znaków wewnątrz linii do jednej spacji, obcinać białe znaki na początku i na końcu każdej linii oraz pomijać przy wypisywaniu linie puste.
    Część B.
    Napisz program, który zapisze w pliku tekstowym kolejne liczby z trójkąta Pascala aż do wyczerpania zakresu liczb typu long long:
        P0,0 = 1
        Pn,0 = Pn,n = 1 dla n>0
        Pn,k = Pn-1,k-1 + Pn-1,k dla 0>k>n
    Nazwę pliku przekaż do programu poprzez parametry wywołania. Każdy wiersz trójkąta Pascala zapisz w oddzielnej linii, a poszczególne liczby w obrębie wiersza poodzielaj pojedynczą spacją. Plik należy napierw otworzyć do pisania, potem zapisać w nim wspomniany trójkąt, a na końcu zamknąć.
  2. zadanie domowe

  3. (25 pkt.)
    Część A.
    W tekstowym pliku z danymi jest zapisanych N liczb rzeczywistych a0, a1, ..., aN-1. Zawartość pliku z danymi jest następująca: w pierwszej linii jest zapisana liczba całkowita N≥1 a w kolejnych liniach pooddzielane białymi znakami wartości rzeczywiste a0, a1, ..., aN-1. Należy te liczby najpierw odczytać, zapamiętując je w dynamicznie zaalokowanej tablicy typu double [] a potem zapisać je do pliku binarnego (bez wartości N na początku) i zwolnić przydzieloną wcześniej pamięć. Nazwy plików przekaż poprzez parametry wywołania programu.
    Wskazówka! Wykorzystaj funkcje fscanf() i fwrite().
    Część B.
    W binarnym pliku z danymi jest zapisane są liczby typu double. Określ ile tych liczb jest zapisanych w pliku, zaalokuj tablicę o takim rozmiarze na stercie i wczytaj je tam. Następnie policz i wypisz na standardowym wyjściu średnią arytmetyczną i geometryczną z tych wartości. Na końcu zwolnij przydzieloną pamięć. Nazwę pliku przekaż poprzez parametry wywołania programu.
    Wskazówka! Wykorzystaj funkcję fread().
    Część C.
    Napisz program, który porówna ze sobą zawartości dwóch plików z dokładnością do białych znaków w obrębie linii. Po napotkaniu pierwszej różnicy program powinien wypisać numer wiersza i numer pozycji w wierszu, w którym występuje różnica, po czym przerwać dalsze porównywanie. Nazwy plików przekaż poprzez parametry wywołania programu.
    Uwaga! Sprawdź, czy program wywołano z prawidłową liczbą argumentów oraz czy podane nazwy są nazwami istniejących plików w lokalnym systemie.

Laboratorium 10 - czwartek 18:15,

    zadanie laboratoryjne

  1. (20 pkt.)
    Część A.
    Napisz program, który wypisze zawartość pliku tekstowego, o ile podany plik istnieje, na standardowym wyjściu. Nazwę pliku przekaż do programu poprzez parametry wywołania. Plik należy napierw otworzyć do czytania, potem przeczytać linia po linii, a na końcu zamknąć. Twój program ma przycinać długie linie do 24 znaków (ignorować pozostałe w tej linii znaki) oraz pomijać przy wypisywaniu linie puste.
    Część B.
    Napisz program, który zapisze w pliku tekstowym kolejne liczby ciągu Fibonacciego aż do wyczerpania zakresu liczb typu long long:
        F0 = 0
        F1 = 1
        Fn = Fn-1 + Fn-2 dla n≥2
    Nazwę pliku przekaż do programu poprzez parametry wywołania. Każdą liczbę zapisz w oddzielnej linii. Plik należy napierw otworzyć do pisania, potem zapisać w nim wspomniany ciąg, a na końcu zamknąć.
  2. zadanie domowe

  3. (25 pkt.)
    Część A.
    W tekstowym pliku z danymi jest zapisanych N liczb rzeczywistych a0, a1, ..., aN-1. Zawartość pliku z danymi jest następująca: w pierwszej linii jest zapisana liczba całkowita N≥1 a w kolejnych liniach pooddzielane białymi znakami wartości rzeczywiste a0, a1, ..., aN-1. Należy te liczby najpierw odczytać, zapamiętując je w dynamicznie zaalokowanej tablicy typu double [] a potem zapisać je do pliku binarnego (bez wartości N na początku) i zwolnić przydzieloną wcześniej pamięć. Nazwy plików przekaż poprzez parametry wywołania programu.
    Wskazówka! Wykorzystaj funkcje fscanf() i fwrite().
    Część B.
    W binarnym pliku z danymi jest zapisane są liczby typu double. Określ ile tych liczb jest zapisanych w pliku, zaalokuj tablicę o takim rozmiarze na stercie i wczytaj je tam. Następnie policz i wypisz na standardowym wyjściu średnią arytmetyczną i geometryczną z tych wartości. Na końcu zwolnij przydzieloną pamięć. Nazwę pliku przekaż poprzez parametry wywołania programu.
    Wskazówka! Wykorzystaj funkcję fread().
    Część C.
    Napisz program, który porówna ze sobą zawartości dwóch plików z dokładnością do białych znaków w obrębie linii. Po napotkaniu pierwszej różnicy program powinien wypisać numer wiersza i numer pozycji w wierszu, w którym występuje różnica, po czym przerwać dalsze porównywanie. Nazwy plików przekaż poprzez parametry wywołania programu.
    Uwaga! Sprawdź, czy program wywołano z prawidłową liczbą argumentów oraz czy podane nazwy są nazwami istniejących plików w lokalnym systemie.
Projekt

Tematy zadań projektowych

tautologie w rachunku zdań
Napisz program badający spełnialność, sprzeczność i własność bycia tautologią dowolnej formuły rachunku zdań (bez kwantyfikatorów) ze spójnikami logicznymi: alternatywą (|), koniunkcją (&), negacją (!), implikacją (=>) i równoważnością (<=>). Możesz przyjąć, że zbiór zmiennych zdaniowych jest dowolnym niepustym ciągim liter alfabetu angielskiego. Program może operować na formule w postaci ONP. Zadaniem programu będzie sprawdzenie czy formuła w wylicza się dla każdego wartościowania do wartości true, czy dla każdego wartościowania do wartości false, czy może dla pewnych wartościowań do true a dla innych do false.
wyrażenia ONP
Napisz klakulator dla wyrażeń infiksowych (notacja tradycyjna). Kalkulator ma najpierw przekształcić wyrażenie infiksowe do postfiksowego (Odwrotna Notacja Polska) a potem je wyliczyć i wypisać. Do obliczania wartości wyrażeń ONP wykorzystaj kolejkę i stos zaimplementowane na liście jednokierunkowej. Twój program powinien umożliwiać zapamiętywanie wartości obliczonych wyrażeń za pomoca zmiennych; zbiór zmiennych przechowuj w postaci drzewa BST - elementami tego drzewa będą więc pary nazwa-wartość, gdzie kluczem w takiej parze będzie nazwa zmiennej. Należy sprwdzać poprawność wpisywanych wyrażeń.
maszyna RAM
Maszyna RAM (Random Access Machine) jest abstrakcyjnym modelem obliczeń ze swobodnym dostępem do pamięci. Dokładny opisz tej maszyny (jej budowę, działanie i zestaw rozkazów) można znaleść na stronie http://wm.ite.pl/stud/ram/doc/index.html. Zadanie polaga na napisaniu symulatora maszyny RAM. Symulator ten powinien działać w trybie tekstowym w jednym z dwóch trybów: w tybie krokowym (wykonujemy kolejną instrukcję dopiero po wydaniu stosownego polecenia a w międzyczasie możemy kontrolować stan rejestrów) i w trybie ciągłym (wykonujemy kolejne instrukcje aż do momentu zatrzymania maszyny).
drzewa zrównoważone
Zaimplementuj słownik, czyli taką strukturę danych na której można efektywnie wykonać ciąg instrukcji insert-delete-search, w postaci zrównoważonego drzewa BST. Możesz wybrać jedno z następujących drzew:
  1. drzewo AVL
  2. drzewo czerwono-czarne
  3. drzewo SPLAY zwane też drzewem samoorganizującym się
Na strukturze tej powinieneś wykonywać operacje słownikowe odczytane ze standardowego wejścia. Powinieneś też umieć wydrukować schematycznie strukturę takiego drzewa.
kompresja danych
Napisz program, który będzie umożliwiał kompresję i dekompresję zadanych plików. Możesz wybrać jedną z następujących metod kompresji:
  1. kodowanie Hufmana
  2. LZ77 albo wariant ulepszony LZSS
  3. LZ78 albo wariant ulepszony LZW
Twój program powinien umieć skompresować wiele różnych plików umieszczając je wszystkie w jednym archiwum.
sudoku
Napisz parę programów - jeden, który będzie generował łamigłówkę sudoku i drugi, który będzie ją rozwiązywał. Przy rozwiązywaniu sudoku zastosuj algorytm z nawrotami. Przy generowaniu pamiętaj, że prawidłowa łamigłówka powinna posiadać dokładnie jedno rozwiązanie.
geometria analityczna
Rozważmy przestrzeń 3--wymiarową z kartezjańskim układem współrzędnych. W przestrzeni tej umieszczamy figury takie jak punkty, odcinki, trójkąty i czworościany. Figury te mogą się nawzajem zasłaniać lub przenikać. Zadaniem programu jest wygenerowanie rysunku w formacie PS, który byłby rzutem na pewną ustaloną płaszczyznę wszystkich umieszczonych w przestrzeni figur z uwzględnieniem ich wzajemnego zasłaniania.
inne tematy
Można zgłaszać własne propozycje zadań projektowych. Takie indywidualne projekty muszą być ze mną szczegółowo przedyskutowane i zatwierdzone!

Uwagi ogólne

  • Temat projektu student wybiera samodzielnie spośród zamieszczonych na powyższym wykazie. Należy jednak pamiętać, że do jednego projektu może być przypisanych co najwyżej 2 studentów w grupie. Można także zgłaszać własne propozycje.
  • Szczegóły dotyczące zakresu prac powinny być uzgodnione ze mną jeszcze przed Nowym Rokiem.
  • Projekty mają być wykonane samodzielnie.
  • Program trzeba rozsądnie podzielić na pliki nagłówkowe i źródłowe.
  • Do projektu należy dołączyć dokumentację w postaci komentarza na początku pliku. W dokumentacji należy umieścić:
    1. imię i nazwisko (numer indeksu) autora;
    2. opis metody rozwiązania problemu;
    3. opis używanych struktur danych;
    4. bibliografię (ksiązki, czasopisma, artykuły, linki w internecie).
  • Nieprzekraczalny termin realizacji projektu to 21 stycznia 2010 r.
Ranking

Punkty z laboratoriów

  • zestawienie dorobku punktowego studentów w moich grupach PRz14 i PRz18

powrót na początek strony