podstawy programowania w C/C++

Celem zajęć jest nauczenie studentów podstaw programowania w języku C oraz w C++.

literatura

Literatura papierowa:

B.W.Kernighan, D.M.Ritchie: Język ANSI C. WNT, Warszawa 1994.
S.B.Lippman, J.Lajoie: Podstawy języka C++. WNT, Warszawa 2001.
C.L.Tondo, B.P.Leung: Podstawy języka C++. Ćwiczenia i rozwiązania. WNT, Warszawa 2001.
J.Grębosz: Symfonia C++ (tom 1, 2, 3). Oficyna Kallimach, Kraków 2002.
J.Grębosz: Pasja C++ (tom 1, 2). Oficyna Kallimach, Kraków 2003.

Literatura elektroniczna:

Standard ANSI C
Opis bibliotek standardowych
Steve Summit: Introductory Class Notes oraz Intermediate Class Notes
Marshall Brain: How C Programming Works
Steven Holmes: C Programming
Robert Chwastek: Język C

powrót na początek strony

ogłoszenia

6-01-2008: Zadanie 4 oraz do wyboru zadanie 2 albo 3 z listy 5 będzie można oddać na następnych zajęciach za połowę punktów.
2-12-2007: Zadanie 2 albo 3 do wyboru z listy 4 będzie można oddać na następnych zajęciach za połowę punktów.
25-11-2007: Zadania 2 i 3 z listy 3 będzie można oddać na następnych zajęciach za połowę punktów.
20-10-2007: W tym miejscu będą się pojawiały ważne ogłoszenia związane z zajęciami i zadaniami z przedmiotu podstawy programowania w C/C++ adresowane do studentów z moich grup (1ZA, 1ZB, 1ZC).

terminy

laboratorium 1:

1ZA, 21-10-2007, 12:00
1ZB, 21-10-2007, 15:10
1ZC, 21-10-2007, 13:40

laboratorium 2:

1ZA, 28-10-2007, 12:00
1ZB, 28-10-2007, 13:40
1ZC, 28-10-2007, 15:10

laboratorium 3:

1ZA, 25-11-2007, 15:10
1ZB, 25-11-2007, 13:40
1ZC, 25-11-2007, 16:40

laboratorium 4:

1ZA, 2-12-2007, 12:00
1ZB, 2-12-2007, 09:00
1ZC, 2-12-2007, 10:30

laboratorium 5:

1ZA, 6-01-2008, 10:30
1ZB, 6-01-2008, 12:00
1ZC, 6-01-2008, 09:00

laboratorium 6:

1ZA, 13-01-2008, 12:00
1ZB, 13-01-2008, 09:00
1ZC, 13-01-2008, 10:30

laboratorium 7:

1ZA, 19-01-2008, 12:00
1ZB, 19-01-2008, 09:00
1ZC, 19-01-2008, 10:30

powrót na początek strony

zasady zaliczania przedmiotu

ogólnie:: W semestrze będzie opublikowanych (na tej stronie) 7 list z zadaniami. Zadania będą publikowane w internecie w dniu, w którym odbywają się zajęcia. Za każde poprawnie zaprogramowane zadanie będzie można otrzymać 10 punktów (wybrane zadania będzie można oddawać na kolejnych zajęciach za 5 punktów).
obecności:: Zadania do zaprogramowania będą ogłaszane tuż przed zajęciami, dlatego obecność na zajęciach jest obowiązkowa. Jeśli ktoś nie zaliczy na zajęciach żadnego zadania, to będzie to potraktowane jak nieobecność. Warunkiem koniecznym zaliczenia przedmiotu jest aktywna obecność na co najmniej 5 laboratoriach.
prezentacje:: Zadania należy realizować i prezentować w czasie trwania pracowni. Kto nie zdąży, nie może już oddawać zadań zrobionych w domu w terminie późniejszym. Za zrobione na pracowni zadanie można dostać co najwyżej określoną przy zadaniu liczbę punktów (ze skokiem co 1). W trakcie prezentacji programu trzeba się liczyć z pytamiami dotyczącymi zadania: metoda rozwiązania, zastosowane konstrukcje językowe, itp.
oceny:: Aby zaliczyć laboratorium na ocenę dostateczną trzeba do końca semestru zdobyć 40% spośród możliwych do zebrania punktów (za zadania treningowe i zwykłe, nie licząc zadań nadobowiązkowych); na ocenę bardzo dobra trzeba będzie zgromadzić 80% punktów; oceny pośrednie pozostają w liniowej zależności od przedstawionych wymagań granicznych.

