Konsultacje (pokój 339):
Adres:
Instytut Informatyki7 lutego 2013 r.
Oceny zaliczeniowe z laboratorium z ANSI C:
Chciałbym Państwu powpisywać już oceny do indeksów z laboratorium z ANSI C. Proszę się ze mną kontaktować w przyszłym tygodniu (poniedziałek lub wtorek) w trakcie godzin konsultacji albo umówić się na spotkanie w innym dogodnym terminie.
9 grudnia 2012 r.
Korekta zadania 2 z ósmej listy:
W zadaniu 2 na ósmej liście (o skoczkach na szachownicy) znalazło się niedoszacowanie. Otóż w zadaniu było napisane, że graf połączeń pomiędzy polami na szachownicy należy pamiętać w postaci macierzy sąsiedztwa; bok szachownicy mamy dany liczbą n, co daje nam n2 wierzchołków a w efekcie macierz sąsiedztwa rozmiaru n2. Skorygowałem więc rozmiar szachownicy do maksymalnie 50x50 pól. Proszę w swoich programach uwzględnić nowy maksymalny rozmiar szachownicy i zaimpementować graf w postaci macierzy sąsiedztwa.
W związku z tak późno wprowadzoną korektą do zadania, przedłużam termin jego realizacji o dwa dni, a więc do wtorku do godziny 21:00.
10 października 2012 r.
Korekta zadania 3 z pierwszej listy:
W zadaniu 3 na pierwszej liście (o odcinku AB w układzie OXY) znalazły się dwie nieścisłości. Dopisałem więc do zadania dwie uwagi (jedna dotyczy odcinków leżących na osi a druga zdegenerowanych odcinków będących punktami) oraz cztery przykłady ilustrujące te uwagi. Proszę w swoich programach uwzględnić wszytkie opisane w tych uwagach przypadki.
8 października 2012 r.
Zapisy do Moodla:
Proszę wszystkich moich studentów o jak najszybsze zapisanie się na kurs ANSI C 2012/13 w Moodlu.
1 października 2012 r.
Pierwsze laboratorium:
Pierwsze laboratorium odbędzie się w zaplanowanym terminie. Przetestujemy na nim środowisko programistyczne Code::Blocks oraz wysyłanie programów na Moodle.
1 października 2012 r.
Punkt informacyjny:
W tym miejscu będą umieszczene informacje dotyczące organizacji zajęć w moich grupach. Proszę zaglądać do ogłoszń co najmniej raz w tygodniu przed laboratorium.
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 papierowa polskojęzyczna:
Literatura papierowa anglojęzyczna:
Literatura elektroniczna polskojęzyczna:
Literatura elektroniczna anglojęzyczna:
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.
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.
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ń.
Napisz program, który wczyta współrzędne rzeczywiste dwóch punktów na
płaszczyźnie A=(x1,y1)
i B=(x2,y2), 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ć.
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
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
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ę:
*
* *
* *
* *
* *
* *
* *
* *
*
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.
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
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
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).
Napisz program, który wczyta dwie liczby naturalne n i k
a następnie wyliczy i wypisze dla tych liczb wartość symbolu Newtona
(nk).
Do wyliczenia symbolu Newtona zdefiniuj funkcję rekurencyjną zgodnie ze wzorem:
(n0) = (nn) = 1 dla n≥0
(nk) = (n-1k-1)·n/k dla 0<k<n
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.
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.
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).
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().
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).
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.
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
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
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.
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.
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.
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
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.
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.
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
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
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).
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.
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.
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:
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ą.
Część B.
Napisz drugi program, który dla zadanych wartości n i k
wypisze wartość symbolu Newtona (nk).
Wartość symbolu Newtona należy odczytać z podanego pliku tekstowego (w pliku tym
zapisane będą kolejne liczby z trójkąta Pascala).
(nk) = 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.
Część A.
Napisz pierwszy program, który zapisze w pliku tekstowym kolejne liczby
ciągu Catalana, aż do wyczerpania zakresu liczb typu long long:
C0 = 1
Cn = (4n+2/n+2) · Cn-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 n1,
n2,... nk wypisze wartości wyrazów
ciągu Catalana Cn1,
Cn2,... Cnk.
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).
Cn = (2n)!/n!·(n+1)! dla 0≤n
Nazwa pliku oraz wartości n1, n2,...
nk 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.
W tekstowym pliku tekstowym z rozszerzeniem .in jest zapisanych
N liczb całkowitych 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 całkowite a0, a1,... aN-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.
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.
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.
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).