ANSI C (semestr zimowy 2012/13)

Język C to jeden z najbardziej rozpowszechnionych imperatywnych języków programowania. Celem tych zajęć jest nauka programowania w języku ANSI C (standard C99). Studium języka C ułatwia start w naturalną ich kontynuację, do której obecnie zaliczają się ważne z komercyjnego punktu widzenia języki C++, C# oraz Java.

Literatura

Literatura papierowa polskojęzyczna:

• K.N.King: Język C. Nowoczesne programowanie. Wydanie 2. Wydawnictwo Helion, Gliwice 2011.
• B.W.Kernighan, D.M.Ritchie: Język ANSI C. Programowanie. Wydanie 2. Wydawnictwo Helion, Gliwice 2010.
• S.Oualline: Język C. Programowanie. Wydawnictwo Helion, Gliwice 2003.

Literatura papierowa anglojęzyczna:

• H.Schildt: C: The Complete Reference, 4th Edition. Osborne/McGraw-Hill, 2000.

Literatura elektroniczna polskojęzyczna:

• C [Wikibooks]
• Programowanie w C (pdf)

Literatura elektroniczna anglojęzyczna:

• The C Book
• Programming languages - C [ISO/IEC 9899:201x] (pdf)
• Steve Summit: Introductory Class Notes oraz Intermediate Class Notes
• Marshall Brain: How C Programming Works
• Steven Holmes: C Programming
• C Language Library

Terminarz

• wykład: czwartek 8-10 s.25 (Marek Piotrów)
• laboratorium (grupy PRz):
  wtorek 12-14 s.110 (Paweł Rzechonek)
  wtorek 16-18 s.110 (Paweł Rzechonek)

Materiały do wykładu i ćwiczeń

• strona przedmiotu [Moodle]
• opis przedmiotu [USOS]

Laboratorium

Zasady zaliczenia przedmiotu

Ogólnie:

Ćwiczenia laboratoryjne będą podzielone na dwie części: krótkie zadania laboratoryjne i projekt. Część zadaniowa będzie obejmować 10 pierwszych ćwiczeń a projektowa 4 ostatnie (pierwsze ćwiczenia to testowanie środowiska programistycznego Bode::Blocks i platformy edukacyjnej Moodle). Po Nowym Roku będzie jeszcze kolokwium.

Zadania laboratoryjne:

Laboratorium na części zadaniowej będzie przebiegać według następującego scenariusza. Tuż przed ćwiczeniami będzie się pojawiać w internecie na tej stronie lista z zadaniem laboratoryjnym i z zadaniami domowymi (na początku będą to trzy zadania po 10 punktów - jedno na laboratorium i dwa domowe; potem będą dwa zadania po 15 punktów - jedno laboratoryjne i jedno domowe).

• Zadanie laboratoryjne należy zaprogramować w czasie trwania zajęć; za poprawne i samodzielne rozwiązanie tego zadań będzie można otrzymać do 10/15 punktów. Kto nie zdąży zrobić zadania na ćwiczeniach może dokończyć je w domu i przesłać rozwiązanie do końca tygodnia na Moodle (dotyczy to również osób nieobenych a mających usprawiedliwienie), ale za spóźnione rozwiązanie będzie można otrzymać maksymalnie połowę punktów.
• Zadania domowe należy zaprogramować w domu i przesłać rozwiązania do końca tygodnia na Moodle; za poprawne i samodzielne rozwiązanie tych zadań będzie można otrzymać do 20/15 punktów.

Przy ocenianiu zadania będą brane pod uwagę następujące rzeczy:

• poprawność rozwązania (zgodność ze specyfikacją),
• sposób rozwiązania (metodyka programowania),
• czytelność kodu (notacja węgierska).

Z części zadaniowej będzie można uzbierać w trakcie semestru maksymalnie 300 punktów.

Projekt:

Część projektowa będzie polegać na zrealizowaniu jednego większego zadania, obejmującego cały przerobiony na części laboratoryjnej materiał. Studenci otrzymają indywidualne zadania projektowe jeszcze przed świętami Bożego Narodzenia. Za samodzielne i poprawne napisanie programu na tej części będzie można dostać do 150 punktów.

Kolokwium:

Po Nowym Roku zostanie przeprowadzone kolokwium. Za kolokwium będzie można dostać do 150 punktów.

Obecności:

Zadania do zaprogramowania będą ogłaszane w internecie tuż przed zajęciami, dlatego obecność na ćwiczeniach jest obowiązkowa.

Prezentacje:

Zadania i projekt można prezentować tylko w czasie trwania pracowni. W trakcie prezentacji programu trzeba się liczyć z pytamiami dotyczącymi rozwiązania: zastosowane metody, zrobione optymalizacje, wykorzystane konstrukcje językowe, itp. Odpowiedzi na te pytania będą miały wpływ na ocenę danego zadania.

Oceny:

Ocena końcowa z ćwiczeń będzie zależeć od zdobytych w semestrze punktów: 50% z częsci zadaniowej, 25% z częsci projektowej i 25% z kolokwium (razem 600 punktów). Ocena będzie wyznaczana według następującej skali:
40% (240 punktów) - dostateczny,
55% (330 punktów) - dostateczny plus,
65% (390 punktów) - dobry,
75% (450 punktów) - dobry plus,
85% (510 punktów) - bardzo dobry.

Lista zadań laboratoryjnych

• Laboratorium 1 (9.10.2012): formatowane wejście/wyjście; proste obliczenia arytmetyczne.
• Laboratorium 2 (16.10.2012): formatowane wejście/wyjście; instrukcje sterujące.
• Laboratorium 3 (23.10.2012): funkcje; rekurencja.
• Laboratorium 4 (30.10.2012): nieformatowane wejście/wyjście; tablice znakowe i napisy.
• Laboratorium 5 (6.11.2012): operacje bitowe; binarna reprezentacja liczb całkowitych.
• Laboratorium 6 (20.11.2012): wskaźniki; pliki nagłówkowe.
• Laboratorium 7 (27.11.2012): wskaźniki; dynamiczne struktury danych.
• Laboratorium 8 (4.12.2012): grafy.
• Laboratorium 9 (11.12.2012): pliki tekstowe.
• Laboratorium 10 (18.12.2012): grafika w GTK+.
• Projekt programistyczny (18.12.2012).

Laboratorium 1 (9.10.2012): formatowane wejście/wyjście; proste obliczenia arytmetyczne.

Zadania laboratoryjne

W poniższych zadaniach dane należy wczytywać ze standardowego wejścia za pomocą funkcji scanf(). Wyniki należy wypisywać na standardowym wyjściu za pomocą funkcji printf(). Zakładamy, że wprowadzone przez użytkownika dane do programu są poprawne.

Zadanie 1 dla grupy wtorkowej 12-14 (10 punktów):

Napisz program, który wczyta trzy dodatnie liczby rzeczywiste będące długościami boków trójkąta. Najpierw sprawdź, czy wczytane liczby mogą być długościami boków w trójkącie - jeśli nie, to natychmiast zakończ działanie programu. Program ma wyliczyć i wypisać powierzchnię tego trójkąta z dokładnością do 3 miejsc po kropce dziesiętnej.
Wskazówka. Skorzystaj ze wzoru Herona, pozwalającego obliczyć pole trójkąta.
Uwaga. Aby użyć funkcji sqrt() liczącej pierwiastek kwadratowy należy włączyć do programu plik nagłówkowy math.h z deklaracjami funkcji matematycznych z biblioteki standardowej.