laboratorium

laboratorium 1: pisanie na standardowym wyjściu, czytanie ze standardowego wejścia.

(zadanie treningowe)
Dane jest równanie liniowe postaci ax+b=0 . Napisz program, który wczyta dwie liczby rzeczywiste a≠0 i b będące parametrami tego równania, a następnie wyliczy i wypisze jego rozwiązanie z dokładnością do 3 miejsc po kropce dziesiętnej.
Napisz program, który wczyta liczbę całkowitą oznaczającą kod znaku i wydrukuje w sposób estetyczny znak ASCII o podanym kodzie oraz kod tego znaku w postaci szestanstkowej.
Uwaga:
Widoczne znaki ASCII mają kody z zakresu od 32 do 126.
(zadanie nadobowiązkowe)
Napisz program, który wczyta liczbę rzeczywistą i wydrukuje pierwiastek z tej liczby z dokładnością do 9 miejsc po kropce dziesiętnej oraz kwadrat i sześcian tej liczby.
Uwaga:
Można pierwiastkować tylko liczby nieujemne.
(zadanie nadobowiązkowe)
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 obliczeń.

laboratorium 2: instrukcja warunkowa, instrukcja wyboru, instrukcje pętli.

(zadanie treningowe)
Napisz program, który wypisze w słupku kolejne potęgi 2 zaczynając od 2⁰ a kończąc na 2^-10. Kropki dziesiętne mają się znajdować w tej samej kolumnie dla wszystkich wypisywanych liczb. Nie należy wypisywać nieznaczących zer pojawiających się na końcu liczby.
Uwaga:
Zabezpiecz się przed wczytaniem nieprawidłowego parametru (liczby mniejszej od 1 albo napisu którego nie można przekształcić na liczę).
Napisz program, który wczyta liczbę naturalną n a następnie obliczy i wypisze sumę sześcianów 1³ + 2³ + ... + n³.
Uwaga:
Zabezpiecz się przed wczytaniem nieprawidłowego parametru (liczby mniejszej od 1 albo napisu którego nie można przekształcić na liczę).
Uwaga:
Istnieje wzór na sumę sześcianów: 1³ + 2³ + ... + n³ = (n(n+1))² / 4, ale twoim zadaniem jest zaprogramowanie tych obliczeń w pętli for (później możesz sprawdzić, czy otrzymany wynik zgadza się z wartością wyliczoną bezpośrednio ze wzoru).
(zadanie nadobowiązkowe)
Napisz program, który wczyta ze standardowego wejścia wszystkie znaki, aż do napotkania symbolu EOF. Na końcu program powinien wypisać na standardowym wyjściu dla błędów statystykę dotycząca wczytanego tekstu: ile było wszystkich przeczytanych znaków, ile w tym tekście wystąpiło liter, ile cyfr i ile znaków przestankowych (kropek, przecinków, itp).
Uwaga:
Do zliczania znaków przestankowych posłuż się instrukcją wyboru switch.
(zadanie nadobowiązkowe)
Napisz program, który wczyta trzy liczby całkowite a, b i c a następnie wyznaczy i wypisze wartość środkową (medianę).
Uwaga:
Zabezpiecz się przed wczytaniem nieprawidłowych parametrów (danych których nie można przekształcić na liczy).

laboratorium 3: funkcje, rekurencja; pliki nagłówkowe i źródłowe.

