Grupa 13

UWAGA! Osoby, które zamiast oceny mają wstawioną literę N muszą donieść usprawiedliwienia najpóźniej do 4-02-2015 na dyżur.

nr	indeks	08-10-2014	15-10-2014	22-10-2014	29-10-2014	05-11-2014	12-11-2014	19-11-2014 Kolokwium	26-11-2014	03-12-2014	10-12-2014	17-12-2014	07-01-2015	14-01-2015	21-01-2015	28-01-2015 Kolokwium	spoj	suma punktów	ocena
1	290414	N	N	N	N	N	N	N	N	N	N	N	N	N	N	N	0	0	2
2	396311	O	O	O	O	O	O	O 18	S	O	S	O	O	O	O	O 14	0	32	3,5
3	396384	O	O	O	O	N	S	O 2	O	N	S	O	O	O	O	U 0	0	2
4	396423	N	N	N	N	N	N	N	N	N	N	N	N	N	N	N	0	0	2
5	397852	O	O	O	O	N	O	O 8,5	S	N	O	O	O	O	O	O 4	0	12,5
6	405108	O	O	O	O	O	N	O 4,5	O	O	O	O	N	O	N	O 0	0	4,5	N
7	407210	N	N	N	N	N	N	N	N	N	N	N	N	N	N	N	0	0	2
8	407212	O 2	O	O 1	O	S	O	O 8	S	O	S	O	O	O	O	O 2	26,3	39,3	4
9	407224	O 1	O	O	O	O	O	O 2,5	O	O	O	O	O	O	O	O 0	0	3,5
10	407259	O 1	O	O 1	O	O	O	O 0,5	N 0,25	O	O	O	O	O	S	O 2	20,5	25,25	3
11	407261	O	O	O	O	S	N	O 1	S	N	N	O	S	S	O	O 2	0	3	N
12	407270	N	N	N	N	N	N	N	N	N	N	N	N	N	N	N	0	0	2
13	407283	O	O	O	O	O	O	O 7	S	O	S	O 3	S 9	O 2	S	O 15	0	36	4,5
14	407286	O 1	O	O 1	O	O	O	O 9,5	O 3	O	O	O	O	O	O	O 16	24,7	55,2	5
15	407297	O 1	O	O 0,5	O	O	O 4	O 7,5	O 1	U	O	O	O	S	O	O 3	26,5	43,5	5
16	407302	N	N	N	N	N	N	N	N	N	N	N	N	N	N	N	0	0	2
17	407319	O 1	O	N 1	O	O	O 1,5	O 7	O 1	O	O	O	O (7) 3	O	O	O 8	10,5	33	4
18	407331	O	O	O (1)	O	O	N	U 3,5	S	O	N	N	O	N	O	O 4	0	7,5	N
19	407333	O 1	O	O 1	O	S	O	O 6	O 1	O 2	O 2	N	S 7	O	O	O 7	2,8	29,8	3
20	412141	O	O	O	O	O	U	O 4	O (1,5)	O	N	O	N	S	O	O 2	19,7	25,7	3
21	412150	O	O	O 1	O	O	O	O 11,5	O 1	O	O	O	O	O	O	O 13	13,3	39,8	4,5
22
23
24
25
26

legenda:

O - obecny
U - nieobecny usprawiedliwiony
S - spóźniony
N - nieobecny
n - liczba otrzymanych punktów (gdzie n jest liczbą naturalną większą od zera)
(n) - liczba nieobronionych punktów

Skala ocen
od	do	ocena
0	25	2
25,1	30	3
30,1	35	3,5
35,1	40	4
40,1	45	4,5
45,1	∞	5

Literatura:

Programowanie

Algorytmy

Wykonane zadania:

Zasady zgłaszania

pl.spoj.pl

Osoby, które wykonały dowolne dwa zadania łatwe ze strony pl.spoj.pl mogą wykonywać dowolną liczbę zadań łatwych według poniższej tabeli:

