Ćwiczenia:

1. 04-10-2017
2. 11-10-2017
3. 18-10-2017
4. 25-10-2017
5. 08-11-2017
6. 15-11-2017
7. 22-11-2017 Kolokwium aula: B
8. 29-11-2017
9. 06-12-2017
10. 13-12-2017
11. 20-12-2017
12. 03-01-2018
13. 10-01-2018
14. 17-01-2018
15. 24-01-2018 Kolokwium aula: B

Literatura:

Programowanie

• Brian Kernighan, Dennis MacAlistair Ritchie - Język ANSI C
• Stephen Prata - Język C. Szkoła programowania. Wydanie V

Algorytmy

• Ewa Palka - Elementy algorytmiki dla początkujących
• Kenneth A. Ross, Charles R.B. Wright - Matematyka dyskretna
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein - Wprowadzenie do algorytmów
• Ważniak
• Google

Sprawdzian:

Materiały do sprawdzianu dostępne są w następującej pozycji Brian Kernighan, Dennis MacAlistair Ritchie - Język ANSI C zakres sprawdzianu jest następujący:

• Rozdział 1 - Elementarz - podrozdziały 1-10
• Rozdział 5 - Wskaźniki i tablice - podrozdziały 1-3
• Rozdział 6 - Struktury - podrozdziały 1-2

Wykonane zadania:

Zasady zgłaszania, Konfiguracja Dev-C++

Błędy

Dodatkowe punkty można uzyskać, za wskazanie błędów na niniejszej stronie.
Dotyczy to stron z aktualnego semestru (uwaga: np. zima-2015 dotyczy semestru zimowego rozpoczynającego się w 2015 roku).
Błędy należy zgłaszać mailowo (należy wskazać link do strony, zrobić zrzut ekranu, na którym należy zaznaczyć błąd i napisać poprawną wersję).
Pierwsza osoba, która zgłosi błąd, otrzymuje punkt.
Maksymalna liczba punktów, jaką można uzyskać tą drogą, to 10 pkt.
O tym, czy coś jest błędem, ostatecznie decyduje prowadzący.
Błędy, które można zgłaszać:

• ortograficzne (błędami nie są nazwy plików bez polskich znaków)
• w pseudokodach
• w datach, nr sal itd. (nie dotyczy to zmiany terminu lub sali)
• błędy odnośników (nie dotyczy to strony z zablokowanym dostępem, ani linków zewnętrznych)
• nie można zgłaszać błędów w materiałach, których autorem nie jest prowadzący (czyli np. cytatach)

pl.spoj.com

Zadania można zgłaszać o ile:

• Nie ma zadanego projektu, a jeżeli jest to już został oddany i zaakceptowany do obrony.
• Nie występują na poniższej liście chyba, że osiągnęliśmy lepszy wynik tzn.:
  • Liczba punktów jest mniejsza/większa (zależy od zadania) (o ile punkty istnieją).
  • Nasz czas wykonania jest lepszy przy takiej samej liczbie punktów lub przy jej braku.
  • Zgłoszone zadanie ma czas 0.0, a program zużywa mniej pamięci.

• 1 punkt łatwe
• 2 punkty średnie
• 3 punkty trudne
• 1-10 punktów challenge
  
  a dla problemów: BSPIES, PIEK, PLGCOL, TOFFMILL, NPNPNPNP
  

Zadanie 3 (termin: 15:00:00 06-12-2017)

Napisz program, który:

• tworzy po 3 tablice o wymiarach od 10¹ do 10⁷ (łącznie 3 * 7 tablic)

  #include<stdlib.h>
  int * tab;
  int rozmiar = 10;
  tab = (int *) calloc(rozmiar, sizeof(int)); /* dynamiczna alokacja tablicy */
  /* tutaj można używać tablicy */
  free(tab); /* zwolnienie pamięci */
  

  1. posortowaną niemalejąco
  2. z losowymi liczbami

     #include<time.h>
     #include<stdlib.h>
     srand((unsigned) time(NULL));
     int liczba = rand() % 100 + 1; //1-100

  3. posortowana nierosnąco