(zadanie treningowe)
Napisz program, który wczyta liczbę naturalną n a następnie wyliczy i wypisze wartość n!. Do wyliczenia silni n! = n·(n-1)·(n-2)...2·1 zdefiniuj osobne funkcje, jedną iteracyjną a drugą rekurencyjną. W swoim programie wykorzystaj obie funkcje. Dodatkowo zabezpiecz program przed podaniem nieprawidłowych danych.
Uwaga:
Podziel program na pliki nagłówkowe i źródłowe.
Napisz program, który wczyta liczbę naturalną p a następnie sprawdzi czy jest to liczba pierwsza i wypisze odpowiedni komunikat. Do testowania pierwszości liczby zdefiniuj osobną funkcję iteracyjną. Dodatkowo zabezpiecz program przed podaniem nieprawidłowych danych.
Uwaga:
Podziel program na pliki nagłówkowe i źródłowe.
Napisz program, który wczyta dwie liczby naturalne p i r a następnie wyliczy i wypisze wartość p^r. Do wyliczenia potęgi p^r zdefiniuj osobną funkcję rekurencyjną, implementującą algorytm szybkiego potęgowania. Dodatkowo zabezpiecz program przed podaniem nieprawidłowych danych.
Uwaga:
Podziel program na pliki nagłówkowe i źródłowe.
(zadanie nadobowiązkowe)
Napisz program, który wczyta liczbę naturalną n a następnie wyliczy i wypisze wartość n-tego wyrazu w ciągu Fibonacciego F_n. Do wyliczenia n-tego wyrazu w ciągu Fibonacciego zdefiniuj osobne funkcje, jedną iteracyjną a drugą rekurencyjną, zgodnie z wzorem:
F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2 dla n≥2
W swoim programie wykorzystaj obie funkcje. Dodatkowo zabezpiecz program przed podaniem nieprawidłowych danych.
Uwaga:
Podziel program na pliki nagłówkowe i źródłowe.

laboratorium 4: tablice znakowe.

(zadanie treningowe)
Napisz program, który wczytuje do tablicy znakowej napis ze standardowego wejścia i sprawdza, czy jest on palindromem.
Uwaga: Napisz oddzielną funkcję, która będzie sprawdzać, czy napis jest palindromem; funkcja ta nie powinna rozróżniać małych i wielkich liter.
Uwaga: Wczytany napis ma mieć nie więcej niż 79 znaków.
Wskazówka: Palindrom to napis, który ma to samo znaczenie niezależnie od tego, czy czytamy go normalnie czy wspak. Przykładowe znane palindromy w języku polskim to: Kajak, Anna, KobyłaMaMałyBok, ZakopaneNaPokaz, MożeJutroTaDamaDaTortuJeżom.
Napisz program, który wczytuje do tablicy znakowej napis ze standardowego wejścia i sprawdza, czy zawiera on dwie takie same litery obok siebie.
Uwaga: Napisz oddzielną funkcję, która będzie sprawdzać, czy napis zawiera dwie takie same litery obok siebie:
int para (char *str);
Uwaga: Wczytany napis ma mieć nie więcej niż 79 znaków.
Napisz program, który wczyta pojedyncze słowo do tablicy znakowej. Następnie program ma odwrócić ten napis i wypisać go (pierwotny napis powinien być wypisany wspak).
Uwaga: Napisz oddzielną funkcję, która będzie odwracać napis wewnątrz tej samej tablicy:
void odwroc (char *str);
Uwaga: Wczytany napis ma mieć nie więcej niż 79 znaków.
(zadanie nadobowiązkowe)
Napisz program, który przepisze tekst ze standardowego wejścia na standardowe wyjście i w trakcie działania przytnie długie linie do 40 znaków.
Wskazówka: Skorzystaj z funkcji fgets().

laboratorium 5: alokowanie i zwalnianie pamięci na stercie.