od	liczba rozwiązań mniejsza niż	możliwe do zdobycia punkty
23:59:59 08-10-2014	1000	2
23:59:59 15-10-2014	2000	1,9
23:59:59 22-10-2014	3000	1,8
23:59:59 29-10-2014	4000	1,7
23:59:59 05-11-2014	5000	1,6
23:59:59 12-11-2014	6000	1,5
23:59:59 19-11-2014	7000	1,4
23:59:59 26-11-2014	8000	1,3
23:59:59 03-12-2014	9000	1,2
23:59:59 10-12-2014	10000	1,1
23:59:59 17-12-2014	11000	1

lub pozostałe zadania według punktacji:

typ zadania	punkty
średnie	2+
trudne	4+
wyzwania	do ustalenia

id zadania	kod zadania	nr indeksu	język programowania	czas wykonania	zajęta pamięć	status	liczba punktów
1116	Pierwiastki równania kwadratowego	407212	c++ 4.3.2	0,00 2	2,6 M	A	3,8
1218	Wyszukiwanie wzorca w tekscie	407297	c++ 4.3.2	0,28	2,8 M	A	2,6
751	Ciekawa wyliczanka	412150	c++ 4.3.2	0,00	3,5 M	A	2,6
505	Cwany Lutek	407259	c++ 4.3.2	0,00	2,6 M	A	2,2
1346	Łamacz gg	407319	c++ 4.3.2	0,00	2,8 M	A	2,0
2484	Czy potrafisz nie uzyc srednika	407286	c++ 4.0.0-8	0,01	2,6 M	A	2,0
2484	Czy potrafisz nie uzyc srednika	412141	c++ 4.0.0-8	0,04	2,6 M	A	2
21016	Wyznacz promień	407212	c++ 4.3.2	0,00	2,8 M	A	2,0
21021	BMI	407297	c++ 4.3.2	0,00	2,8 M	A	2,0
17140	To zadanie jest łatwe!	412141	c++ 4.3.2	0,92	2,8 M	A	2,0
17140	To zadanie jest łatwe!	412141	c++ 4.3.2	0,93	2,8 M	A	2,0
20176	Mundial 2014	407286	c++ 4.3.2	0,00	2,6 M	A	2,0
10344	Taksówka na Manhattanie 3	407259	c++ 4.3.2	0,48	2,6 M	A	2,0
2045	Pola Prostokątów	407259	c++ 4.9.2	0,00	3,0 M	A	2,0
12989	Prezent	407297	c++ 4.3.2	1,03	2,6 M	A	1,9
12989	Prezent	407286	c++ 4.3.2	1,04	14 M	A	1,9
1142	Ciążowy specjalista	407212	c++ 4.3.2	0,00	2,8 M	A	1,9
1056	Tabelki liczb	407297	c++ 4.3.2	0,00	3,0 M	A	1,9
806	Wiatraczki	407259	c++ 4.3.2	0,04 15 pkt	2,9 M	A	1,9
8981	Zamiana miejsc	407286	c++ 4.3.2	0,00	2,6 M	A	1,9
1299	Stefan	407259	c++ 4.3.2	0,13	3,3 M	A	1,9
6702	Rodzaje trójkątów	407259	c++ 4.3.2	0,01	2,6 M	A	1,9
4840	Szyfr Gronsfelda	412150	c++ 4.0.0-8	0,14 70	2,7 M	A	1,9
1211	Niekolejne	412141	c++ 4.3.2	0,01	2,6 M	A	1,9
4647	PTwPZ Telefony	407286	c++ 4.3.2	0,00	2,8 M	A	1,9
5517	Punkty w okręgu	407212	c++ 4.3.2	0,00	2,6 M	A	1,9
3326	Warunek w tablicy	407319	c++ 4.3.2	0,00	2,8 M	A	1,8
1978	Zliczanie linii	407319	c++ 4.3.2	0,00	2,8 M	A	1,8
2181	Wycinanie literek	407286	c++ 4.0.0-8	0,00	3,4 M	A	1,8
1102	Średnia arytmetyczna	407259	c++ 4.3.2	0,00	2,8 M	A	1,8
1145	Imieniny	412141	c++ 4.3.2	0,00	3,4 M	A	1,8
1242	Zliczacz liter	407319	c++ 4.3.2	0,00	2,8 M	A	1,7
1240	Współliniowość punktów	407212	c++ 4.3.2	0,00	2,8 M	A	1,7
1844	Zliczanie wystąpień	407212	c++ 4.3.2	0,04	2,6 M	A	1,7
1844	Zliczanie wystąpień	407297	c++ 4.3.2	0,05	2,6 M	A	1,7
1844	Zliczanie wystąpień	407286	c++ 4.3.2	0,17	4,6 M	A	1,7
617	StringMerge	407297	c++ 4.3.2	0,00	2,8 M	A	1,7
998	Kalkulator 2	407259	c++ 4.3.2	0,00	2,7 M	A	1,7
1910	Odwracanie wyrazów	407212	c++ 4.9	0,05	2,8 M	A	1,7
1910	Odwracanie wyrazów	412150	c++ 4.3.2	0,06	2,8 M	A	1,7
1910	Odwracanie wyrazów	412141	c++ 4.3.2	0,09	2,8 M	A	1,7
1042	Transponowanie macierzy	407212	c++ 4.3.2	0,00	2,7 M	A	1,7
1042	Transponowanie macierzy	407297	c++ 4.0.0-8	0,01	2,7 M	A	1,7
1042	Transponowanie macierzy	407212	c++ 4.0.0-8	0,01	3,3 M	A	1,7
4138	Harry and big doughnuts	407259	c++ 4.3.2	0,00	2,6 M	A	1,7
1300	Szyfr Cezara	412150	c++ 4.3.2	0,00	2,8 M	A	1,7
499	Czy umiesz potęgować	412141	c++ 4.3.2	0,00	2,6 M	A	1,7
1035	Test 3	407286	c++ 4.0.0-8	0,00	3,5 M	A	1,7
626	Obżartuchy	407212	c++ 4.3.2	0,02	2,6 M	A	1,7
1830	Nierówność trójkąta	407297	c++ 4.3.2	0,05	2,8 M	A	1,7
1830	Nierówność trójkąta	407319	c++ 4.3.2	0,08	2,8 M	A	1,7
804	Gra Euklidesa	412150	c++ 4.3.2	0,0 5	2,8 M	A	1,6
804	Gra Euklidesa	407212	c++ 4.3.2	0,84 15	2,6 M	A	1,6
1228	Równanie liniowe	407297	c++ 4.3.2	0,00	2,8 M	A	1,6
1228	Równanie liniowe	412141	c++ 4.3.2	0,01	2,8 M	A	1,6
969	Równanie kwadratowe	412141	c++ 4.3.2	0,00	2,8 M	A	1,6
609	Pole pewnego koła	407212	c++ 4.3.2	0,00 4pkt.	2,8 M	A	1,6
977	Tablica	407297	c++ 4.3.2	0,0	2,6 M	A	1,6
1261	Pesel	407286	c++ 4.3.2	0,01	2,6 M	A	1,6
1011	Połowa	407297	c++ 4.3.2	0,01	2,8 M	A	1,5
1011	Połowa	407286	c++ 4.3.2	0,12	2,8 M	A	1,5
1055	Parzyste nieparzyste	407286	c++ 4.3.2	0,00	2,6 M	A	1,5
1016	Predkość średnia	407319	c++ 4.3.2	0,00	2,8 M	A	1,5
1016	Predkość średnia	407297	c++ 4.0.0-8	0,03	2,6 M	A	1,5
1016	Predkość średnia	407286	c++ 4.0.0-8	0,03	2,6 M	A	1,5
1016	Predkość średnia	407333	c++ 4.0.0-8	0,04	2,6 M	A	1,5
1032	Podzielność	407297	c++ 4.3.2	0,00	2,6 M	A	1,5
1032	Podzielność	407286	c++ 4.3.2	0,06	2,6 M	A	1,5
997	Kalkulator	412150	c++ 4.0.0-8	0,00	2,6 M	A	1,4
522	Przedszkolanka	407259	c++ 4.3.2	0,00	2,6 M	A	1,4
1139	Nowa działka	412141	c++ 4.3.2	0,00	2,6 M	A	1,4
723	ROL	412141	c++ 4.3.2	0,00	2,6 M	A	1,4
968	Suma	412141	c++ 4.3.2	0,00	2,6 M	A	1,4
438	Liczby Pierwsze	412150	c++ 4.3.2	0,24	2,6 M	A	1,3
438	Liczby Pierwsze	407333	c++ 4.3.2	0,27	2,6 M	A	1,3
438	Liczby Pierwsze	407297	c++ 4.3.2	1,51	3,0 M	A	1,3
606	Tablice	412141	c++ 4.3.2	0,00	2,6 M	A	1,2
496	Dwie cyfry silni	407286	c++ 4.0.0-8	0,00	3,2 M	A	1,2
601	NWD	407212	c++ 4.3.2	0,00	2,6 M	A	1,2
601	NWD	407297	c++ 4.3.2	0,03	2,8 M	A	1,2
1502	Samolot	407212	c++ 4.3.2	0,00	2,6 M	A	1,1
1502	Samolot	412150	c++ 4.3.2	0,02	2,6 M	A	1,1
1828	Dodawanie liczb całkowitych	407297	c++ 4.0.0-8	0,00	2,6 M	A	1,1
549	Proste dodawanie	407212	c++ 4.0.0-8	0,00	2,6 M	A	1
549	Proste dodawanie	407286	c++ 4.0.0-8	0,01	2,6 M	A	1