Zadanie 1 dla grupy wtorkowej 16-18 (10 punktów):

Napisz program, który wczyta trzy dodatnie liczby rzeczywiste będące długościami boków trójkąta. Najpierw sprawdź, czy wczytane liczby mogą być długościami boków w trójkącie - jeśli nie, to natychmiast zakończ działanie programu. Program ma wyliczyć i wypisać wielkości wszystkich kątów w tym trójkącie z dokładnością do 3 miejsc po kropce dziesiętnej (mierzone w radianach).
Wskazówka. Skorzystaj z twierdzenia Carnota, pozwalającego wyznaczyć cosinus dowolnego kąta w trójkącie.
Uwaga. Aby użyć funkcji acos() liczącej arcus cosinus należy włączyć do programu plik nagłówkowy math.h z deklaracjami funkcji matematycznych z biblioteki standardowej.

Zadania domowe

Zadania domowe należy przesłać na Moodla do niedzieli 14.10.2012 do godziny 21:00.

Zadanie 2 (10 punktów):

Napisz program, który wczyta liczbę rzeczywistą oznaczającą temperaturę mierzoną w stopniach Celsjusza. Oblicz i wypisz, ile wynosi ta temperatura w stopniach Fahrenheita, Kelwina i Rankina. Wypisz wyniki z dokładnością do 2 miejsc po kropce dziesiętnej.
Uwaga. W swoim programie zdefiniuj za pomocą dyrektywy #define odpowiednie stałe symboliczne o wartościach 273.15 (do przeliczania na stopnie Kelwina) i 459.67 (do przeliczania na stopnie Rankina) i wykorzystaj je do obliczeń.

Zadanie 3 (10 punktów):

Napisz program, który wczyta współrzędne rzeczywiste dwóch punktów na płaszczyźnie A=(x₁,y₁) i B=(x₂,y₂), które są końcami pewnego odcinka. Program ma wypisać współrzędne punktów przecięcia odcinka AB z osią OX i z osią OY (o ile takie punkty istnieją). Współrzędne punktów przecięcia wypisz z dokładnością do 2 miejsc po kropce dziesiętnej.
Uwaga 1. Program nie powinien wypisać dwa razy tego samgo punktu (chodzi o początek układu współrzędnych (0,0)).
Uwaga 2. Program powinien ignorować sytuację nakładania się odcinka na oś (gdy odcinek leży na którejś osi to ma z nim nieskończenie wiele punktów wspólnych, ale w programie taki przypadek ma być pomijany).
Uwaga 3. Program powinien uwzględniać sytuację, gdy oba końce odcinka leżą w tym samym punkcie (w takim przypadku program ma zbadać, czy ten punkt leży na którejś osi).
Przykład 1: dla punktów (-2,1) i (6,3) program powinien wypisać:
(0.00, 1.50)
Przykład 2: dla punktów (-2,1) i (6,-3) program powinien wypisać:
(0.00, 0.00)
Przykład 3: dla punktów (-2,1) i (-6,3) program nie powinien nic wypisać.
Przykład 4: dla punktów (-2,1) i (0,-1) program powinien wypisać:
(-1.00, 0.00)
(0.00, -1.00)
Przykład 5: dla punktów (-2,0) i (6,0) program powinien wypisać:
(0.00, 0.00)
Przykład 6: dla punktów (0,2) i (0,6) program nie powinien nic wypisać.
Przykład 7: dla punktów (3,0) i (3,0) program powinien wypisać:
(3.00, 0.00)
Przykład 8: dla punktów (6,2) i (6,2) program nie powinien nic wypisać.

Laboratorium 2 (16.10.2012): formatowane wejście/wyjście; instrukcje sterujące.

Zadania laboratoryjne

W poniższych zadaniach dane należy wczytywać ze standardowego wejścia stdin za pomocą funkcji scanf(). Wyniki należy wypisywać na standardowym wyjściu stdout za pomocą funkcji printf(). Programy powinny wypisywać na standardowe wyjście dla błędów stderr komunikaty informujące użytkownika o tym, kiedy progam oczekuje na wprowadzenie danych oraz o tym, jakiego rodzaju wyniki zostały wypisane. Po wczytaniu każdej liczby sprawdź, czy operacja czytania powiodła się.

Zadanie 1 dla grupy wtorkowej 12-14 (10 punktów):

Napisz program, który wczyta ze standardowego wejścia małą liczbę naturalną x a następnie wyliczy i wypisze na standardowe wyjście jej rozkład na czynniki pierwsze (każdy czynnik w oddzielnej linii); na koniec program ma wypisać na standardowe wyjście dla błędów informację o tym, czy liczba ta jest pierwsza czy złożona.
Uwaga. Sprawdź w swoim programie czy poprawnie wczytano liczbę całkowitą i czy jest ona <0 i >1000000.
Przypomnienie. Liczba pierwsza to liczba naturalna >1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą.
Przykład 1: dla liczby 60 program powinien wypisać:
2
2
3
5
60 to liczba złożona
Przykład 2: dla liczby 41 program powinien wypisać:
41
41 to liczba pierwsza
Przykład 3: dla liczby -7 program powinien wypisać:
błędne dane

Zadanie 1 dla grupy wtorkowej 16-18 (10 punktów):

Napisz program, który wczyta ze standardowego wejścia małą liczbę naturalną x a następnie wyliczy i wypisze na standardowe wyjście wszystkie jej dzielniki właściwe (każdy dzielnik w oddzielnej linii); na koniec program ma wypisać na standardowe wyjście dla błędów informację o tym, czy liczba ta jest doskonała czy nie.
Uwaga. Sprawdź w swoim programie czy poprawnie wczytano liczbę całkowitą i czy jest ona <0 i >1000000.
Przypomnienie. Dzielnikiem właściwym liczby nazywa się każdy jej dodatni dzielnik, który jest od niej różny. Liczba doskonała to liczba naturalna, która jest sumą wszystkich swych dzielników właściwych.
Przykład 1: dla liczby 28 program powinien wypisać:
1
2
4
7
14
28 jest liczbą doskonałą
Przykład 2: dla liczby 41 program powinien wypisać:
1
41 nie jest liczbą doskonałą
Przykład 3: dla liczby -7 program powinien wypisać:
błędne dane

Zadania domowe

Zadania domowe należy przesłać na Moodla do niedzieli 21.10.2012 do godziny 21:00.

Zadanie 2 (10 punktów):

Napisz program, który wczyta liczbę naturalną n a potem wydrukuje na standardowym wyjściu romb (taki jak karo w kartach), używając tylko spacji i gwiazdek. Wszystkie boki rombu mają być równe i mają składać się z n gwiazdek.
Uwaga. Sprawdź w swoim programie czy poprawnie wczytano liczbę całkowitą i czy jest ona <1 i >20.
Przykład: Dla n=5 program powinien wydrukować na ekranie następującą figurę:
        *
      *   *
    *       *
  *           *
*               *
  *           *
    *       *
      *   *
        *

Zadanie 3 (10 punktów):