(zadanie treningowe)
Napisz program, który wczyta dwie dodatnie liczby całkowite N i Z, a następnie wygeneruje N losowych liczb ze zbioru {0,1,...,Z-1} z rozkładem jednostajnym. Liczby te należy umieścić w dynamicznie przydzielonej tablicy. Program ma wypisać wszystkie wylosowane liczby, potem posortować je korzystając z funkcji standardowej qsort() i na koniec wypisać znowu te liczby w kolejności niemalejącej.
Uwaga: Do losowania liczb całkowitych z podanego zakresu zdefiniuj osobną funkcję:
int losuj (int pocz, int kon);
Uwaga: Twój program powinien na końcu zwolnić przydzieloną pamięć.
Napisz program, który wczyta dodatnią liczbę całkowitą N, a następnie wygeneruje losowo N-elementową permutację (wymieszany ciąg liczb od 0 do N-1); zadbaj o to, by każda permutacja mogła być wylosowana z jednakowym prawdopodobieństwem. Ciąg liczb od 0 do N-1 należy zapamiętać w dynamicznie przydzielonej, potem dokonać losowej permutacji a na koniec wypisać ją.
Uwaga: Do losowania liczb całkowitych z podanego zakresu zdefiniuj osobną funkcję:
int losuj (int pocz, int kon);
Uwaga: Do przeprowadzenia losowej permutacji ciągu zdefiniuj osobną funkcję:
void permutuj (int *tab, int n);
Uwaga: Twój program powinien na końcu zwolnić przydzieloną pamięć.
Napisz program, który wczyta dodatnią liczbę całkowitą N a potem ciąg N liczb rzeczywistych A₀, A₁, ..., A_N-1. Liczby te należy umieścić w dynamicznie przydzielonej tablicy. Następnie program ma wyliczyć i wypisać średnią arytmetyczną oraz wartość minimalną i maksymalną spośród liczb we wczytanym ciągu.
Uwaga: Do obliczenia średniej aytmetycznej z podanego ciągu oraz do wyznaczenia wartości najmniejszej i największej zdefiniuj osobne funkcje:
double srednia (int n, double *tab);
double miminum (int n, double *tab);
double maksimum (int n, double *tab);
Uwaga: Do poruszania się po tablicy zastosuj wskaźniki.
Uwaga: Twój program powinien zwolnić na końcu przydzieloną pamięć.
(zadanie nadobowiązkowe)
Napisz program, który wczyta dodatnią liczbę całkowite N a potem N łańcuchów znakowych S₀, S₁, ..., S_N-1. Każdy łańcuch należy umieścić w dynamicznie przydzielonej tablicy znakowej. Wskaźniki do łańcuchów także należy pamiętać w dynamicznie przydzielonej tablicy rozmiaru N. Następnie program ma posortować wczytane łańcuchy korzystając z funkcji standardowej qsort() a na koniec wypisać je w kolejności leksykograficznej.
Wskazówka: Wystarczy posortować wskaźniki do łańcuchów znakowych.
Uwaga: Do poruszania się po tablicy zastosuj wskaźniki.
Uwaga: Twój program powinien zwolnić na końcu przydzieloną pamięć.

laboratorium 6: operacje na plikach.