legenda status:

Z - zgłoszone
A - zaakceptowane
O - odrzucone

Zadanie 3 (termin: 23:59:59 09-12-2014)

Napisz program, który:

tworzy po 3 tablice o wymiarach od 10¹ do 10⁷ (łącznie 3 * 7 tablic)
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 algorytmami:
za (3 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(n²) 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)CLOCK_PER_SEC;

W c++ można używać bibliotek z C w następujący sposób

time.h	// c
ctime	// c++

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: 23:59:59 28-10-2014)

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

a * x ^ 2 + b * x + c = 0
a, b, c, x ∈ R

Wejście:A B C Wyjście:L x1 x2 gdzie L oznacza liczbę rozwiązań, a x1 x2 ... xL poszczególne rozwiązania ułożone niemalejąco
Przykład:

1 0 0
1 0

-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)

ZAŁĄCZNIKI:
Plik z kodem źródłowym (*.c, *.cpp)

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

Zadanie 1 (termin: 23:59:59 28-10-2014)

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
//	=

Linijka rozpoczynająca się symbolami // oznacza komentarz w pseudokodzie do końca linii.
Proszę również określić liczbę operacji w Państwa rozwiązaniu
PRZYKŁAD:

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

Rozwiązanie o najmniejszej liczbie operacji otrzyma dodatkowy punkt (1 pkt.)
ZAŁĄCZNIKI:
Plik z kodem źródłowym (*.c, *.cpp)
Plik z pseudokodem(*.txt)

link do pseudokodu	nr indeksu	język programowania	liczba operacji	zajęta pamięć	liczba punktów
txt	407212	c++	4	8	2
txt	407333	c++	6	8	1
txt	407286	c++	6	8	1
txt	407297	c++	6	8	1
txt	407224	c++	6	8	1
txt	407259	c++	6	8	1
txt	407319	c++	6	8	1