Napisz program, który wydrukuje w estetyczny sposób tabelę z kodami dla znaków ASCII. Należy wypisać kod znaku najpierw w postaci dziesiętnej (na 3 pozycjach), potem szesnastkowej (na 2 pozycjach) a na końcu sam znak. Program powinien wydrukować tabelę tylko dla znaków o kodach od 32 do 126. Znaki należy wydrukować w taki sposób, aby kolejność ich kodów była uporządkowana kolumnami (czytamy kolejne kolumny z góry na dół). Tabela ma się składać z 6 kolumn (16 wierszy), przy czym ostania kolumna będzie niepełna.
Uwaga. Kolumny mają być odseparowane za pomocą kilku spacji. Możesz założyć, że konsola ma szerokość 80 pozycji.

Laboratorium 3 (23.10.2012): funkcje; rekurencja.

Zadania laboratoryjne

Przed definicjami funkcji w programie umieść najpierw ich deklaracje. Sam program powinien sprawdzić poprawność danych wejściowych i jeśli wykryje błędy, to powinien natychmiast zakończyć działanie.

Zadanie 1 dla grupy wtorkowej 12-14 (10 punktów):

Napisz program, który dla zadanych liczb naturalnych p i q wyliczy i wypisze ich najwięszy wspólny dzielnik i najmniejszą wspólną wielokrotność. Liczby p i q niech będą zadane poprzez argumenty wywołania programu.
Do wyliczenia najwięszego wspólnego dzielnika zdefiniuj funkcję rekurencyjną, implementującą algorytm Euklidesa.
Uwaga. Program powinien sprawdzić, czy został wywołany z poprawnymi parametrami.
Przykład 1: dla liczb 60 i 75 program powinien wypisać:
15
300
Przykład 2: dla liczb 7 i 3 program powinien wypisać:
1
21
Przykład 3: dla liczb 30 i 6 program powinien wypisać:
6
30

Zadanie 1 dla grupy wtorkowej 16-18 (10 punktów):

Napisz program, który zadaną liczbę całkowitą r wypisze w postaci binarnej. Liczba r niech będzie zadana poprzez argumenty wywołania programu.
Do wypisania liczby w postaci binarnej zdefiniuj funkcję rekurencyjną, która zapisze ją we wskazanej tablicy znaków; powinna ona zwrócić długość napisu reprezentującego zadaną liczbę. Funkcja ta ma sobie radzić zarówno z liczbami dodatnimi (wpisując na początku znak +) jak i z ujemnymi (wpisując na początku znak -) z całego zakresu typu int.
Wskazówka. Napisz rekurencyjną funkcję pomocniczą, która będzie zapisywać w tablicy w postaci binarnej tylko liczby dodatnie.
Uwaga. Program powinien sprawdzić, czy został wywołany z poprawnymi parametrami.
Przykład 1: dla liczby 28 program powinien wypisać:
+11100
Przykład 2: dla liczby -41 program powinien wypisać:
-101001
Przykład 3: dla liczby 0 program powinien wypisać:
0

Zadania domowe

Zadania domowe należy przesłać na Moodla do niedzieli 28.10.2012 do godziny 21:00.

Zadanie 2 (10 punktów):

Napisz program, który wczyta liczbę naturalną n a potem n liczb rzeczywistych, umieszczając je w automatycznie utworzonej tablicy. Następnie program ma obliczyć i wypisać średnią arytmetyczną, średnią geometryczną i odchylenie standardowe dla tych liczb z dokładnościa do 12 miejsc po kropce dziesiętnej.
Do wyliczenia średniej arytmetycznej, średniej geometrycznej i odchylenia standardowego zdefiniuj osobne funkcje; w swoich obliczeniach użyj funkcji pomocniczych liczących sumę i iloczyn liczba w tablicy. Funkcje te powinny przyjmować jako argumenty odniesienie do tablicy typu double[] i jej długość (liczbę komórek).

Zadanie 3 (10 punktów):

Napisz program, który wczyta dwie liczby naturalne n i k a następnie wyliczy i wypisze dla tych liczb wartość symbolu Newtona (ⁿ_k).
Do wyliczenia symbolu Newtona zdefiniuj funkcję rekurencyjną zgodnie ze wzorem:
(ⁿ₀) = (ⁿ_n) = 1 dla n≥0
(ⁿ_k) = (^n-1_k-1)·n/k dla 0<k<n

Laboratorium 4 (30.10.2012): nieformatowane wejście/wyjście; tablice znakowe i napisy.

Zadania laboratoryjne

W poniższych zadaniach nie wolno używać funkcji printf() do pisania formatowanego na standardowe wyjście ani funkcji scanf() do czytania formatowanego ze standardowego wejścia. W zamian za to posłuż się funkcjami fputc(), fputs(), fgetc() i fgets().

Zadanie 1 dla grupy wtorkowej 12-14 (10 punktów):

Napisz program, który odczyta standardowe wejście linia po linii, aż do napotkania symbolu EOF. Każdą z linii należy umieścić w tablicy znakowej i sprawdzić, czy zawiera ona poprawnie zapisaną liczbę dziesiętną (liczba ta może być bardzo duża i nie zmieści się w żadnym standardowym typie danych). Jeśli w linii jest zapisana liczba dziesiętna, to wypisz ją na standardowym wyjściu, w przeciwnym przypadku nie rób nic.
Liczba dziesiętna to pojedynczy znak '0' albo ciąg cyfr dziesiętnych rozpoczynający się od cyfry różnej od '0'; liczby ujemne rozpoczynają się od znaku minus '-', przed liczbą dodatnią może stać plus '+' (liczba 0 może być poprzedzona plusem albo minusem).
Uwaga. Zakładamy, że długość każdej linii nie przekracza 79 znaków. Użyj więc 80-znakowego bufora i funkcji fgets() do czytania danych ze standardowego wejścia oraz funkcji fputs() do wypisywania wyników.

Zadanie 1 dla grupy wtorkowej 16-18 (10 punktów):

Napisz program, który odczyta standardowe wejście linia po linii, aż do napotkania symbolu EOF. Każdą z linii należy umieścić w tablicy znakowej i sprawdzić, czy zawiera ona poprawnie zapisany identyfikator (taki jak w języku C). Jeśli w linii jest zapisany identyfikator, to wypisz go na standardowym wyjściu, w przeciwnym przypadku nie rób nic.
Identyfikator to ciąg znaków składający się z małych lub dużych liter alfabetu angielskiego, cyfr dziesiętnych i znaku podkreślenia '_', który nie rozpoczyna się od cyfry.
Uwaga. Zakładamy, że długość każdej linii nie przekracza 79 znaków. Użyj więc 80-znakowego bufora i funkcji fgets() do czytania danych ze standardowego wejścia oraz funkcji fputs() do wypisywania wyników.

Zadania domowe

Zadania domowe należy przesłać na Moodla do niedzieli 4.11.2012 do godziny 21:00.

Zadanie 2 (10 punktów):

Napisz program, który przepisze tekst ze standardowego wejścia na standardowe wyjście, i który w trakcie działania skompresuje bloki odstępów (spacje i tabulacje) występujące w linii do pojedynczej spacji oraz pominie odstępy występujące na końcu linii.
Dodatkowo program ma przyciąć długie linie wynikowe do k znaków, o ile liczba k została zadana przez argument wywołania programu (pomiń przycinanie linii jeśli program wywołano bez żadnego argumentu).

