Konsultacje

Jeśli zaistaniała by taka potrzeba to po uprzednim kontakcie mailowym. Raczej nie do południa.

Warunki zaliczenia

• 30% Kartkówki (obowiązuje materiał z poprzednich ćwiczeń/wykładów (zazwyczaj tych bezpośrednio poprzedzających zajęcia))
• 20% Program1 (prezentacja na zasadzie code-review projekt)
• 20% Program2 (tak samo)
• 30% ProgramZaliczeniowy (to samo ale niepublicznie)

Metoda oddawanie projektów

Zakładam, że program wraz z ewentualnym makefile`em jest w kataolgu \(prog1\)

tar -cf program1.tar prog1

Uwaga! Przed spakowaniem katalogu należy usunąć z niego plik wykonywalny (skompilowany program).

Można dodatkowo spakować:

bzip2 program1.tar

Dopiero tak spakowaną paczkę należy przesłać jako rozwiązanie.

Update 1

Ze względu na szereg przesunięc w zajęciach i dopasowanie się do poziomu uśrednionego poziomu problemów na ćwiczeniach, code-review zostanie zmieniony na projekty czyli po prostu większe prace domowe.

Aby zaliczyć projekt (warunki konieczne):

• program musi się kompilować
• program musi rozwiązywać zagadnienie/problem
• program musi być napisany samodzielnie

Aby otrzymać lepszą ocenę (warunki dodatkowe):

0. sprecyzowane w zadaniu
1. program powinien być podzielony na funkcje realizujące poszczególne części
2. kompliacja programu nie powieninna zwracać warningów (przy użyciu flag -W -Wall --ansi)
3. program powinien być opatrzony licznymi komentarzami
4. program może mieć dołączonego makefile`a
5. program może wykorzystywać bilioteki systemowe lub rozwiązania z poprzednich projektów

Dobre nawyki

Katalogi i nazwy plików

• Każdy program, zestaw programów należy trzymać w osobnym katalogu.
• Nazwy powinny oddawać to co jest w programie. System linux dopuszcza do użytku bardzo długie nazwy - korzystaj z tego!
• Nazwy plików źródłowy kończymy .c - większość edytorów od razu zorientuje się, że to język C i pokoloruje składnię.

Nazwy zmiennych/funkcji

• CamelCase jest dobrym przydatnym nawykiem
• Nazwy zmiennych powinny być opisowe - oszczędzamy swój własny czas w przyszłości!!!
• Używanie przedrostków (w dużych kodach) opisujące rodzaj/typ zmiennej.

Komentarze, komentarze, komentarze

Po prostu należy być przyzwoitym i je pisać.

Niektóre informacje z wykładu

Minimalny program w języku C wygląda dość skromnie: ## Minimalny, program

main()
{
}

Struktura programu

Jest tylko jeden obowiązkowy element programu:

• Funkcja main

Z dodatków zamieniających programy w coś przydatnego:

• Instrukcje dla preprocesora (poprzedzone znakiem #)
• Deklaracje/definicje funkcji
• Deklaracje zmiennych
• Operacje (pętle/warunki)

Najprostszy program

#include<stdio.h>

int main()
{
    printf("Witaj szary Świecie!\n");
    return 0;
}

Komentarze

W C (konkretniej dla współczesnych kompilatorów C) mamy trzy możliwość:

//wszystko za slashami jest komentarzem

/* wszystko pomiędzy jest komentarzem */
/* mogą być
wieloliniowe */
/* ale nie mogą być zagnieżdżone */

#if 0
//można tak wyłączyć szybko duży blok kodu wraz z komentarzami
int a;
int b;
a=2;
for(b=0;b<10;b++) printf("Bezsensowna pętla\n");
//nie można ich zagnieżdżać 
#endif

Kompilacja

gcc -o <nazwa_programu_po_kompilacji> <nazwa_pliku_źródłowego>

Makefile

Przykładowy Makefile kompilujący kod.c do programu exe

all:
    gcc -o exe kod.c

Teraz wystarczy wpisać make i zostanie wykonana kompilacja.

Instrukcja warunkowa

if( <warunek> )
{
//blok instrukcji
}

if( <warunek> )
{

}
else 
{
//ten blok instrukcji zostanie wykonany gdy <warunek> jest fałszem.
}

if( <warunek1> )
{
//jeśli warunek1 jest prawdą wykonaj
}
else if ( <warunek2> ) //jeśli warunek1 nie jest prawdą sprawdź warunek2
{

}
else if ( <warunek3> ) //jeśli warunek2 nie jest prawdą sprawdź warunek3
{

}
else
{
//jeśli warunek3 nie jest prawdą wykonaj ten blok

}

Pętle

Pętla for

for( <instrukcjaPrzedFor> ; <warunekIstnieniaPętli> ; <instrukcjaPoZakończeniuBloku> )
{
//blok instrukcji
}

Pętla while

while( <warunkeIstnieniaPętli> )
{
//blok instrukcji
}

Pętla do-while

do
{
//blok instrukcji
}
while( <warunekIstnieniaPętli> );

Typy

Typy całkowite

Znaki

Typy zmiennoprzecinkowe

void

Funkcje

/*Deklaracja funkcji*/
int Funkcja(int a);

/*Definicja funkcji*/
int Funkcja(int a)
{
    return a*a;
}

Obowiązkową cześć jest definicja funkcji (pełni ona również rolę deklaracji jeśli taka nie wystąpiła).

Deklaracja (lub cała treść (definicja)) funkcji musi wystąpić PRZED użyciem tej funkcji.

#include<stdio.h>

int Funkcja(int a)
{
    return a*a;
}

int main()
{
    printf( "%d\n", Funkcja(16) );
    return 0;
}

lub:

#include<stdio.h>
//Deklaracja
int Funkcja(int a);

int main()
{
    printf( "%d\n", Funkcja(16) );
    return 0;
}

//Definicja
int Funkcja(int a)
{
    return a*a;
}

Jaki błąd zwróci komilator jeśli w tym wypadku pominiemy deklarację a jaki jeśli pominiemy definicję?

Jeśli kompilator nie zwraca żadnych, błędów skompiluj program z następującymi flagami:

> gcc -o exe funkcje.c -W -Wall -ansi

Deklaracja funkcji

Niektóre funkcje ze stadardowej biblioteki

printf

Tablice

Statyczne

Deklaracja:

<typ> nazwa[rozmiar];

Przykłady:

char znaki[256];
int liczby[100];

Zapisanie liczby w pierwszym elemencie tablicy i wypisanie go na ekran:

int tab[10];
tab[0]=178;
printf("%d\n",tab[0]);

Wczytanie ze standardowego wejścia do piątego elementu tablicy:

int tab[19];
scanf("%d", &(tab[4]) );

Zadania na ćwiczenia

3.1 Parzystość

Napisz funkcję o następującej deklaracji:

int CzyParzysta(int Liczba);

która sprawdza czy liczba całkowita Liczba jest parzysta.

Jeśli jest zwróć wynik 1. A 0 w przeciwnym wypadku.

3.2 Podzielność

Napisz funkcję o następującej deklaracji:

int CzyPodzielna(int Liczba, int Przez);

która sprawdza czy liczba całkowita Liczba jest podzielna przez liczbę całkowitą Przez.

3.3 Liczby Fibbonaciego

Napisz funkcję o następującej deklaracji:

int Fibonacci(int Numer);

która oblicza i zwraca liczbę Fibonacciego o zadanym numerze.

Jaka jest maksymalna liczba Fibonacciego którą można zapisać przy użyciu typu int? Jak wykazać to empirycznie?

3.4 Szyfr Cezara (wersja 2)

Wykorzystaj kawałek kodu

#include<stdio.h>

int main()
{
    char litera;
    while(scanf("%c",&litera) == 1)
    {
        printf("%c",litera);
    }
    return 0;
}

Napisz dwa programy jeden do zaszyfrowania a drugi do odszyfrowywania.

Program ma wykorzystywać funkcję Przesun o następującej deklaracji:

char Przesun(char Litera, int Przesuniecie);

Która przesuwa znak z następującymi regułami (jeśli na przykład Przesuniecie==1):

• a -> b
• z -> a
• A -> B
• Z -> A
• 0 -> 1
• 9 -> 0

Podpowiedź: wykorzystaj dzielenie modulo aby poruszać wewnątrz podzbiorów (małe litery, duże litery, liczby).

Aby zaszyfrować plik list.txt i zapisać wynik w zaszyfrowany_list.txt można użyć przekierowania w powłoce (bash, tcsh, ...):

> ./program < list.txt > zaszyfrowany_list.txt

Gdy testujemy program z klawiatury, aby przerwać jego działanie można użyć kombinacji klawiczy ctrl + c.

3.5 Zliczanie białych znaków

Wykorzystaj wiedzę zdobytą przy okazji zadania 3.5 i napisz program który zlicza biłe znaki.

Białe znaki to:

• ' ' - spacje
• '\n' - znaki końca linii
• '\t' - tabulatory

3.6 Badanie podzielności

Napisz program który wczytuje liczby całkowite ze standardowego wejścia, sprawdza ich podzielność przez 2,3,4,...,9 i komunikuje ten fakt na standardowe wyjście.

Przykładowa treść wejścia to:

1
2
15
-16

Wyjście w tym wypadku powinno być mniej więcej takie:

Liczba 1 Podzielna przez 
Liczba 2 Podzielna przez 2
Liczba 15 Podzielna przez 3 5 
Liczba -16 Podzielna prze 2 4 8

4.1 Wypełnianie/wypisywanie statycznej tablicy

Zdeklaruj statyczną tablicę liczb całkowitych o rozmiarze 10. Wypełnij ją w pętli liczbami od 5 do 14. Wypisz na standardowe wyjście elementy tablicy.

4.2 +wyodrębnione funkcje

W programie z 4.1 wyodręnij funkcje o następujących deklaracjach:

int Wypelnij(int *tab, int rozmiar, int ndanych);

Która wypełnia, przekazaną przez wskaźnik tab, tablicę (o rozmiarze rozmiar) i zwraca 0 jeśli wszystko przebiegło w poprawnie a 1 gdy ndanych było więcej niż rozmiar tablicy. Wypełniane jest pierwsze ndanych elementów.

void Wypisz(int *tab, int ndanych);

Która wypisuje na standardowe wyjście elementy tablicy.

4.3 +funkcja do wczytywania danych

Dodaj do programu kolejną funkcję:

int Wczytaj(int *tab, int rozmiar, int ndanych);

Która w odróżnieniu od Wypelnij wczytuje dane ze standardowego wejścia. Obsługa błędu tak samo jak w Wypelnij.

4.4 Sprawdzanie podzielności danych

Dopisz funkcję sprawdzającą podzielność przez 5. I napisz program który sprawdzi podzielność danych (wczyta je ze standardowego wejścia i wypisze podzelności na wyjście).

Format wejścia ma być następujący:

n
a1
a2
(...)
an

Gdzie n to liczba danych do wczytania (liczba całkowita od 0 do 100) a a1,..,an to dane (liczby całkowite).

Przykładowe wejście:

3
5
15
14

I wyjście dla tych danych:

1
1
0

5.1 Iloczyn skalarny wektorów

Napisz funkcję obliczającą ilocz skalarny wektorów.

float Skalarny(float *A, float *B);

Użyj jej w programie który wczyta dwa wektory ze standardowego wejścia

1.3 1.5 0.
0. 2. 1.

i zwróci na standardowe wyjście wynik:

3.

5.2 Iloczyn wektorowy

Napisz funkcję obliczającą iloczyn wektorowy wektorów.

void Wektorowy(float *A, float *B, float *Wynik);

Użyj jej w programie. Przykłądowe wejście:

1. 0. 0.
0. 1. 0.

Wyjście:

0. 0. 1.

5.3 Normalizacja wektora

Napisz funkcję:

void Normalizacja(float *A);

normalizującą wektor.

Użyj jej w programie.

Przykładowe wejście:

2. 0. 0.

Wyjście:

1. 0. 0.

5.4 Zamiana

Napisz funkcję:

void Swap(float *a, float *b);

zamieniającą miejscami wartości zmiennych.

5.5 Sortowanie

Napisz funkcję:

void Srotuj(float *A);

która posortuje tablicę danych. Wykorzystaj funkcję swap.

Napisz program który sortuje dane.

Wejście

n
a1
a2
...
an

Przykład wejścia

3
4.5
1.2
-4

Wyjście

-4
1.2
4.5

7.1 Wskaźniki

UWAGA W programie warto napisać bardzo dokładne komentarze (wręcz przekleić treść)! Program stanie się swego rodzaju ściągawką podczas dalszej nauki c/c++.

Napisz program pointers, który robi następujące rzeczy (w kolejności):

1. Deklaruje dwie zmienne typu float o dowolnych nazwach (np. a i b)
2. Deklaruje dwa wskaźniki na zmienne typu float (np. a_ptr i b_ptr)
3. Wskazuje a_ptr obszar pamięci a. "Wskazuje a_ptr na a."
4. To samo dla b, b_ptr
5. Przypisuje zmiennej a wartość (wedle fanaberii).
6. Przypisuje zmiennej b wartość przy użyciu b_ptr
7. Wypisuje na ekran wartości a i b (używając zmiennych a i b).
8. Wypisuje adresy a i b (używając zmiennych a i b).
9. Wypisuje na ekran wartości a i b (używając wskaźników a_ptr i b_ptr).
10. Wypisuje adresy a i b (używając zmiennych a_ptr i b_ptr).
11. Wypisuje adresy a_ptr i b_ptr.
12. Deklaruje zmienna c odpowiedniego typu i zapisuje w niej wartość a przy pomocy wskaźnika a_ptr
13. Deklaruje wskaźnik d_ptr odpowiedniego typu, który wskazuje na zmienną b
14. Przy pomocy d_ptr podwaja wartość zmiennej b
15. Wypisuje na ektran wartosć c i b

Przy okazji...

Aby ćwiczenie stało się uniwersalne w skali c/c++ należy uzupełnić je o referencję. Np. tworząc referencję do c i podglądając jej wartość/adres. Oczywiście to wymaga skorzystania z innego kompilatora... ;)