(zadanie treningowe)
Napisz program, który wczyta ze standardowego wejścia nazwę pliku tekstowego, a następnie zapisze w tym pliku kolejne liczby ciągu Fibonacciego (F₀ = 0, F₁ = 1, a dla n>1 korzystamy ze wzoru F_n = F_n-1 + F_n-2), aż do wyczerpania zakresu liczb typu unsigned long. Każdą liczbę zapisz w oddzielnej linii. Plik należy napierw otworzyć do pisania, potem zapisać w nim kolejne liczby wspomnianego ciągu, a na końcu zamknąć go.
Wskazówka: Posłuż się funkcją fprintf().
W tekstowym pliku z danymi jest zapisanych N liczb rzeczywistych a₀, a₁, ..., a_N-1. Zawartość pliku z danymi jest następująca: w pierwszej linii jest zapisana liczba całkowita N typu int, a w kolejnych liniach pooddzielane białymi znakami wartości rzeczywiste a₀, a₁, ..., a_N-1 typu double. Należy te liczby odczytać, zapamiętując je w dynamicznie zaalokowanej tablicy. Na koniec trzeba je przepisać do pliku binarnego (bez wartości N na początku) i zwolnić przydzieloną pamięć.
Uwaga: Nazwę pliku/plików przekaż poprzez parametry wywołania programu.
Wskazówka: Posłuż się funkcją fscanf() i fwrite().
(kontynuacja poprzedniego zadania)
W binarnym pliku z danymi jest zapisane są liczby typu double. Określ ile tych liczb jest zapisanych w pliku, przydziel dynamicznie odpowiedni obszar pamięci i wczytaj je tam. Następnie policz i wypisz na standardowym wyjściu średnią arytmetyczną z tych liczb. Na końcu zwolnij przydzieloną pamięć.
Uwaga: Nazwę pliku przekaż poprzez parametry wywołania programu.
Wskazówka: Posłuż się funkcją fread().
(zadanie nadobowiązkowe)
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. Nazwy plików mają być podawane jako argumenty wywołania programu. 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.
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 7: egzamin ustny

podstawowe typy danych
operatory (arytmetyczne, bitowe, logiczne i relacyjne) i wyrażenia
deklaracje zmiennych i ich inicjalizacja
tablice
arytmetyka wskaźników
instrukcje sterujące (instrukcja warunkowa if, instrukcja wyboru switch, pętle for, while i do-while, skoki)
funkcje, ich argumenty i zwracane wartości, rekurencja
dyrektywy prekompilatora
pliki źródłowe i nagłówkowe
struktury i unie
przydzielanie i zwalnianie pamięci dynamicznej
operacje na plikach (otwieranie, zamykanie, czytanie i pisanie tekstowe i binarne)

zadania nadobowiązkowe:

W pliku nagłówkowym 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 wskaźnik do tablicy znakowej z napisem:
struct Element
{
Element *lewe, *prawe;
char *wartosc;
};
Oprócz struktury zadeklaruj również funkcje wstaw() (wstawienie nowego elementu do drzewa), ile() (policzenie ile jest elementów w drzewie) oraz wypisz() (wypisanie kolejno wszystkich wartości zapamiętanych w drzewie w porządku inorder, czyli uporządkowane leksykograficznie). Pierwszym argumentem każdej z tych funkcji powinien być wskaźnik na korzeń drzewa lub poddrzewa. Dalej, w oddzielnym pliku źródłowym zdefiniuj wymienione funkcje (zaimplementuj je rekurencyjnie).
(kontynuacja poprzedniego zadania)
W tekstowym pliku z danymi jest zapisanych N łańcuchów znakowych s₀, s₁, ..., s_N-1. Zawartość pliku z danymi jest następująca: w pierwszej linii jest zapisana liczba całkowita N typu int, a w kolejnych N liniach napisy s₀, s₁, ..., s_N-1 typu char[] (każda linia to jeden łańcuch). Należy te łańcuchy odczytać, umieszczając je w drzewie BST (jeśli jakieś napisy się powtarzają, to nie umieszczaj ich wielokrotnie w drzewie). Na koniec trzeba wypisać na standardowe wyjście w porządku leksykograficznym wszystkie zapamiętane drzewie BST napisy i zwolnić przydzieloną pamięć.
Uwaga: Nazwę pliku z danymi przekaż poprzez parametry wywołania programu.
Uwaga: Zakładamy, że długość pojedynczego łańcucha znakowego nie przekracza 255 znaków.
Wskazówka: Posłuż się funkcją fgets() przy czytaniu napisów z pliku.
Wskazówka: Każdy napis w drzewie BST powinien być umieszczony w dynamicznie zaalokowanej tablicy znaków.

ranking

Punktacja z laboratoriów:

powrót na początek strony