Zadanie 3 (10 punktów):

Napisz program, który przeczyta ze standardowego wejścia wszystkie znaki, aż do napotkania symbolu EOF. Na końcu program powinien wypisać na standardowym wyjściu statystykę dotycząca wczytanego tekstu: ile było wszystkich przeczytanych znaków, z ilu linii składał się tekst, ile w nim było słów/bloków (pooddzielanych odstępami) oraz ile w tym tekście wystąpiło liter, cyfr i znaków przestankowych (kropek, przecinków, dwukrpków, średników, pytajników, wykrzykników i myślników). Każdą z tych informacji (liczby całkowite) zapisz w osobnej linii w standardowym strumieniu wyjściowym; informacje te poprzedź komentarzem (do czego odnosi się dana liczba) skierowanym do standardowego strumienia wyjściowego dla błędów.
Uwaga. Wypisując statystykę użyj funkcji fprintf().

Laboratorium 5 (6.11.2012): operacje bitowe; binarna reprezentacja liczb całkowitych.

W poniższych zadaniach nie wolno używać żadnych funkcji matematycznych z biblioteki standardowej - korzystaj tylko z operacji bitowych i ewentualnie arytmetycznych.

Zadanie 1 dla grupy wtorkowej 12-14 (10 punktów):

Dość często potrzebujemy ustawiać lub sprawdzać wartości pojedynczych bitów w słowie typu int lub unsigned int. Zdefiniuj dwie funkcje: jedną do odczytywania wartości określonego bitu w słowie (funkcja ma zwracać wartość 0 lub 1), a drugą do ustawiania wartości określonego bitu (funkcja ma ustawić bit na 1 tylko wtedy, gdy parametr bit ma wartość różną od 0):
int jakiBit (int liczba, unsigned int nrBitu);
void ustawBit (int *liczba, unsigned int nrBitu, int bit);
Na koniec przetestuj działanie obu funkcji picząc 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 32 bity zaczynając od najbardziej znaczącego).
Dodatkowo program ma wypisać bit znaku wczytanej liczby oraz policzyć i wypisać, na której pozycji znajduje się pierwszy zapalony bit w liczbie dodatniej albo pierwszy zgaszony bit w liczbie ujemnej (rozpocznij poszukiwania od najbardziej znaczącego bitu).

Zadanie 1 dla grupy wtorkowej 16-18 (10 punktów):

Dość często potrzebujemy ustawiać lub sprawdzać wartości pojedynczych bitów w słowie typu int lub unsigned int. Zdefiniuj dwie funkcje: jedną do odczytywania wartości określonego bitu w słowie (funkcja ma zwracać wartość 0 lub 1), a drugą do ustawiania wartości określonego bitu (funkcja ma ustawić bit na 1 tylko wtedy, gdy parametr bit ma wartość różną od 0):
int jakiBit (int liczba, unsigned int nrBitu);
void ustawBit (int *liczba, unsigned int nrBitu, int bit);
Na koniec przetestuj działanie obu funkcji picząc 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 32 bity zaczynając od najbardziej znaczącego).
Dodatkowo program ma wypisać bit znaku wczytanej liczby oraz policzyć i wypisać ile jest w niej bitów zapalonych gdy liczba jest dodatnia albo ile zgaszonych gdy jest ujemna.

Zadania domowe

Zadania domowe należy przesłać na Moodla do niedzieli 11.11.2012 do godziny 21:00.

Zadanie 2 (10 punktów):

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 dwójkowej (wszystkie bity zaczynając od bitu znaku) i w następnej linii nową wartość po transformacji.
Przykłady 1: dla liczby 19 program powinien wypisać:
00000000000000000000000000010011
11001000000000000000000000000000
Przykłady 2: dla liczby -4 program powinien wypisać:
11111111111111111111111111111100
00111111111111111111111111111111

Zadanie 3 (10 punktów):

Napisz program, który wczyta ze standardowego wejścia liczby całkowite n oraz s i przesunie cyklicznie wszystkie bity liczby n o s pozycji w lewo.
Wskazówka. Gdy przesuwamy liczbę o jedną pozycję w lewo, to bit z pozycji 0 zostanie przeniesiony na pozycję 1, bit z pozycji 1 zostanie przeniesiony na pozycję 2 itd; bit najbardziej znaczący zostanie przeniesiony na pozycję 0. Gdy s<0 to tak, jakbyśmy ją przesuwali w prawo.
Uwaga. Program ma wypisać najpierw pierwotną wartość liczby n w postaci dwójkowej (wszystkie bity zaczynając od bitu znaku) i w następnej linii nową wartość po transformacji.
Przykłady 1: dla liczb 19 i 3 program powinien wypisać:
00000000000000000000000000010011
00000000000000000000000010011000
Przykłady 2: dla liczb 19 i -2 program powinien wypisać:
00000000000000000000000000010011
11000000000000000000000000000100
Przykłady 3: dla liczb 19 i 32 program powinien wypisać:
00000000000000000000000000010011
00000000000000000000000000010011

Laboratorium 6 (20.11.2012): wskaźniki; pliki nagłówkowe.

Program laboratoryjny podziel na pliki nagłówkowe i źródłowe; zadania domowe zaprogramuj w jednym pliku, przy czym na początku umieść deklaracje wzystkich funkcji tak jak w pliku nagłówkowym. Używaj raczej wskaźników niż operatorów indeksowania. Zabezpiecz swoje programy przed wyjściem poza tablicę przy przesuwaniu wskaźników.

Zadanie 1 dla grupy wtorkowej 12-14 (10 punktów):

Zdefiniuj funkcję obliczającą długość ciągu znakowego (liczba znaków w ciągu z pominięciem symbolu kończącego '\0'):
int dlugosc (const char *p);
Funkcja dlugosc() powinna używać tylko jednego pomocniczego wskaźnika (wynikiem może być wartość licznika albo różnica pomiędzy wskaźnikami).
Zdefiniuj też funkcję odwracającą znaki w ciągu znakowym (zamiana pierwszego znaku z ostatnim, drugiego z przedostatnim, itd):
void odwroc (char *p);
Funkcja odwroc() powinna używać tylko dwóch wskaźników pomocniczych (jeden ustawiony na początku napisu a drugi na jego końcu w procesie inicjalizacji) oraz powinna korzystać z funkcji dlugosc() z poprzedniego zadania i z funkcji zamien().
void zamien (char *r, char *s);
Na koniec napisz program testujący twoje funkcje, który odczyta standardowe wejście linia po linii, odwróci każdą linię w miejscu i wypisze ją po odwróceniu na standardowym wyjściu.
Uwaga. Zakładamy, że długość każdej linii nie przekracza 79 znaków. Użyj więc 81-znakowego bufora i funkcji fgets() do czytania danych ze standardowego wejścia oraz funkcji fputs() do wypisywania wyników na standardowe wyjście.

Zadanie 1 dla grupy wtorkowej 16-18 (10 punktów):