7.3 Arytmetyka wskaźników.

Napisz program morepointers a w nim:

1. Zdeklarują globalną stałą liczbową size o wartości 8.
2. Utwórz statyczną tablicę tab o wielkości size zmiennych typu int
3. Wypełnij w dowolny sposób tablicę liczbami (np. przy deklaracji, w pętli, ...)
4. Nie używając operatora tablicowego [] zmień pierwszy, trzeci i ostatni element tab przemnażając go przez 4.
5. Uwtórz dwa wskaźniki (p i q) na typ int
6. Wskaż nimi na dwa dowolne elementy tab
7. Wypisz ich wzajemną odelgłość
8. Wypisz elementy tablicy (bez użycia operatora [])

8.1 Struktury i liczby zespolone

Używając deklaracji struktury i typu:

struct SZespolona
{
    float Re;
    float Im;
};

typedef struct SZespolona TZespolona;

Zaimplementuj funkcje operujące na liczbach zespolonych:

Funkcję obliczającą moduł:

float Modul(TZespolona A);

Funkcje zwracające część rzeczywistą/urojoną:

float Im(TZespolona A);
float Re(TZespolona A);

Funkcje dodające/odejmujące i mnożące dwie liczby zespolone:

TZespolona Dodaj(TZespolona A, TZespolona B);
TZespolona Odejmij(TZespolona A, TZespolona B);
TZespolona Pomnoz(TZespolona A, TZespolona B);