• każdą tablicę należy posortować niemalejąco co najmniej dwoma algorytmami:
  za (1 pkt.)

  SELECT-SORT
  INSERT-SORT
  BUBBLE-SORT
  MERGE-SORT
  QUICK-SORT
  COUNT-SORT

  dodatkowo (+ 1 pkt) za każdy kolejny algorytm sortujący o złożoności O(n2) lub szybszy.
• wypisać tablicę 10¹ przed i po posortowaniu
• zmierzyć czas działania każdego z algorytmów, a wyniki wypisać

  #include<time.h>
  clock_t start, stop;
  double czas;
  
  start = clock();
  
  sort();
  
  stop = clock();
  czas = (stop - start)/(double)CLOCKS_PER_SEC;

• Wyjście programu:

  rozmiar: 10^1
  niemalejaco:
  1 2 3 4 5 6 7 8 9 10
  INSERT-SORT: 0.0
  1 2 3 4 5 6 7 8 9 10
  BUBBLE-SORT: 0.0
  1 2 3 4 5 6 7 8 9 10
  losowo:
  10 3 6 9 7 2 4 1 5 8
  INSERT-SORT: 0.0
  1 2 3 4 5 6 7 8 9 10
  BUBBLE-SORT: 0.0
  1 2 3 4 5 6 7 8 9 10
  nierosnaco:
  10 9 8 7 6 5 4 3 2 1
  INSERT-SORT: 0.0
  1 2 3 4 5 6 7 8 9 10
  BUBBLE-SORT: 0.0
  1 2 3 4 5 6 7 8 9 10
  rozmiar: 10^2
  niemalejaco:
  INSERT-SORT: 0.0
  BUBBLE-SORT: 0.6
  losowo:
  INSERT-SORT: 0.1
  BUBBLE-SORT: 0.5
  nierosnaco:
  INSERT-SORT: 0.5
  BUBBLE-SORT: 60+
  rozmiar: 10^3
  . . .
  

Uwaga! Aby program działał szybciej, można nie mierzyć czasu dla wolnych algorytmów i dużych tablic (sortujących dłużej niż minutę).

Zadanie 2 (termin: 15:00:00 08-11-2017)

Napisz procedurę (1 pkt), która wypisuje pierwiastki równania kwadratowego

A * x2 + B * x + C = 0
A, B, C, x ∈ R

A B C

L x1 x2

1 0 0
1 0 //liczby całkowite wypisują się bez kropki dziesiętnej

-2 3 -1
2 0.5 1	//wyniki posortowane niemalejąco

0 1 2
1 -2

0 0 1
0

0 0 0
R	//oznacza nieskończenie wiele rozwiązań (cały zbiór liczb rzeczywistych)

Proszę dokładnie przeanalizować wszystkie możliwości, za oddanie dwukrotnie błędnego programu obniżę ocenę o 0,5.

Zadanie 1 (termin: 15:00:00 18-10-2017)

Napisz program, który zamienia dwie zmienne miejscami nie korzystając z trzeciej zmiennej (1 pkt)
Operatory użyte w programie, a których nie używaliśmy na zajęciach, należy zdefiniować na początku pliku z pseudokodem w następujący sposób:
PRZYKŁAD:
// a SHIFTL b – operator, który reprezentację bitową liczby a przesuwa w lewo o b bitów obcina bity z lewej strony a z prawej dopisuje zerami
Należy też podać tablicę priorytetów operatorów użytych w pseudokodzie.
PRZYKŁAD:

//PRIORYTET OPERATORA
//	()
//	/ * DIV MOD
//	+ -
//	SHIFTL
//	=

x = a	//1 przypisanie
a = b	//1 przypisanie
b = x	//1 przypisanie
//razem 3 operacje