Zdefiniuj funkcję kopiującą znaki z podanego ciągu znakowego do wskazanego miejsca:
void kopiuj (const char *skad, char *dokad);
Funkcja kopiuj() nie powinna używać żadnych pomocniczych wskaźników.
Następnie zdefiniuj funkcję porównującą ciągi znakowe (dwa ciągi są takie same, gdy wszystkie znaki na odpowiadających sobie pozycjach są takie same):
int takiesame (const char *p, const char *q);
Funkcja takiesame() też nie powinna używać żadnych pomocniczych wskaźników.
Na koniec napisz program testujący twoje funkcje, który odczyta standardowe wejście linia po linii i wypisze na standardowe wyjście wszystkie, które się nie powtarzają po sąsiedzku. W swoim programie użyj do czytania dwóch buforów i operacji kopiowania.
Uwaga. Zakładamy, że długość każdej linii nie przekracza 79 znaków. Użyj więc 81-znakowego bufora i funkcji fgets() do czytania danych ze standardowego wejścia oraz funkcji fputs() do wypisywania wyników na standardowe wyjście.

Zadania domowe

Zadania domowe należy przesłać na Moodla do niedzieli 25.11.2012 do godziny 21:00.

Zadanie 2 (10 punktów):

Zdefiniuj funkcję sortującą dane typu int zapisane w tablicy. Zaimplementuj sortowanie przez wstawianie.
void sortuj (int t[], int n);
Funkcja sortuj() powinna używać pomocniczej funkcji porownaj_zamien(), która porówna ze sobą wskazane elementy i jeśli nie są uporządkowane to zamieni je miejscami (funkcja ma zwrócić wartość boolowską odnoszącą się do wykonanej zamiany elementów).
int porownaj_zamien (int *r, int *s);
Następnie napisz program, który wczyta liczbę naturalną n a potem n liczb całkowitych, umieszczając je w automatycznie utworzonej tablicy, potem posortuję tę tablicę i wypisze ją po posortowaniu.

Zadanie 3 (10 punktów):

Napisz program, który liczby całkowite typu long przekazane do programu poprzez argumenty wywołania wypisze w postaci słownej. Program powinien korzystać z tablic liczebników:
const char *JEDNO[] = {””, ”jeden”, ”dwa”, ”trzy”, ..., ”osiemnascie”, ”dziewietnascie”};
const char *DZIES[] = {””, ”dziesiec”, ”dwadziescia”, ... , ”osiemdziesiat”, ”dziewiecdziesiat”};
const char *SETKI[] = {””, ”sto”, ”dwiescie”, ”trzysta”, ... , ”osiemset”, ”dziewiecset”};
W swoim programie zdefiniuj i wykorzystaj funkcję, która przekształci liczbę na napis, umieszczając wynik w zewnętrznym buforze.
void konwersja (long x, char buf[]);
Funkcja ta powinna korzystać z metody, która dokleja łańcuch znakowy do innego łańcucha w buforze (funkcja dopisz() ):
void dopisz (const char *co, char gdzie[]);
Funkcja dopisz() powinna z kolei korzystać z funkcji obliczającej długość łańcucha znakowego i funkcji kopiującej łańcuch znakowy z jednego miejsca do drugiego.
Liczebniki tysiąc, milion i miliard same dają się liczyć z użyciem mnożnej tak jak zwykłe rzeczowniki (konstrukcja z mianownikiem l. mn. występuje przy mnożnych zakończonych na 2, 3, 4 z wyjątkiem zakończonych na 12, 13, 14 a konstrukcja z dopełniaczem l. mn. obowiązuje we wszystkich pozostałych przypadkach). Zadbaj o to, by w liczebnikach większych od 999 użyć właściwej deklinacji dla miliardów (miliard, -y, -ów), milionów (milion, -y, -ów) i tysięcy (tysiąc, -e, tysięcy). Posłuż się tablicą:
const char *odmiana[][4] = { {””, ””, ””, ””},
  {””, ”tysiac”, ”tysiace”, ”tysiecy”},
  {””, ”milion”, ”miliony”, ”milionow”},
  {””, ”miliard”, ”miliardy”, ”miliardow”} };
Uwaga 1! Program ma poprawnie działać dla wartości ujemnych wpisując słowo minus na początku bufura wynikowego.
Uwaga 2! Program ma poprawnie działać także dla wartości 0 i -2147483648.
Uwaga 3! Pomiędzy poszczególnymi liczebnikami powinny się znajdować pojedyncze odstępy.
Przykład: dla liczb 256, -102, 1000002012 i 0 przekazanych poprzez argumenty wywołania program powinien wypisać:
dwiescie piecdziesiat szesc
minus sto dwa
jeden miliard dwa tysiace dwanascie
zero

Laboratorium 7 (27.11.2012): wskaźniki; dynamiczne struktury danych.

Program laboratoryjny podziel na pliki nagłówkowe i źródłowe; zadania domowe zaprogramuj w jednym pliku, przy czym na początku umieść deklaracje wzystkich funkcji tak jak w pliku nagłówkowym. Przy programowaniu operacji na strukturach dynamicznych używaj raczej rekurencji niż iteracji. Pamiętaj, aby zawsze na końcu zwolnić przydzieloną w trakcie działania programu pamięć na stercie.

Zadanie 1 dla grupy wtorkowej 12-14 (10 punktów):