9.1 Dynamiczna alokacja pamięci i sortowanie

Do zaalokowania (zarezerwowania) służy komenda (między innymi - patrz strona 336 podręcznika) malloc. Używamy jej następująco:

Najpierw tworzymy wskaźnik do którego będzie dopięta nasza tablica:

double *pfDane; //liczby zmienno przecinkowe
int *pnLiczby; //albo może liczby całkowite

Następnie prosimy komputer o zarezerwowanie pamięci na, powiedzmy, n = 100 obiektów odpowiedniego typu. W celu dowiedzenia się ile bajtów zajmuje dany typ, możemy posłużyć się np. naszą wiedzą albo funkcją sizeof. Do trzymania długości tablicy "kanonicznie" używa się typu size_t - zazwyczaj jest to long long int.

int n = 100;
size_t nRozmiarDane = n*sizeof(double); //zamiast typu, argumentem sizeof może też być zmienna
size_t nRozmiarLiczby = n*sizeof(int); 

pfDane = (double*)malloc(nRozmiarDane);
pnLiczby = (int*)malloc(nRozmiarLiczby);

Gdyby nie udało się zaalokować danego obszaru pamięci (powodów może być bardzo dużo), funkcja malloc zwróci aders NULL. Czyli sprawdzenie polegało by na:

if((pfDane == NULL) || (pnLiczby == NULL))
{
    printf("nie udalo zarazerowac sie pamieci ktoregos z obszarow\n");
    exit(EXIT_FAILURE); 
}

Po zakończeniu używania dynamicznych tablic, należy zwolnić obszar przez nie zajmowany:

free(pfDane);
free(pnLiczby);

Zadanie polega na posortowaniu n liczb podanych następująco:

n
a1
a2
a3
...
an

Używając tablicy dynamicznej.

Wynikiem powinno być lista posortowanych liczb.

Przykład. In:

3
2
5
2

Out:

2
2
3

Projekty

Seria końcowa na 10.06.2016 (termin nieprzekraczalny)

Sortowanie liczb zespolonych

Napisz program który posortuje n liczb zespolonych po ich module, części rzeczywistej lub urojonej. Wejście:

t
n
re1 im1
re2 im2
...
ren imn

gdzie t to typ sortowania (0 - po module, 1 - po części rzeczywistej, 2 - poczęści urojonej), n to liczba danych.

Danych może być dużo także należy użyć dynamicznej alokacji pamięci.

Program ma wykorzystywać strukturę podobną do tej z zadania 8.1

Seria na 13.05.2016 (Max 27.05.2016 12:00)

Sortowanie wektorów

Napisz program który posortuje n wektorów po ich długości. Program powinien (pełna ocena) wykorzystywać funkje takie jak w 5-tej serii ćwiczeń.

Wejście:

n
x1 y1 z1
...
xn yn zn

n liczba całkowita - ilość wektorów (nie większa niż 20).

xi yi zi liczby zmienno przecinkowe - współrzędne wektora.

Wyjście:

wx1 wy1 wz1
...
wxn wyn wzn

Przykładowe wejście:

4
1. 3. 5.
1. 3. 8.
0. 5. 0.
1. 0. 0.

Przykładowe wyjście:

1. 0. 0.
0. 5. 0.
1. 3. 5.
1. 3. 8.

Ciekawostka

Filmik o sortowaniu

Podpowiedz

Jeśli zastanawiacie się jak można zapisać wiele wektorw w jednowymiarowej tablicy - proponuję następującą podpowiedź... Zapisać je jeden za drugim. ;]

//pojemnik dla 4 wektorów
float Dane[12];

Czyli kolejne komórki pamięci wyglądały by ta

Dane[0] - to x0
Dane[1] - to y0
Dane[2] - to z0
Dane[3] - to x1
Dane[4] - to y1
Dane[5] - to z1
itd.

Jeśli mięliśmy dowolną funkcję wykorszystującą wektor jako tablicę o długości 3. Np.:

float ZwrocXWektora(float *Wektor)
{
    return Wektor[0];
}

To przesuwając wskaźnik początku tablicy, możemy dostarczy do funkcji kolejne wektory:

float Dane[6] = {0. , 2. , 5.,
                 7. , 3. , 4. };

printf("Xowa wspolrzedna %d-go wektora to %f\n", 0, ZwrocXWektora(Dane));
printf("Xowa wspolrzedna %d-go wektora to %f\n", 1, ZwrocXWektora(Dane+3));

Korzystając z takiego układu wektórw w pamięci, proponuję następującą podpowiedź do zadania:

//Funkcja dlugosc oblicza dlugosc wektora
//Wejsciem jest tablica o co najmniej rozmiarze [3]
//Wykorzystuje funkcje obliczajaca iloczyn skalarny
float Dlugosc(float *Wektor)
{
    return sqrt(Skalarny(Wektor,Wektor));
}

//Funkcja ktora wypelnia tablice dlugosci
void ObliczDlugosci(float *Wektory, float *IchDlugosci, int IchLiczba)
{
    int i;
    for(i=0; i<IchLiczba; ++i)
    {
        IchDLugosci[i] = Dlugosc(Wektor+3*i);
    }
}


//Funkcja ktora zamienia miejscami DlugoscA-DlugoscB i WektorA-WektorB
//Wektory są tablicami o co najmniej trzech wspolrzednych. Tzn. i tak
//interesuja nas tylko pierwsze trzy
void Swap(float *DlugoscA, float *DlugoscB, float *WektorA, float *WektorB)
{
    float TempDlugosc;
    float TempWektor[3];

    //zamiana danych miejscami
    //bla bla bla

}


void Posortuj(float *Wektory, float *IchDlugosci, int IchLiczba)
{
    //blablabla

    //gdizes wewnatrz jakis petli w sortowaniu bombelkowym 
    if(IchDlugosci[i] > IchDlugosci[i+1])
    {
        //moza przekazac tak:
        Swap( IchDlugosci+i, IchDlugosc+i+1, Wektory+(3*i), Wektory+((i+1)*3) );
        //albo tak:
        //Swap(&(IchDlugosci[i]), &(IchDlugosc[i+1]), &(Wektory[3*i]), &(Wektory[3*(i+1)]);
        IloscSwapniec++;
    }

}



int main()
{
    float DaneWektorow[60];
    float DlugosciWektorow[20];
    int nLiczba;

    //czytanie danych
    //bla bla bla
    
    ObliczDlugosci(DaneWektorow,DlugosciWektorow,nLiczba);
    Posortuj(DaneWektorow,DlugosciWektorow,nLiczba);

    //wypisywanie
    //szmery/bajery

    return 0;
}

Seria na 8.04.2016

Należy rozwiązać następujące problemy:

Prosta statystyka

Dane wejściowe

N
x1
x2
(...)
xN

Gdzie \(N\) jest liczbą całkowitą określającą ilość danych wejściowych. \(N\) jest zakresu od 1 do 100. \(x_i\) to liczby zmiennoprzecinkowe.

Oblicz średnią \[ \mu = \frac{1}{N}\sum _{i=1}^{N}x_i \] i sigmę \[ \sigma = \sqrt{\frac{1}{N} \sum_{i=1}^{N}(x_i - \mu)^2 } \]

i podaj je na stadardowe wyjście:

mu
sigma

Zarówno \(\mu\) i \(\sigma\) to, z bardzo oczywistych powodów, liczby zmienno przecinkowe.

Przykład:

Wejście:

10
0.
1.
2.
3.
4.
5.
6.
7.
8.
9.

Wyjście:

4.500000
2.872281

Program powinien spełniać warunki konieczne (50%) i dodatkowe 2, 3 (50%).

Cechy liczb

Dane wejściowe

N
a1
a2
(...)
aN

Gdzie \(N\) jest liczbą całkowitą określającą ilość danych wejściowych. \(a_i\) to liczby całkowite z zakresu od 3 do 100.

Program ma sprawdzać czy dana liczba ma następujące cechy:

• istnieje jej naturalny pierwiastek trzeciego stopnia
• jest liczbą finbonacciego
• jest liczbą parzystą

Wynik programu (standardowe wyjście)

a1 fib parz mapierw
(...)
aN fib parz mapierw

Gdzie fib, parz i mapierw to liczby całkowite 0 lub 1 określające daną cechę.

Przykład

Wejście:

3
5
8
27

Wyjście:

5 1 0 0
8 1 1 1
27 0 0 1

Program powinien spełniać warunki konieczne (50%), dodatkowe 1, 2, 3 (50%).

Kartkówki

Zadania domowe

Literatura

1. Kernighan, Brian W., Ritchie, Dennis M., Język ANSI C