Zdefiniuj strukturę reprezentującą węzeł listy jednokierunkowej struct element, w której będzie pole nast wskazujące na następny element na liście oraz pole wartosc przechowujące pewną wartość typu TYP (TYP oraz makra do czytania i pisania danych tego typu zdefiniuj za pomocą dyrektywy #define):
// przykład dla typu double
# define TYP double
# define CZYT(x) scanf("%lf",&x)
# define PISZ(x) printf("%.3f",x)
typedef struct element {
    TYP wartosc;
    struct element *nast;
} wezel;
Oprócz struktury zadeklaruj i zdefiniuj funkcje wstaw_na_pocz() (wstawienie nowego elementu na początek listy), wstaw_na_kon() (wstawienie nowego elementu na koniec listy), ile() (policzenie ile jest elementów na liście) oraz wypisz() (wypisanie kolejno wszystkich wartości zapamiętanych w liście). Pierwszym argumentem tych funkcji powinien być wskaźnik na początek listy. Funkcje ile() i wypisz() zdefiniuj rekurencyjnie.
Następnie uzupełnij moduł programu o możliwość usunięcia elementu z listy z zadanej pozycji funkcją usun_z_pozycji(), sprawdzenia gdzie na liście znajduje się element o zadanej wartości funkcją szukaj_wartosci() oraz sprawdzenia jaka wartość znajduje się na zadanej pozycji na liście funkcją sprawdz_pozycje().
Na koniec 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.
Uwaga. Zakładamy, że polecenia wraz z parametrami zawsze są w programie podawane prawidłowo.

Zadanie 1 dla grupy wtorkowej 16-18 (10 punktów):

Zdefiniuj strukturę reprezentującą węzeł listy jednokierunkowej struct element, w której będzie pole nast wskazujące na następny element na liście oraz pole wartosc przechowujące pewną wartość typu TYP (TYP oraz makra do czytania i pisania danych tego typu zdefiniuj za pomocą dyrektywy #define):
// przykład dla typu double
# define TYP double
# define CZYT(x) scanf("%lf",&x)
# define PISZ(x) printf("%.3f",x)
typedef struct element {
    TYP wartosc;
    struct element *nast;
} wezel;
Oprócz struktury zadeklaruj i zdefiniuj funkcje wstaw() wstawiającą nowy element do listy w takim miejscu, aby zachowany był porządek niemalejący (możesz zdefiniować makro porównujące elementy typu TYP), ile() (policzenie ile jest elementów na liście) oraz wypisz() (wypisanie kolejno wszystkich wartości zapamiętanych w liście). Pierwszym argumentem tych funkcji powinien być wskaźnik na początek listy. Funkcje ile() i wypisz() zdefiniuj rekurencyjnie.
Następnie uzupełnij moduł programu o możliwość usunięcia elementu z listy o zadanej wartości funkcją usun_wartosc(), sprawdzenia gdzie na liście znajduje się element o zadanej wartości funkcją szukaj_wartosci() oraz sprawdzenia jaka wartość znajduje się na zadanej pozycji na liście funkcją sprawdz_pozycje().
Na koniec 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.
Uwaga. Zakładamy, że polecenia wraz z parametrami zawsze są w programie podawane prawidłowo.

Zadania domowe

Zadania domowe należy przesłać na Moodla do niedzieli 2.12.2012 do godziny 21:00.

Zadanie 2 (10 punktów):

Zdefiniuj strukturę reprezentującą węzeł drzewa 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 (TYP oraz makra do czytania i pisania danych tego typu zdefiniuj za pomocą dyrektywy #define):
// przykład dla typu double
# define TYP double
# define CZYT(x) scanf("%lf",&x)
# define PISZ(x) printf("%.3f",x)
typedef struct element {
    TYP wartosc;
    struct element *lewe, *prawe;
} wezel;
Oprócz struktury zadeklaruj i zdefiniuj funkcje wstaw() (wstawienie nowego elementu do drzewa), szukaj() (sprawdzenie czy w drzewie znajduje się element o zadanej wartości), 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 na korzeń drzewa lub poddrzewa wezel*. Wszystkie wymienione funkcje zaimplementuj rekurencyjnie.
Następnie uzupełnij program o 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). Pierwszym argumentem tych funkcji powinien być wskaźnik do wskaźnika na korzeń drzewa lub poddrzewa wezel**.
Na koniec napisz program testujący zaprogramowane przez Ciebie drzewo. 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. Oto lista poleceń, które program ma realizować: wstaw, usun, szukaj, ile, pisz oraz koniec (na końcu program ma usunąć całe drzewo z pamięci).
Uwaga. Zakładamy, że polecenia wraz z parametrami zawsze są w programie podawane prawidłowo.
Przykład: program rozpoczyna działanie z drzewem pustym:
wstaw 8
wstaw 1
wstaw 2
wstaw 1
wstaw 7
wstaw 1
wstaw 4
pisz
1 2 4 7 8
szukaj 8
1
ile
5
wstaw 5
usun 1
usun 8
wstaw 3
usun 8
usun 4
pisz
2 3 5 7
szukaj 8
0
ile
4
koniec

Zadanie 3 (10 punktów):

Tablica socjacyjna to struktura (często jest to tablica ale niekoniecznie), w której przechowujemy pary elementów klucz-wartość. Zdefiniuj strukturę reprezentującą element tablicy asocjacyjnej, gdzie kluczem jest napis o dowolnej długości char* (przechowywany na stercie) a skojarzoną wartością liczba rzeczywista typu double.
typedef struct element {
    double wartosc;
    char klucz*;
} el;
Następnie zdefiniuj strukturę dla tablicy dynamicznej. Tablica taka posiada pewną pojemność, którą można wykorzystać wstawiając do niej nowe elementy. Gdy tablica taka zapełni się a program chce wstawić do niej kolejny element, to tworzymy nową (dwa razy większą) tablicę, przepisujemy do niej wartości ze starej tablicy i dopisujemy jeden nowy (poprzednią tablicę należy usunąć z pamięci).
typedef struct tab_dynam {
    el *tab;
    int pojemnosc, zajetosc;
} td;
Napisz program, który będzie zarządzał tablicą asocjacyjną zbudowaną na tablicy dynamicznej. Początkowo tablica dynamiczna ma mieć pojemność jednej komórki (i zerową zajętość). 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. Oto lista poleceń, które program ma realizować: dodaj (wstawienie nowej pary klucz-wartość do tablicy), szukaj (odnalezienie wartości na podstawie zadanego klucza; gdy klucza nie ma w tablicy asocjacyjnej to należy zwrócić wartość 0.0), zmien (podmiana wartości skojarzonej z zadanym kluczem; gdy klucza nie ma w tablicy asocjacyjnej to należy utworzyć nową parę), wypisz (wypisanie wszystkich par klucz-wartość przechowywanych w tablicy) oraz koniec (wyjście z programu; przed zakończeniem należy usunąć całą strukturę z pamięci).
Wskazówka. Do wyznaczania długości, kopiowania i porównywania napisów użyj funkcji z biblioteki standardowej zdefiniowanych w pliku nagłówkowym string.h.
Uwaga. Zakładamy, że polecenia wraz z parametrami zawsze są w programie podawane prawidłowo.
Przykład: program rozpoczyna działanie z pustą tablicą acocjacyjną:
dodaj asd 8.9
dodaj fgh 7.6
dodaj jkl 5.4
dodaj zxcv 1.2
dodaj bnm -3.4
szukaj jkl
5.400
szukaj qwerty
0.000
zmien bnm -2.3
zmien uiop 0.5
wypisz

asd 8.900
fgh 7.600
jkl 5.400
zxcv 1.200
bnm -2.300
uiop 0.500
koniec

Laboratorium 8 (4.12.2012): grafy.

Zapoznaj się z pojęciem grafu oraz metodami przeszukiwania grafów wszerz (BFS) i w głąb (DFS).

Zadanie 1 dla grupy wtorkowej 12-14 (15 punktów):

Pewne przedsiębiorstwo jest właścicielem ogólnokrajowej sieci kolejowej. Stacje kolejowe są zlokalizowane we wszystkich miastach wojewódzkich i w stolicy (oraz w wielu mniejszych miasteczkach). Sieć linii kolejowych składa się z odcinków torów łączących stacje kolejowe. Wiadomo, że z każdej stacji kolejowej da się dojechać do każdej innej stacji kolejowej (potencjalnie odwiedzając stacje pośrednie). Odcinki torów sa dwukierunkowe. Między każdą parą stacji może być co najwyżej jeden odcinek torów. Każdy taki odcinek torów charakteryzuje się kosztem przejazdu, czyli dodatnią liczbą całkowitą.

Pewnego razu wszyscy wojewodowie postanowili spotkać się w stolicy przyjeżdżając tam pociągami. Trasa przejazdu każdego wojewody do stolicy powinna przebiegać przez jak najmniejszą liczbę miejscowości.

Przejazd wszystkich wojewodów ma być sfinansowany z budżetu. Twoim zadaniem jest wyliczenie minimalnej kwoty, jaką należy przeznaczyć na sfinansowanie ich podróży do stolicy. Napisz więc program, który wczyta ze standardowego wejścia opis sieci linii kolejowych, zapamięta go w grafie w postaci listy sąsiadów, wyznaczy dla każdego miasta wojewódzkiego minimalny koszt dojazdu do stolicy przez jak najmniejszą liczbę stacji pośrednich, a w końcu podsumuje i wypisze na standardowym wyjściu koszt podróży wszystkich wojewodów do stolicy.

Uwaga. W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite n i m, przy czym 2 ≤ n ≤ 1000 oraz 1 ≤ m < 500000 (n-1 ≤ m ≤ n(n-1)/2), oddzielone pojedynczym odstępem. Liczba n to liczba stacji kolejowych, a m liczba odcinków torów. Stacje kolejowe sa ponumerowane od 0 do n-1. W kolejnych m wierszach są opisane odcinki torów kolejowych, po jednym w wierszu. W każdym z tych wierszy są zapisane po trzy dodatnie liczby całkowite a, b i c, przy czym 0 ≤ a, b ≤ n-1, a ≠ b, 1 ≤ c ≤ 100000. Liczby a i b to numery stacji, które łaczy dany odcinek torów, a c to związany z nim koszt przejazdu. W m+2 wierszu zapisany jest ciąg liczb całkowitych pooddzielanych pojedynczymi odstępami. Pierwsza z nich to s - numer stacji stołecznej. Następna to w - liczba stacji w miastach wojedódzkich. Dalej w tym wierszu wymienione są numery wszystkich stacji wojedódzkich w kolejności rosnacej.

Wskazówka. Zastosuj przeszukiwanie wszerz (BFS).

Zadanie 1 dla grupy wtorkowej 16-18 (15 punktów):

Pewne przedsiębiorstwo jest właścicielem ogólnokrajowej sieci kolejowej. Stacje kolejowe są zlokalizowane we wszystkich miastach wojewódzkich i w stolicy (oraz w wielu mniejszych miasteczkach). Sieć linii kolejowych składa się z odcinków torów łączących stacje kolejowe. Wiadomo, że z każdej stacji kolejowej da się dojechać do każdej innej stacji kolejowej (potencjalnie odwiedzając stacje pośrednie). Odcinki torów sa dwukierunkowe. Między każdą parą stacji może być co najwyżej jeden odcinek torów. Każdy taki odcinek torów charakteryzuje się kosztem przejazdu, czyli dodatnią liczbą całkowitą.

Pewnego razu do stolicy przyleciał prezydent z bardzo bogatego kraju. Postanowiono więc zaproponować mu wycieczkę po kraju, tak aby wycieczka ta była jak najdroższa. Trasa ma się rozpoczynać w stolicy i kończyć poza nią oraz przebiegać przez różne miejscowości.

Przejazd obcego prezydenta ma zasilić budżet państwa. Twoim zadaniem jest wyliczenie maksymalnej kwoty, jaką można zarobić na trasie przejazdu dostojnego gościa. Napisz więc program, który wczyta ze standardowego wejścia opis sieci linii kolejowych, zapamięta go w grafie w postaci listy sąsiadów, wyznaczy trasę o maksymalnym koszcie przejazdu, przebiegającą przez różne stacje z początkiem w stolicy, a w końcu podsumuje i wypisze na standardowym wyjściu koszt podróży prezydenta.

Uwaga. W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite n i m, przy czym 2 ≤ n ≤ 100 oraz 1 ≤ m < 5000 (n-1 ≤ m ≤ n(n-1)/2), oddzielone pojedynczym odstępem. Liczba n to liczba stacji kolejowych, a m liczba odcinków torów. Stacje kolejowe sa ponumerowane od 0 do n-1. W kolejnych m wierszach są opisane odcinki torów kolejowych, po jednym w wierszu. W każdym z tych wierszy są zapisane po trzy dodatnie liczby całkowite a, b i c, przy czym 0 ≤ a, b ≤ n-1, a ≠ b, 1 ≤ c ≤ 100000. Liczby a i b to numery stacji, które łaczy dany odcinek torów, a c to związany z nim koszt przejazdu. W m+2 wierszu zapisana jest jedna liczba całkowita s - numer stacji stołecznej.

Wskazówka. Zastosuj przeszukiwanie w głąb (DFS). Postaraj się odcinać ścieżki poszukiwań nie rokujące poprawienia dotychczasowego rezultatu.

Zadania domowe

Zadanie domowe należy przesłać na Moodla do niedzieli 9.12.2012 do godziny 21:00.

Zadanie 2 (15 punktów):

Na kwadratowej szachownicy n × n znajduje się k superskoczków. Każdy z nich może wykonywać skoki oparte na trójkącie prostokątnym o różnych bokach a i b. Każdy rodzaj ruchu jest określony za pomocą dwóch różnych liczb całkowitych - pierwsza liczba mówi o ile kolumn (w prawo w przypadku liczby dodatniej lub w lewo w przypadku liczby ujemnej) a druga o ile wierszy (do przodu w przypadku liczby dodatniej lub do tyłu w przypadku liczby ujemnej) przesuwa się skoczek wykonując taki ruch. Pojedynczy ruch skoczka jest więc określony za pomocą wektora (±a, ±b) albo (±b, ±a).

Twoim zadaniem jest wyznaczenie liczby pól, do których jest najtrudniej dotrzeć (liczba wykowywanych ruchów przez skoczki jest największa), albo do których nie można dotrzeć w ogóle. Napisz więc program, który wczyta ze standardowego wejścia rozmiar szachownicy n, liczbę skoczków k i ich położenia, liczby charakteryzujące ruchy skoczków a i b, następnie wygeneruje graf w postaci macierzy sąsiedztwa wszystkich możliwych ruchów z każdego pola, wyznaczy liczbę pól najtrudniej osiągalnych albo nieosiągalnych przez skoczki i wypisze tą liczbę na standardowym wyjściu a poniej w nowej linii liczbę koniecznych ruchów, aby takie pola osiągnąć którymś ze skoczków (albo wartość -1 gdy zliczone pola są nieosiągalne przez żadnego skoczka).

Uwaga. W pierwszym wierszu standardowego wejścia zapisana jest liczba całkowita n oznaczająca rozmiar boku kwadratowej planszy, przy czym 2 ≤ n ≤ 50. W drugim wierszu zapisana jest liczba skoczków k, przy czym 1 ≤ k ≤ n². W kolejnych k wierszach są zapisane różne współrzędne skoczków. W każdym z tych wierszy są zapisane po dwie dodatnie liczby całkowite s i t, przy czym 0 ≤ s, t ≤ n-1. Liczby s i t to odpowiednio numer kolumny i wiersza na planszy. W ostatnim wierszu zapisane są liczby a i b charakteryzujące ruchy skoczków, przy czym 1 ≤ a < b ≤ n-1.

Laboratorium 9 (11.12.2012): pliki tekstowe.

Zawsze sprwdzaj w programach czy udało się otworzyć plik. Po przeczytaniu/zapisaniu wszystkich danych z/do pliku zamknij go.

Zadanie 1 dla grupy wtorkowej 12-14 (15 punktów):

Część A. Napisz pierwszy program, który zapisze w pliku tekstowym kolejne liczby z trójkąta Pascala, aż do wyczerpania zakresu liczb typu long long:
    P_0,0 = 1
    P_n,0 = P_n,n = 1 dla n>0
    P_n,k = P_n-1,k-1 + P_n-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ą.

Część B. Napisz drugi program, który dla zadanych wartości n i k wypisze wartość symbolu Newtona (ⁿ_k). Wartość symbolu Newtona należy odczytać z podanego pliku tekstowego (w pliku tym zapisane będą kolejne liczby z trójkąta Pascala).
    (ⁿ_k) = ^n!/_k!·(n-k)! dla 0≤k≤n
Wartości n i k oraz nazwę pliku przekaż do programu poprzez parametry wywołania. Gdy wartość n będzie zbyt duża i danych nie będzie w pliku, należy wyświetlić odpowiedni komunikat informujący o bezradności programu w zaistniałej sytuacji.

Zadanie 1 dla grupy wtorkowej 16-18 (15 punktów):

Część A. Napisz pierwszy program, który zapisze w pliku tekstowym kolejne liczby ciągu Catalana, aż do wyczerpania zakresu liczb typu long long:
    C₀ = 1
    C_n = (⁴ⁿ⁺²/_n+2) · C_n-1   :   n≥1
Nazwę pliku przekaż do programu poprzez parametry wywołania. Każdy wyraz ciągu Catalana zapisz w oddzielnej linii.

Część B. Napisz drugi program, który dla zadanych wartości n₁, n₂,... n_k wypisze wartości wyrazów ciągu Catalana C_n1, C_n2,... C_nk. Wartości wyrazów ciągu Catalana należy odczytać z podanego pliku tekstowego (w pliku tym zapisane będą kolejne liczby ciągu Catalana).
    C_n = ^(2n)!/_n!·(n+1)! dla 0≤n
Nazwa pliku oraz wartości n₁, n₂,... n_k przekaż do programu poprzez parametry wywołania. Gdy wartość n będzie zbyt duża i danych nie będzie w pliku, należy wyświetlić odpowiedni komunikat informujący o bezradności programu w zaistniałej sytuacji.

Zadania domowe

Zadanie domowe należy przesłać na Moodla do niedzieli 16.12.2012 do godziny 21:00.

Zadanie 2 (15 punktów):

W tekstowym pliku tekstowym z rozszerzeniem .in jest zapisanych N liczb całkowitych a₀, a₁,... a_N-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 całkowite a₀, a₁,... a_N-1. Należy te liczby najpierw odczytać, zapamiętując je w dynamicznie zaalokowanej tablicy typu int[], potem posortować funkcją z biblioteki standardowej qsort() a na koniec zapisać do pliku tekstowego z rozszerzeniem .out tylko liczby pierwsze z tego ciągu w kolejności niemalejącej. Nazwę bazową dla plików (z danymi i na wyniki) przekaż poprzez parametry wywołania programu.
Uwaga. Pamiętaj, aby przed wyjściem z programu zwolnić przydzieloną wcześniej pamięć i pozamykać wszystkie pliki.

Laboratorium 10 (18.12.2012): grafika w GTK+.

Zapoznaj się z biblioteką GTK+ z funkcjami do tworzenia aplikacji okienkowych i obsługującymi graficzny interfejs użutkownika.

Zadanie 1 dla grupy wtorkowej 12-14 (15 punktów):

Stwórz aplikację okienkową używając GTK+, która będzie rozkładała zadaną liczbę całkowitą na czynniki pierwsze. Twoja aplikacja powinna zawierać pole tekstowe do wpisania liczby całkowitej (sprawdź czy udało się poprawnie przekonwertować liczbę z postaci znakowej na binarną), przycisk do uruchamiania obliczeń i etykietę do zaprezentowania wyniku.

Zadanie 1 dla grupy wtorkowej 16-18 (15 punktów):

Stwórz aplikację okienkową używając GTK+, która będzie NWD i NWW dla zadanej pary liczb całkowitych. Twoja aplikacja powinna zawierać dwa pola tekstowe do wpisania liczb całkowitych (sprawdź czy udało się poprawnie przekonwertować liczby z postaci znakowej na binarną), przycisk do uruchamiania obliczeń i etykietę do zaprezentowania wyniku.

Zadania domowe

Zadanie domowe należy przesłać na Moodla do niedzieli 23.12.2012 do godziny 21:00.

Zadanie 2 (15 punktów):

Stwórz aplikację okienkową używając GTK+, która będzie grą w kółko i krzyżyk. Użytkownik tej aplikacji ma grać z komputerem - opracuj więc jakąś prostą ale nietrywialną strategię wybierania kolejnego ruchu dla komputera. Przed rozpoczęciem rozgrywki pozwól na dokonaie wyboru, kto ma rozpocząć grę - komputer czy użytkownik. Twój program powinien też rozpoznać koniec gry i wskazywaćć zwycięzcę (albo ogłaszać remis).

Projekt programistyczny (22.01.2013).

Poniżej znajduje się lista tematów projektów programistycznych. Z listy tej każdy student wybiera sobie jeden temat i zgłosza go mailowo do zaakceptowania do piątku 21 grudnia 2012. Jeśli rozkład zgłoszonych tematów nie będzie w miarę jednostajny, to samodzielnie dokonam przydziału tematów (wówczas żadna osoba nie dostanie tego samego tematu, który zadeklarowała). Osoby, które same się nie zadeklarują, otrzymają temat projektu z góry (ode mnie). Można również zgłaszać własne propozycje projektów.

Tematy zadań projektowych:

tautologie

Napisz program badający spełnialność, sprzeczność i własność bycia tautologią w rachunku zdań 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 zbiorem liter alfabetu angielskiego. Program może operować na formule w postaci ONP. Zadaniem programu będzie sprawdzenie czy formuła wylicza się dla każdego wartościowania do wartości true (albo false), czy może dla pewnych wartościowań do wartości true a dla innych do false.

kalkulator

Napisz klakulator dla wyrażeń infiksowych (notacja tradycyjna). Kalkulator ma najpierw przekształcić wyrażenie infiksowe do postaci postfiksowej (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 i 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. kodowanie Shannona-Fano
3. LZ77 albo wariant ulepszony LZSS
4. 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 określone reguły wnioskowania i wypisuj je kolejno dla każdej umieszczanej w rozwiązaniu liczbie (w ostateczności użyj algorytmu 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ć jednak ze mną szczegółowo przedyskutowane i zatwierdzone!

Ogólne uwagi dotyczące realizacji projektu:

• Temat projektu student wybiera samodzielnie spośród zamieszczonych na powyższym wykazie. Należy jednak pamiętać, że rozkład zadań na poszczególnych studentów w grupie ma być w miarę możliwości jednostajny. Można także zgłaszać własne propozycje projektów.
• Szczegóły dotyczące zakresu prac powinny być uzgodnione ze mną jeszcze przed Bożym Narodzeniem.
• Projekty mają być wykonane samodzielnie.
• Program trzeba rozsądnie podzielić na pliki nagłówkowe i źródłowe.
• W programach należy wykorzystywać pamięć wolną (sterta) i pliki (czytanie danych, zapisywanie wyników).
• Programy mają być napisane optymalnie, z myślą o łatwych modyfikach i rozszerzeniach.
• Do projektu należy dołączyć dokumentację w postaci komentarza na początku pliku źródłowego, w którym znajduje się funkcja main(). W dokumentacji należy umieścić:
  1. imię, nazwisko i 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 22 stycznia 2013 r.

Ranking

• stan punktowy można sprawdzić w Moodlu

Instytut Informatyki