, pro rozdělení textu koncem řádku nepárovou značka <strong>tucny text dalsiho odstavce
. Pro zvýraznění textu se používá značka <em>, pro silnější zvýraznění (tučně) značka <strong>, pro zápis citace slouží značka , pro výpis kódu programu bývá uvozen značkou . Všechny tyto značky jsou párové (specifikují začátek a konec platnosti). Pro definici nadpisů se používají párové značky až
mezi které se zapíší texty nadpisů. Značka
označuje nadpis nejvyšší úrovně, značka
nadpis nejnižší úrovně, např. takto:
titulek kapitoly 1
<em>zvyrazneny text první kapitoly titulek podkapitoly 1.1
text podkapitoly
text na novem radku titulek podkapitola 1.1.1
... Text lze doplnit o obrázky pomocí značky , přičemž parametr src definuje soubor obrázku a parametr alt text, který bude zobrazen v případě, že obrázek nebude k dispozici:
Další značky pro tvorbu HTML stránek lze nalézt například na: http://www.jakpsatweb.cz/html/ Doplňte váš HTML dokument o obrázky a rozšířené formátování textu a vystavte jej na studentském serveru. Úloha C. Tento úkol je zaměřen na základní práci a testování v počítačových sítích. Určete IP adresy přidělené serveru FEST. Pomocí utilit ping a traceroute otestujte síťové připojení k vybraným serverům přes protokoly IPv4 (UNIX i Windows) a IPv6 (UNIX). Pro UNIX/Linux lze využít příkaz ifconfig (výstup a příslušné adresy jsou patrné z výpisu na obr. 1.3). Dále vyzkoušejte utility pro zjištění odezvy a cesty k vybranému serveru v síti (obr. 1.4): ping|ping6 název_cíle a traceroute|traceroute6 [-n] název_cíle
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
7
Obr. 1.3. Ifcofig pro server FEST.
Obr. 1.4. Výpis traceroute pro server s doménovým jménem www.google.com.
Seznamte se s utilitou nslookup. Získejte IPv4 a IPv6 záznamy vybraných doménových jmen. Vyzkoušejte si nerekurivní dotaz na kořenový jmenný server. Spusťte nslookup a nastavte: set type=any poté zadejte doménové jméno serveru (viz obr. 1.5). Pomocí utility Telnet se připojte na vybrané HTTP servery a získejte metodou GET indexovou stránku. Použijte UNIXový telnet např.: telnet www.urel.feec.vutbr.cz 80 a volejte metodu GET: GET/HTTP/1.0
8
FEKT VUT v Brně
Obr. 1.5. Prohledání sítě utilitou nslookup pro doménové jméno www.google.cz.
Hodnocení: Úloha není hodnocena. Kontrolní otázky 1.1)
Jaký je vztah mezi HostName a IP adresou?
1.2)
Kolik zařízení (serverů) je možno adresovat IP adresou s protokoly IPv4 a IPv6 (UNIX)?
1.3)
Jaký je rozdíl mezi párovou a nepárovou značkou v HTML skriptu?
Literatura [1.1]
HERBORTH, Ch. Unix a Linux. Názorný průvodce. Brno: Computer Press, 2006.
[1.2]
KUROSE, J. F., ROSS, K. W. Počítačové sítě. Brno: Computer Press, 2014.
2
Konzolová aplikace, tisková funkce printf()
Cílem je seznámit se vývojovým prostředím Code::Blocks a společně sestavit první konzolovou aplikaci s výpisem výsledků na obrazovku při aplikaci tiskové funkce printf(). Úloha A. Spolu se cvičícím sestavte a odlaďte konzolovou aplikaci pro převod dekadického čísla na hexadecimální a naopak. Proveďte rovněž ladění aplikace v režimu „debugging“. Výsledné okno aplikace je jako příklad uvedeno na obrázku 2.1. Program bude pracovat v textovém režimu s jednoduchým menu, kdy uživatel nejprve zadá znakem h (H) nebo d (D) jaký typ převodu se bude provádět. Následně zadá vstupní převáděnou hodnotu a program vytiskne výsledek v kýžené číselné soustavě. Pro případ ukončení programu je součástí menu znak q (Q) pro ukončení aplikace.
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
9
Obr. 2.1. Zobrazení výsledků příkladu v konzolovém okně.
V první části programu je vždy nejprve nutné definovat hlavičkové soubory knihoven, které budeme v programu využívat pomocí direktivy #include. Tato direktiva zajistí vložení hlaviček funkcí z příslušné standardní knihovny, které je uvedena v <>. Například pro naši aplikaci budeme potřebovat funkce pro vstup hodnot a znaků z klávesnice, proto vkládáme hlavičkový soubor knihovny stdio (standardní funkce pro vstupy a výstupy), tedy soubor studio.h. Protože budeme používat i funkce pro matematické operace, které nejsou definovány v jazyce C žádnými operátory, např. pro výpočet mocnin při základu 16, vložíme také hlavičkový soubor pro standardní knihovnu matematických funkcí math.h. Pro snadnou práci s řetězci pak použijeme funkce z knihovny string: #include <stdio.h> #include <math.h> #include <string.h> Dále je třeba definovat hlavičky vlastních funkcí, možné to je i vložením vlastního vytvořeného hlavičkového souboru. My budeme používat dvě vlastní funkce, jednu pro převod desítkového na hexadecimální číslo: void dec2hex(unsigned int dec, char hex[]); a druhou pro převod zpětný:
10
FEKT VUT v Brně
unsigned int hex2dec(char hex[]); Funkce má v závorce definovány vstupní parametry a může obsahovat jednu návratovou hodnotu, jejíž typ je uveden před názvem příslušné funkce. To je případ druhé funkce. V případě té první je nutné vrátit výsledek, tedy hexadecimální číslo, jako pole znaků, proto je požadované pole uvedeno jako vstupní parametr char hex[]. Pokud je vstupním parametrem jedno číslo nebo znak, jedná se o tzv. volání hodnotou, kdy se tato hodnota překopíruje do lokální proměnné funkce a po skončení funkce se tato lokální proměnná uvolní z paměti a její nesená hodnota se ztratí. V případě pole nebo ukazatele (ukazatele budeme probírat později) jako vstupního parametru funkce, jde o volání odkazem (referencí). Funkci se předává adresa pole (prvního prvku, ostatní prvky pole v paměti bezprostředně navazují), proto v těle funkce můžeme přímo ovlivňovat obsah tohoto pole a tím i vložit do tohoto pole výsledek funkce, který nemá jen jednu hodnotu, ale např. pole znaků u hexadecimálního čísla. Těla uvedených funkcí je pak třeba následně definovat. To už může být kdekoli v kódu, protože hlavičky funkcí jsou již známy a lze tyto funkce kdykoli volat. Dále je do kódu programu nutné vždy vložit funkci main(), která je volána se spuštěním programu. Právě v těle funkce main() bude umístěna sekvence příkazů, které se budou postupně vykonávat, včetně volání funkcí (standardních i vlastních). Z hlediska algoritmu bude ve funkci main() naprogramováno výše uvedené menu a na základě volby pak bude volána příslušná funkce pro převod čísla. V části kódu pro menu bude integrován cyklus typu do-while, kdy bude program vykonávat tělo tohoto cyklu (výpis informací pro menu a vstup znaku pro volbu) dokud uživatel nezvolí ukončení programu znakem q, resp. Q. Dále již budete postupovat při sestavování programu s vyučujícím, přesto si uveďme stručný popis standardních funkcí, které bude program používat: Fukce printf(char[]) z knihovny stdio slouží k výstupu na obrazovku (konzolu). Parametrem je řetězec (pole znaků), který má být zobrazen. Řetězec může obsahovat speciální zástupné znaky pro vytištění hodnot proměnných, příslušná proměnná je pak v pořadí dalším parametrem. Například tato konstrukce: int a=12345; printf("V kase je %d Kc\n", a); vypíše na obrazovku: V kase je 12345 Kč _ Zástupným znakem pro desítkové celé číslo v řetězci je %d, což v našem případě znamená, že se vytiskne hodnota uložená v proměnné a, která je uvedená jako druhý parametr. Speciální znak %f je určen pro desetinné desítkové číslo atd. Pochopitelně, že v řetězci může být několik zástupných znaků, pak musí být příslušné proměnné uvedeny jako další parametry v daném pořadí. Znak \n je opět speciální znak pro nový řádek, proto je kurzor posunut v našem příkladě na nový řádek. Funkce scanf(char[], adr) taktéž z knihovny studio slouží k načtení řetězce z klávesnice a uložení do proměnné na adrese adr. Opět je možno v řetězci definovat speciální zástupné znaky jako u funkce printf(). Navážeme-li na předchozí příklad konstrukcí: scanf("%d", &a);
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
11
pak to znamená, že do proměnné a se uloží desítkové celé číslo načtené z klávesnice. Znak & definuje, že se jedná o adresu následné proměnné. Z knihovny string budeme využívat funkci strrev(char[]). Tato funkce jednoduše otočí pořadí znaků v řetězci (poli znaků), tedy řetězec bude otočen (reverzován). Poslední funkcí, kterou budeme využívat je int pow(int, int) z knihovny math, která vrací celočíselný výsledek mocniny prvního celočíselného parametru na druhý celočíselný parametr. Vyzkoušejte si s vyučujícím i problematiku ladění chyb programu záměrným vnesením nějaké syntaktické chyby a rovněž proces ladění po krocích se sledováním stavu proměnných v integrovaném vývojovém prostředí Code::Blocks. Hodnocení: Úloha není hodnocena.
Kontrolní otázky 2.1)
Jaký je rozdíl mezi parametrem funkce volaným hodnotou a volaným odkazem?
2.2)
Co znamená #include?
2.3)
Kdy má funkce printf() více parametrů a co definují?
Literatura [2.1]
KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004.
[2.2]
HEROUT, P. Učebnice jazyka C. 1. díl. České Budějovice: KOOP nakladatelství, 2009.
3 Manipulace s polem, cyklus for Cílem je seznámit se s vytvářením jednoduchých konzolových aplikací a se základními typy proměnných. Jádrem je pak problematika práce s dvourozměrným polem, indexování a využití cyklu for. Úloha A. V úvodní části zdrojového kódu programu k příkladu bpc1e_c03.c je definována ve dvourozměrném poli temp tabulka průměrných měsíčních teplot odměřovaných denně ve 13.00 (a pak zprůměrňovaných za daný měsíc) z nejmenované meteorologické stanice v ČR: float temp[16][12] = {-1.1, -0.3, 7.6, 12.7, 19.2, 27.6, 29.3, 29.1, … … 23.2,20.1,12.0,5.1,0.8}; // temp. table Záznam teplot v tabulce definovaných byl prováděn od roku 1995, řádky v poli odpovídají jednotlivým rokům od roku 1995 a sloupce jednotlivým měsícům, hodnota počátečního roku je k dispozici v proměnné styear.
12
FEKT VUT v Brně
V jednoduché tabulce vypište záznam teplot do konzolového okna. Doplňte program tak, aby v konzolovém okně vypsal průměrnou teplotu ve zvoleném měsíci a roce (zadáno při deklaraci proměnných mon a year). Pro tuto část je již připravena základní kostra programu s tiskem hlavičky zkratek měsíců a naznačeným cyklem for, pochopitelně pro tisk dvourozměrné tabulky teplot budete muset použít dva vnořené cykly for: printf("Temperature table:\n\n"); table:" printf(" JAN FEB MAR DEC\n"); months for(...)
//
printing
"Temperature
APR MAY JUN … // printing abrev.
NOV for
Hodnocení: 1 bod.
Úloha B. Program doplňte o výpočet průměrné teploty v jednotlivých celých letech (leden až prosinec) do šestnáctiprvkového pole s vhodným názvem a průměrné teploty v daných měsících za všech šestnáct let měření do dvanáctiprvkového pole s vhodným názvem, průměrné hodnoty teplot vytiskněte v jednoduché tabulce v konzolovém okně se zobrazením jednoho desetinného místa. Zobrazení na jedno desetinné místo s využitím funkce printf() se provede následovně: printf("%4.1f", x); kde x je racionální číslo a %A.Bf je zástupný znak (symbol) pro tisk desetinného čísla se zarovnáním na A znaků doprava a B desetinných míst. Hodnocení: 1 bod.
Úloha C. Pomocí podmínkové konstrukce s příkazem if (použití demonstruje cvičící) vytiskněte v konzolovém okně všechny tropické měsíce, tj. měsíce, kdy průměrná teplota ve 13.00 dosáhla nebo přesáhla 32°C. Stejně tak vytiskněte všechny arktické měsíce, kdy průměrná teplota dosáhla -6°C a méně. Příklad výstupů tohoto úkolu v konzolovém okně je uveden na obrázku 3.1. Hodnocení: 1 bod.
Bonusová úloha Doplňte předcházející úlohu o algoritmus, který na obrazovku vypíše pouze roky s průměrnou teplotou větší nebo rovnu 14°C a dále pak roky s průměrnou teplotou nižší nebo rovnou hodnotě 12°C.
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
13
Obr. 3.1. Zobrazení výsledků příkladu v konzolovém okně. Kontrolní otázky 3.1) Proč jsou v cyklu for pro oddělení inicializace, podmínky a aktualizace použity středníky? 3.2) Co bude vytisknuto na obrazovce v případě následujícího kódu: float x; x = 3.8975; printf("\nx je %5.2f km", x); 3.3) Jak by vypadala podmínka v úloze C, pokud se mají tisknout měsíce, kdy teplota přesáhla 20°C a současně byla menší než 25°C?
14
FEKT VUT v Brně
Literatura [3.1] [3.2]
KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004. HEROUT, P. Učebnice jazyka C. 1. díl. České Budějovice: KOOP nakladatelství, 2009.
4 Algoritmus Taylorovy řady, programování cyklů Cílem cvičení je procvičit si práci s výrazy a operátory a seznámit se s konverzemi v jazyce C a efektivním řešením složitějšího algoritmu. Úloha A. Vytvořte program, který vypočte hodnotu exponenciální funkce y = e x bez použití knihovních matematických funkcí s využitím rozvoje v Taylorovu řadu (viz Matematika I): ∞ x x 2 x3 xn xn e = 1 + + + + ... + − ... = ∑ 1! 2! 3! n! n = 0 n! x
(4.1)
Vstupní parametr x vygenerujte jako číslo sestávající se z náhodně vygenerované celé části v rozsahu <0; 9> a desetinné části (dvě místa) získané náhodným vygenerováním celého čísla v rozsahu <0; 99>. V konzolovém okně vytiskněte pro kontrolu a srovnání i hodnotu exponenciální funkce vstupního parametru vypočítanou funkcí exp()z knihovny math.h. Dále sestavte algoritmus, který bude postupně přidávat do výpočtu exponentu členy Taylorovy řady a výsledek vždy s uvedením počtu započítaných členů zobrazí (viz obr. 4.1). Připočítání a tisk výsledku provádějte v cyklu for. Pro dosažení velmi přesného výsledku je potřeba pro daný rozsah vstupního parametru asi padesát členů Taylorovy řady. Výsledky exponenciální funkce zobrazujte s 22 platnými a 16 desetinnými čísly. Proměnné výpočtu exponenciální funkce deklarujte jako float, double, long double a pozorujte dosažitelnou přesnost výpočtu (u tisku long double funkcí printf() vložte těsně před specifikátor f velké písmeno L, tedy %22.16Lf. Úvodní část zdrojového kódu programu k příkladu je v bpc1e_c04a.c: #include #include #include #include
<stdio.h> <stdlib.h> <math.h>
int main( void) { double x; // double fval=1; // double xpow=1; // double fact=1; int integ, decim; int n=0; // char c;
input value ouput value power of input value in numerator // factorial in denominator // int. and dec. fractions of input value index for comp. of Taylor series in loop
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
srand(time(NULL));
15
// seed init. for random generator
// write a code here scanf("%c", &c); // waiting for pressing key return 0; // program returns 0 } Vstupní parametr x je definován proměnnou x, která se sestává z celé části integ, rozsah <0; 9>, a desetinné části decim, rozsah <0; 99>, vyjadřující setiny vstupního parametru. Mezivýsledek po započtení příslušného počtu členů je ukládán do proměnné fval. Dvě pomocné proměnné xpow a fact reprezentují čitatel a jmenovatel aktuálního členu. Tyto proměnné jsou zde záměrně zavedeny proto, aby mohl být snadno vypočítán další člen řady. Při pohledu na rovnici (4.1) je zřejmé, že čitatel xpow následujícího členu je roven čitateli předchozího členu násobeného proměnnou x, proto také zvolené jméno proměnné xpow. A u jmenovatele je to podobné, protože je zde aplikován faktoriál a ten je vždy pro následující člen dán pouhým vynásobením předchozího členu pořadím členu n (proměnná n). Využijte této nápovědy, kód algoritmu bude velmi jednoduchý a současně výkonný, např. jen proto, že už nemusíte pro člen s velkým n počítat celý faktoriál čísla n, který je časově velmi náročný. Podobně to platí i pro mocninu x v čitateli.
Obr. 4.1. Příklad výstupů v konzolovém okně pro výpočet exponenciální funkce z příkladu A.
16
FEKT VUT v Brně
Hodnocení: 1,5 bodu.
Úloha B. Zadáno cvičícím na začátku cvičení. Hodnocení: 1,5 bodu.
Bonusová úloha Tímto příkladem si ukážeme, že „C-čko“ nemusí být nuda ani v konzolové aplikaci, budete totiž tvořit vaši zřejmě první hru. Ve zdrojovém kódu programu k příkladu bpc1e_c4bon.c je prakticky vše připraveno, na vás je dopsat jediný řádek označený přemi tečkami. Cílem je naprogramovat klasickou hru, kdy se snažíte vrhem nebo střelou zasáhnout cíl. Jádrem je klasická úloha pohybové rovnice pro šikmý vrh a tu musíte naprogramovat. V programu jsou pro vás stěžejní proměnné ele (definuje elevační úhel hodu ve stupních) a vel (definuje počáteční rychlost v m/s). Vaším úkolem je ve smyčce for pro vstupní polohovou proměnnou x (vodorovná osa, resp. vzdálenost od počátku odkud je hod prováděn) sestavit rovnici, která vypočte hodnotu polohové souřadnice y (výšku střely či kamene) pro daný elevační úhel a počáteční rychlost. Polohové souřadnice jsou definovány v metrech. Bez hlubšího odvození (je velmi primitivní a určitě jste se s ním setkali ve fyzice) platí:
1 1 y = x ⋅ tgα − ⋅ g ⋅ x 2 ⋅ 2 v ⋅ cos α 0
2
(4.2)
V rovnici se kromě elevačního úhlu α a počáteční rychlosti v0 ještě vyskytuje tíhové zrychlení g. Pro tíhové zrychlení a ještě také konstantu π je do programu zavedena direktiva #define, která umožní pro určitou číselnou konstantu definovat její zástupné jméno. Kdykoli překladač narazí na takto definované zástupné jméno, nahradí je příslušnou číselnou hodnotou. Sestavením rovnice (4.2) v programu máte hru připravenou (pozor na typy proměnných). Po spuštění programu se vygeneruje náhodná poloha cíle a parametry elevace a počáteční rychlosti. Měnit hodnotu elevace můžete stiskem klávesy q o jeden stupeň nahoru, stiskem klávesy a o jeden stupeň dolu, pro počáteční rychlost mají obdobnou funkci klávesy w a s. Změnu o více než jeden stupeň nebo m/s zajistíte násobným stiskem příslušné klávesy. Potvrzení je nutné klávesou ENTER. Hod nebo střelba je zahájena stiskem c + ENTER. Program nabízí i jistou grafickou podívanou a končí zásahem cíle (viz obr. 4.2). Kontrolní otázky 4.1) Proč se výsledek v příkladu A po přidání 34. členu již nemění a je rozdílný od výpočtu standardní funkcí exp()? 4.2) K čemu složí direktiva #define? 4.3) Jaké další matematické funkce lze počítat pomocí Taylorovy řady?
Literatura [4.1]
KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004.
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
[4.2]
17
HEROUT, P. Učebnice jazyka C. 1. díl. České Budějovice: KOOP nakladatelství, 2009.
Obr. 4.2. Výstup z konzolové střílečky z bonusového příkladu.
5 Manipulace s řetězci v jazyku C Cílem je se seznámit se zpracováním řetězců v jazyce C a funkcemi standardní knihovny ANSI C pro manipulaci s řetězci string.h. Úloha A. V řetězcové proměnné text ve zdrojovém souboru bpc1e_c05a.c jsou uložena slova zvířat malými písmeny oddělená mezerou: int main(void) { char text[] = "cat dog hen duck … swallow"; // to do return 0; // program returns 0 } Vytvořte program, který v konzolovém okně vypíše jednotlivě slova označující zvířata, každé na samostatném řádku s počátečním velkým písmenem. Program doplňte algoritmem, který spočte počet jednotlivých slov v proměnné text (pomocí počtu mezer, pozor za posledním slovem již mezera není). Dále program doplňte o algoritmus, který určí četnost jednopísmenných až desetipísmenných slov. Počty slov s daným počtem písmen vypište do
18
FEKT VUT v Brně
konzolového okna a to jen v případě, že počet slov s daným počtem písmen bude nenulový (viz obr. 5.1.). Pro řešení programu nevyužívejte knihovních funkcí string.h. Pro výpis názvů zvířat na nový řádek a s velkým písmenem na začátku si stačí uvědomit, že jednotlivá slova odděluje mezera. Ve vhodném cyklu je tedy třeba kontrolovat každý znak vstupního řetězce a v případě mezery vložit na výstup nový řádek. S využitím pomocné celočíselné proměnné je výhodné počítat znaky jednotlivých názvů a v případě prvního znaku převést před tiskem na obrazovku první písmeno z malého na velké (stačí vědět, že ASCII kód stejného písmena anglické abecedy malého je o hodnotu 32 větší než stejného písmena velkého). Poslední úkol je trochu obtížnější, leč opět lze využít proměnné pro počítání znaků slova. Na konci slova, další znak je mezera, případně konec řetězce, tato proměnná obsahuje počet znaků daného slova. Pokud si deklarujeme pole celočíselných elementů, které v pořadí bude definovat počet slov s daným počtem znaků (odpovídá indexu pole), pak proměnná čítače znaků bude vlastně indexem pro element tohoto pole, který je nutné zvětšit o jedna, protože právě dočtené slovo má příslušný počet znaků. Nezapomeňte toto pole na začátku inicializovat (vynulovat všechny elementy pole vhodným cyklem). Hodnocení: 1,5 bodu.
Úloha B. Zadáno cvičícím na začátku cvičení. Hodnocení: 1,5 bodu.
Obr. 5.1. Tisk výstupů v konzolovém okně pro příklad 1.
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
19
Bonusová úloha V řetězcových proměnných stext1 a stext2 ve zdrojovém souboru bpc1e_c05bon.c je zašifrována textová zpráva. Tuto zprávu dešifrujte jednotlivými níže uvedenými kroky (algoritmy) a zobrazte v konzolovém okně. Postup dešifrování je následující (je vhodné výsledky jednotlivých kroků zobrazovat v konzolovém okně): a.
Spojte oba řetězce v jeden, stext1 je první.
b.
Všechna písmena ‘Q‘ nahraďte písmenem ‘C‘ a písmena ‘T‘ písmenem ‘B‘.
c.
Posuňte hodnotu všech znaků zprávy o jedna výše, dle ASCII tabulky např. ‘A‘ bude po operaci ‘B‘,‘M‘ bude ‘N‘ atd.
d.
Všechny řetězce ‘CC‘ ve zprávě nahraďte řetězcem ‘RM‘. Pro tuto operaci využijte knihovní funkce strstr() a strncpy() (viz přednáška 3).
e.
Rotujte všechny znaky zprávy (v tuto chvíli jen velká písmena) opačně ve smyslu abecedy, např. ‘A‘ bude po operaci ‘Z‘, ‘B‘ bude ‘Y‘ atd.
f.
Nahraďte všechna velká písmena malými vyjma prvního znaku.
g.
Všechna písmena ‘w‘ nahraďte znakem ‘ ‘ (mezera) a písmena ‘h‘ znakem ‘.‘ (tečka).
Výsledky procesu dešifrování jsou uvedeny na obr. 5.2.
Obr. 5.2. Výsledky procesu dešifrování z bonusového příkladu. Kontrolní otázky 5.1) Popište, jak pracuje funkce strncpy() a jaké má parametry? 5.2) Co se stane, pokud ani jeden znak v deklarovaném prostoru pro řetězec není NULL? 5.3) Kolik bytů je vyhrazeno v paměti pro řetězec s následující deklarací
char a[] = "Brno je super mesto";?
20
FEKT VUT v Brně
Literatura [5.1]
KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004.
[5.2]
HEROUT, P. Učebnice jazyka C. 1. díl. České Budějovice: KOOP nakladatelství, 2009.
6 Statistické výpočty, aplikace cyklů Cílem cvičení je procvičit si práci s příkazy v jazyku C, především pak využití cyklů, a aplikovat je na běžné statistické výpočty. Úloha A. V této úloze si zkusíte naprogramovat některé typické algoritmy používané v programování a algoritmy pro základní statistické výpočty. Příklad vychází z dřívější úlohy (třetí cvičení), kde se zpracovávala tabulka teplot. V úvodní části zdrojového kódu k příkladu bpc1e_c06a.c je opět definována ve dvourozměrném poli temp tabulka průměrných měsíčních teplot naměřených ve 13:00 z nejmenované meteorologické stanice v ČR. Záznam teplot v tabulce definovaných byl prováděn od roku 1995, přičemž řádky v poli odpovídají jednotlivým rokům počínaje rokem 1995 a sloupce jednotlivým měsícům. V jednoduché tabulce vypište záznam teplot do konzolového okna (využijte řešení původní úlohy 3A): int main( void) { double temp[16][12]={-1.1, -0.3, 7.6 … … 0.8}; int m, n, l; char mon[]="JAN,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT,NOV,DEC"; int styear=1995; double avmon[12], stdmon[12]; float avtemp[3][12]; int mintmon[12], maxtmon[12]; float mint, maxt; printf("Temperature table:\n\n\t "); n=0; while (mon[n]!='\0') { if (mon[n]==',') printf(" "); else printf("%c", mon[n]); n++; } printf("\n"); // to do
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
21
return 0; }
V předpřipraveném kódu je také k dispozici řetězec obsahující třípísmenné zkratky měsíců oddělené čárkami pro snadný výpis zkratek jednotlivých měsíců textově na obrazovku. Příklad je uveden v cyklu while. Doplňte program tak, aby v konzolovém okně byla vypsána také průměrná měsíční teplota (pro každý měsíc) v pětiletých obdobích počínaje rokem 1996 (tedy první průměr bude za roky 1996-2000) a to ve vhodně řešených cyklech s vnořením (ne tři samostatné smyčky pro každé období). Dále program doplňte o algoritmus nalezení nejchladnějšího a nejteplejšího měsíce v celém měřeném období a výsledky vytiskněte v konzolovém okně. V programech aplikujte alespoň jednou všechny typy smyček for, while i do-while. Příklad výstupů tohoto úkolu v konzolovém okně je uveden na obrázku 6.1.
Obr. 6.1. Zobrazení výsledků příkladu A v konzolovém okně. Pro výpočet směrodatné odchylky souboru hodnot X je výhodné využít výpočtově jednodušší vztah:
22
FEKT VUT v Brně
σ ( X ) = E (X 2 ) − [E ( X )]2 =
1 N 2 ⋅ ∑ xi − x 2 N i =1
,
(6.1)
kde operátor E reprezentuje střední hodnotu nad příslušnou množinou. Při použití tohoto vztahu je potřeba v cyklu vypočítat střední hodnotu z druhých mocnin všech teplot (pro 16 roků příslušného měsíce) a od této hodnoty odečíst druhou mocninu vypočítané střední hodnoty pro příslušný měsíc. Výsledkem je statistický rozptyl. Směrodatná odchylka je pak druhou odmocninou rozptylu. Hodnocení: 1,5 bodu.
Úloha B. Zadáno cvičícím na začátku cvičení. Hodnocení: 1,5 bodu.
Bonusová úloha Vytvořte program, který pomocí algoritmu známém jako Eratosthenovo síto, vypíše všechna prvočísla do určité hodnoty (např. 1000). Algoritmus pracuje tak, že se postupně odebírají z pole čísel (rozsah čísel, kde prvočísla hledáme) všechny násobky čísel 2, 3, 4 až polovina maxima rozsahu. Pro řešení v jazyce C je výhodné si vytvořit pole znaků dané s počtem prvků odpovídajícím rozsahu množiny čísel, mezi nimiž hledáme prvočísla. Pak naplníme všechny prvky tohoto pole nějakým znakem např. ’P’, který definuje, že dané číslo odpovídající indexu v poli znaků je prvočíslo. Následně ve vhodném cyklu aplikujeme Eratosthenovo síto, tedy počítáme násobky, a znaky na příslušných indexech (násobcích) nahradíme znakem ’N’ (není to prvočíslo). Po provedení algoritmu zůstanou prvočísla na pozicích (indexech) s původním znakem ’P’. Na závěr pak stačí jen vypsat příslušné indexy pole znaků se znakem ’P’. Příklad pro rozsah do 1000 je uveden na obrázku 6.2. Pro přehlednost doporučuji tisk se zarovnáním na jistý počet znaků.
Obr. 6.2. Zobrazení prvočísel z bonusové úlohy v konzolovém okně. Kontrolní otázky 6.1) Jak by vypadala deklarace 3D matice celých čísel? 6.2) Přepište následující cyklus tak, aby využíval konstrukci cyklu while:
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
23
int n; for(n = 1; n < 100; n+=2) printf("%d ", n); 6.3) Jaký je vztah mezi rozptylem a směrodatnou odchylkou?
Literatura [6.1]
KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004.
[6.2]
HEROUT, P. Učebnice jazyka C. 1. díl. České Budějovice: KOOP nakladatelství, 2009.
7 Funkce, sestavení knihovny funkcí, volání funkcí Cílem cvičení je vyzkoušet si vytváření vlastních funkcí včetně zapouzdření do vlastní knihovny. Knihovna vlastních funkcí je pak aplikována v projektu C.
Úloha A. Příklad opět vychází z úloh s tabulkou teplot. V úvodní části zdrojového kódu programu k příkladu bpc1e_c07a.c je definována ve dvourozměrném poli temp tabulka průměrných měsíčních teplot naměřených ve 13.00 z nejmenované meteorologické stanice v ČR. Záznam teplot v tabulce definovaných byl prováděn od roku 1995, řádky v poli odpovídají jednotlivým rokům od roku 1995 a sloupce jednotlivým měsícům. V projektu je jako vzor sestavena tisková funkce, která umožňuje na nový řádek do konzolového okna vytisknout řádek se zkratkami měsíců (JAN,FEB atd.):
void prn_mons(int tabs, int spaces) { char mon[]="JAN,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT,NOV,DEC"; int m, n; printf("\n"); for(n=0; n
24
FEKT VUT v Brně
} Tato funkce bude užitečná pro různá zobrazení statistických výsledků v konzolovém okně. Její užitečnost je zvýšena přidáním dvou parametrů volaných hodnotou: počtem tabelátoru pro odsazení vlastního textu od počátku řádku a počtem mezer mezi zkratkami měsíců. Funkce je již připravena, v těle je řetězec mon[] obsahující zkratky pro tisk měsíců, které jsou oddělené čárkou. Sestavte rovněž jednoduchou tiskovou funkci, která se bude určitě dále hodit a vytiskne jen jednu zkratku jednoho měsíce podle vstupního parametru (např. prn_mon(1) vytiskne JAN atd.). V jednoduché tabulce vypište záznam teplot do konzolového okna (opět využijte řešení dřívějších úloh) s aplikací vámi vytvořené funkce pro tisk řádku měsíců. Definujte vlastní typ t_temp jako matici 16x12 hodnot typu double tak, aby mohl být použit jako vstupní typ vstupního parametru funkce. K tomuto typu rovněž upravte deklaraci matice teplot temp. Sestavte dvě funkce mean_col a k ní duální mean_row, které vrací střední hodnotu vektoru vybraného sloupce (duálně řádku) z proměnné typu t_temp a od požadovaného řádku (duálně sloupce) do požadovaného řádku (duálně sloupce).
Obr. 7.1. Příklad zobrazení výsledků příkladu A v konzolovém okně.
25
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
Tzn., že tyto funkce budou mít čtyři vstupní parametry a mohou být použity pro výpočty středních hodnot např. v pětiletých obdobích (pro každý měsíc), tak jak bylo řešeno na předchozím cvičení, nebo např. pro výpočet průměrných teplot v kvartálech roku pro funkci mean_row. Hlavička funkce pro průměr ve sloupci může například vypadat následovně:
double mean_col(t_temp t, int col, int i_row, int e_row)
Pak volání funkce mean_col(temp, l, 5, 8) bude znamenat výpočet průměru teplot z tabulky temp a to pro první sloupec a pro teploty od 5. do 8. řádku v tomto prvním sloupci. Sestavené funkce využijte v hlavním programu (např. pětiletky i kvartály v jednotlivých letech). Sestavené funkce ověřte v hlavním programu. Posledním bodem tohoto úkolu je zapouzdření všech funkcí do vlastní knihovny. Příklad výstupů z aplikací je uveden na obrázku 7.1. Hodnocení: 1,5 bodu.
Úloha B. Zadáno cvičícím na začátku cvičení. Hodnocení: 1,5 bodu.
Bonusová úloha Cílem tohoto příkladu je sestavení knihovny funkcí pro základní operace nad komplexními čísly. Sestavte čtyři funkce: pro součet, pro rozdíl, pro násobení a pro dělení dvou komplexních čísel typu double. Vzhledem k tomu, že výsledkem bude opět komplexní číslo o dvou složkách (reálná část a imaginární část) a u funkcí může být pouze jedna návratová hodnota, je nutno použít volání parametrů odkazem pro výstup výsledku z funkce. Příklad hlavičky funkce pro součet dvou komplexních čísel může vypadat následovně:
void cadd(double *r_re, double x_im, double y_re, double y_im)
*r_im,
double
x_re,
double
Vstupními parametry jsou x_re, x_im pro složky prvního komplexního čísla a y_re, y_im pro složky druhého komplexního čísla. Tyto parametry jsou volány hodnotou. Výstupem jsou pak ukazatele r_re a r_im na paměťová místa typu double, do kterých se ukládá výsledek operace (opět reálná a imaginární část). Sestavte všechny čtyři funkce pro operace nad komplexními čísly a zapouzdřete je do vlastní knihovny s vhodným názvem, např. complexmath.h. V další fázi sestavte jednoduchou konzolovou aplikaci, ve které se načtou jednotlivé hodnoty složek komplexních čísel. Následně se načte operand jako znak ’+’ pro součet, ’-’ pro rozdíl, ’*’ pro násobení a ’/’ pro dělení a pomocí přepínače switch-case se zavolá příslušná funkce z vaší knihovny pro komplexní operace, kterou přilinkujte k aplikaci. Výsledek vhodně vytiskněte do konzolového okna. Po výpočtu a tisku výsledku načtěte znak z klávesnice, který umožní ukončení aplikace, např. je-li tento znak ’y’ jako „yes“, nebo
FEKT VUT v Brně
26
pokračování v dalším načtení vstupních komplexních čísel a provedení vybrané operace nad nimi. Příklad výstupů výsledků na konzolu je uveden na obrázku 7.2.
Obr. 7.2. Zobrazení výsledků bolusového příkladu v konzolovém okně.
Kontrolní otázky 7.1) Jaký je rozdíl při přidávání knihoven do projektu direktivou #include v případě jména souboru ve špičatých závorkách
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
27
Literatura [7.1]
KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004.
[7.2]
HEROUT, P. Učebnice jazyka C. 1. díl. České Budějovice: KOOP nakladatelství, 2009.
8 Struktury a dynamické proměnné Cílem cvičení je sestavit aplikaci, která bude používat vhodnou strukturu popisující daný objekt požadovanými parametry. Navazujícím cílem je deklarovat tuto strukturu jako dynamickou proměnnou a procvičit si práci s dynamickými proměnnými v jazyku C.
Úloha A. Cílem tohoto příkladu je sestavit projekt pro jednoduchou správu autobazaru. Projekt k příkladu A se skládá ze zdrojového souboru bpc1e_c08a.c, kde se nachází funkce main():
#include <stdio.h> #include
// ptrs. to cars // number of recorded cars
cnt = ini_bazar(bazar, cnt); printf("\n\nInsert command: 'q' = quit … "); scanf("%c", &cmd); fflush(stdin); while (cmd != 'q') // if not quit { switch (cmd) { case 'p': print_bazar(bazar, cnt); break; //case 'a': call function for adding a new car case 's': { printf("\nSelect low limit of price:"); scanf("%d", &lprice); fflush(stdin); printf("\nSelect high limit of price:"); scanf("%d", &hprice); fflush(stdin); } } printf("\n\nInsert command: 'q' = quit, … "); scanf("%c", &cmd); fflush(stdin); }; // call function for deleting of all recods
FEKT VUT v Brně
28
return 0; }
a knihovny pro funkce spojené se správou autobazaru s hlavičkovým souborem bazar.h:
typedef struct car { char type[20]; char color[10]; char mot; int vol; int year; int price; } T_car;
// car record // // // // // //
type of car color of car kind of the motor B = benzin, D = diesel motor volume in cubic cm year of production price
int ini_bazar(T_car **rec, int num); // bazar initialization void print_record(T_car *prcar); // printing car paramaters void print_bazar(T_car **rec, int num); // printing all cars // insert function header for deleting of all records (cars) // insert function header for printing of bazar content with // defined range of price // insert function header for adding of new car a zdrojovým souborem bazar.c:
#include
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
29
printf("\t %4d ccm\t year %d\t price %6d CZK", prcar->vol, prcar->year, prcar->price); } void print_bazar(T_car **rec, int num) { int n; for(n=0; n
Úloha B. Zadáno cvičícím na začátku cvičení. Hodnocení: 1,5 bodu.
FEKT VUT v Brně
30
Obr. 8.1. Příklad zobrazení výsledků příkladu A) v konzolovém okně.
Bonusová úloha Vytvořte program, který v konzolovém okně umožní hodnocení dvoukolového mezinárodního závodu ve skocích na lyžích. Vytvořte vlastní datový typ struktury (nebo využijte přiložený zdrojový kód), který bude obsahovat jméno závodníka, třímístný kód země, celkové dosažené body a aktuální pořadí a dvě vnitřní struktury s hodnocením jednotlivých skoků v prvním a druhém kole (délka skoku + bodové hodnocení 5 rozhodčích). Bodování je zřejmé z následujících pravidel: Hodnocení se vytváří na základě součtu dvou údajů: bodů za délku skoku a za stylové provedení:
a) body za délku skoku: každý závodník obdrží automaticky 60 bodů (výjimkou jsou mamutí můstky - K170 a více, u nichž se uděluje 120 bodů). V závislosti na dosažení tzv.
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
31
konstrukčního bodu můstku (např. 120 metrů u můstků K120) získává (nebo ztrácí) další body. Za každý metr navíc/méně získá/ztrácí určité množství bodů závislé na typu můstku: K60 - K69: K70 - K79: K80 - K99: K100 - K169: K170 a více:
2,4 bodu za metr 2,2 bodu za metr 2,0 bodu za metr 1,8 bodu za metr 1,2 bodu za metr
(velikost můstku je proměnná zadaná na začátku po spuštění programu)
b) body za stylové hodnocení: Každý z pěti porotců udělí skokanovi známku do 20 bodů s rozlišením po 0,5 bodech. Nejvyšší a nejnižší hodnota ze všech pěti známek se škrtá. Platné jsou tedy pouze tři známky a maximální zisk je 60 bodů. Stylové chyby skokana musí porotce promítnout do svého hodnocení. Jednotlivé záznamy budou generovány jako dynamické proměnné, na které bude nastaven ukazatel v poli ukazatelů na jednotlivé záznamy s počtem maximálně 30. Počet záznamů udržujte ve vhodné globální proměnné. Sestavte funkce pro vložení závodníka a dále funkce pro hodnocení skoku a výpis výsledků. Pro jednoduchost v prvním i druhém kole startují závodníci podle pořadí, ve kterém byly jejich záznamy dynamicky přidány. Po každém skoku bude vypsáno aktuální pořadí a na žádost i tabulka výsledků (pořadí od nejlepšího k nejhoršímu). Na závěr každého kola bude tabulka výsledků vypsána automaticky. V maximální míře využívejte funkce. Příklad výpisů konzolového okna je uveden na obrázku 8.2. Kritickou částí je generování aktuálního pořadí. Doporučuji vytvořit funkci, kterou zavoláte po každém skoku a v níž se vyhodnotí pořadí podle bodů. Tak stačí porovnat jen aktuální záznam s předešlými výsledky a vhodným způsobem jej zařadit. Příklad řešení struktury je v přiloženém zdrojovém kódu bpc1e_c08bon.c:
typedef struct jump // structure for jump and evaluation { float length; // length of jump in meters float points[5]; // evaluation by refs } t_jump;
typedef struct competitor { char name[20]; char country[4]; floa points; int order; t_jump round_1; t_jump round_2; } t_competitor;
// structure for competitor
t_competitor
// global array of pointers // to competitor records // global number of records
int
cnt=0;
*comp[30];
// // // // // //
name three-letter code of country sum of points order jump and eval. in the 1st round jump and eval. in the 2nd round
FEKT VUT v Brně
32
Obr. 8.2. Příklad výstupů v konzolovém okně pro bonusový úkol včetně finálního vyhodnocení. Kontrolní otázky 8.1) Jak velký prostor bude v paměti vyhrazený v případě deklarace proměnné typu T_car z příkladu A? 8.2) Co deklaruje následující konstrukce:
int **x? 8.3) Jak se projeví při tisku znak \t v řetězci funkce printf()?
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
33
Literatura [8.1]
KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004.
[8.2]
HEROUT, P. Učebnice jazyka C. 1. díl. České Budějovice: KOOP nakladatelství, 2009.
[8.3]
HEROUT, P. Učebnice jazyka C. 2. díl. České Budějovice: KOOP nakladatelství, 2008.
9 Programy pro manipulaci se soubory Cílem cvičení je seznámit se s manipulací se soubory, programováním načítání a ukládání dat do souboru a navázáním na dynamickou databázi.
Úloha A. Cílem tohoto příkladu je doplnit projekt pro jednoduchou správu autobazaru z projektu bpc1e_c08a. V předpřipraveném projektu bpc1e_c09a jsou hotové a plně funkční úkoly z projektu předchozího. V hlavním adresáři projektu je umístěn soubor bazar.txt, který obsahuje záznamy jednotlivých aut, každá položka na novém řádku:
14 Skoda Felicia Blue D 1400 2003 75000 Skoda Felicia Red D 1400 2001 55000 Alfa Romeo 156 Black … Číselný údaj na prvním řádku odpovídá počtu záznamů v souboru. Sestavte funkci, kterou nahradíte inicializaci databáze z předchozího projektu a která načte záznamy aut ze souboru bazar.txt a uloží je do dynamicky vytvářených záznamů. Pro načítání řetězců ze souboru, které se mohou skládat z několika slov, použijte funkci fgets(). Pozor tato funkce uloží do cílového řetězce i poslední znak ’\n’ (nový řádek), ten je třeba nahradit znakem ’\0’, například sestavením jednoduché korekční funkce. Druhým úkolem je sestavit funkci, která při ukončení programu uloží všechny záznamy automobilů (i nově přidaných) do souboru bazar.txt. Algoritmus ukládání můžete vložit do funkce pro uvolňování záznamů z paměti. Výstup je pochopitelně shodný s obrázkem 8.1. Pro specifikaci souboru je nutné použít ukazatel na speciální typ FILE, který je předdefinován v knihovně stdio.h. Soubor
FEKT VUT v Brně
34
je nejprve otevřít pomocí funkce fopen() a získat právě tento ukazatel na soubor, parametrem je jméno, případně i celá cesta, souboru a atribut, pro čtení je to řetězec "r", pro zápis do nového souboru pak řetězec "w". Další možné atributy byly diskutovány na přednáškách. Pro čtení specifických dat ze souboru je možné použít funkci fscanf(), která je obdobou funkce scanf(), jen místo čtení ze vstupu (klávesnice) je třeba specifikovat soubor ukazatelem typu FILE. Na závěr práce se souborem je třeba soubor korektně uzavřít funkcí fclose(). Níže je uveden příklad otevření souboru file.txt a přečtení jednoho celého čísla z tohoto souboru a uložení do proměnné x:
FILE int
*ptrf; x;
ptrf = fopen("file.txt","r"); if(ptrf != NULL) fscanf(ptrf, "%d", &x); fclose(ptrf); Hodnocení: 1,5 bodu.
Úloha B. Zadáno cvičícím na začátku cvičení.
Hodnocení: 1,5 bodu. Bonusová úloha K bonusovému projektu z předchozího cvičení doplňte funkci, která výsledky dvoukolového závodu ve skoku na lyžích uloží do textového souboru, příklad je uveden v souboru Results.txt.
Kontrolní otázky 9.1) Co se stane v případě, že již existuje soubor se stejným názvem a použijeme pro otevření souboru funkci fopen() s atributem "w"? 9.2) Proč je v ukázkovém příkladu použit ve funkci fscanf() u x použit symbol & a co znamená? 9.3) Proč je atribut ve funkci fopen() definován jako řetězec?
Literatura [9.1]
KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004.
[9.2]
HEROUT, P. Učebnice jazyka C. 1. díl. České Budějovice: KOOP nakladatelství, 2009.
[9.3]
HEROUT, P. Učebnice jazyka C. 2. díl. České Budějovice: KOOP nakladatelství, 2008.
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
35
10 Dynamická databáze Cílem cvičení je procvičit si práci s dynamicky vkládanými strukturami.
Úloha A. Upravte předchozí projekt pro databázi autobazaru tak, aby nebylo použito pole ukazatelů na jednotlivé záznamy, ale dynamicky vytvářený lineární seznam. V projektu bpc1e_c10a jsou hotové a plně funkční úkoly z projektu předchozího. V projektu je třeba doplnit strukturu car o položku ukazatele na strukturu car a upravit všechny funkce s odkazem na pole ukazatelů na záznamy **rec tak, aby byl definovaný pouze ukazatel na první záznam. Pro funkci mazání použijte také jako vstupní parametr pořadí mazaného záznamu (prodávaného auta). Ve funkci mazání je třeba obnovit vazbu mezi předchozím a následujícím záznamem (vůči mazanému záznamu). Zachovejte načítání a ukládání databáze do souboru bazar.txt. Algoritmus ukládání můžete vložit do funkce pro uvolňování záznamů z paměti. Výstup je pochopitelně opět shodný s obrázkem 8.1.
Hodnocení: 2 body. Úloha B. Zadáno cvičícím na začátku cvičení. Hodnocení: 1 bod.
Bonusová úloha Bonusový projekt z předchozího cvičení upravte stejně jako úlohu A pro dynamické vkládání závodníku bez ohledu na jejich počet.
Kontrolní otázky 10.1) Od kterého záznamu v dynamické databázi je třeba uvolňovat jednotlivé záznamy při ukončení projektu, pokud je definován mimo vazbu ze záznamu pouze ukazatel na první záznam? 10.2) Jak lze zjistit, že záznam je poslední v systému typu lineární seznam, pokud je definován mimo vazbu ze záznamu pouze ukazatel na první záznam? 10.3) Proč je vazba mezi záznamy v dynamické databázi řešena ukazatelem?
Literatura [10.1] KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004. [10.2] HEROUT, P. Učebnice jazyka C. 1. díl. České Budějovice: KOOP nakladatelství, 2009. [10.3] HEROUT, P. Učebnice jazyka C. 2. díl. České Budějovice: KOOP nakladatelství, 2008.
36
FEKT VUT v Brně
11 Pokročilé algoritmy, třídění Cílem cvičení je procvičit si práci s uspořádaným lineárním seznamem dynamicky vkládaných struktur.
Úloha A. Upravte předchozí projekt pro databázi autobazaru tak, aby vkládání nových automobilů do lineárního seznamu bylo provedeno uspořádaně podle ceny (vzestupně). V projektu bpc1e_c11a jsou hotové a plně funkční úkoly z projektu předchozího. Doplňte deklaraci struktury o identifikační číslo vozu (pořadí nákupu vozu do autobazaru). V textovém souboru je uloženo na druhém řádku identifikační číslo posledního přijatého vozu, pro každý záznam vozu je pak identifikační číslo uloženo na prvním místě (prvním řádku) před značkou automobilu (toto doplnění je v souboru bazar1.txt). Poslední identifikační číslo ID vozu udržujte ve vhodné globální proměnné. V projektu je třeba upravit všechny funkce o správu ID včetně všech možných tisků automobilů. V projektu je třeba dále upravit funkci add_car(), která vloží záznam uspořádaně podle ceny do lineárního seznamu. Jeho nové ID bude o jedna vyšší, než je v globální proměnné posledního ID. Pozor při vkládání na první a poslední pozici, je nutno správně naplnit ukazatele *first a *last. Ve druhé části vytvořte funkce pro uspořádaný tisk automobilů v bazaru podle dalších parametrů: objem, rok výroby. Nejvýhodnější je použít metodu selectsort a přímý tisk, doporučuji přidat do struktury nějaký znakový atribut, který nese informaci o tom, zda byl nebo nebyl již tento záznam použit pro tisk, resp. byl již vytříděn. Při troše důvtipu lze sestavit univerzální funkci, které provede třídění databáze podle vybrané položky. Její identifikace (např. znaková) může být vstupním parametrem této funkce. Ukázka výsledků je na obrázku 11.1, kde je uvedeno setřídění podle objemu a podle identifikačního čísla.
Hodnocení: 2 body. Úloha B. Zadáno cvičícím na začátku cvičení.
Hodnocení: 1 bod. Bonusová úloha Bonusový projekt z předchozího cvičení pro správu skokanského závodu upravte stejně jako úlohu A se tříděním závodníků podle příjmení a podle výsledků. Doplňte rovněž hodnocení národů, které se provede na základě součtu bodů tří nejlepších závodní dané země. Toto hodnocení nechť je rovněž setříděno od nejlepšího týmu pro nejhorší.
Kontrolní otázky 11.1) Kolik průchodů cykly třídění je nutných u pole 10 hodnot při použití metody bublesort? 11.2) Kolik průchodů cykly třídění je nutných u pole 10 hodnot při použití metody insertsort? 11.3) Jak lze třídit abecedně řetězce?
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
37
Obr. 11.1. Výstupy úlohy A v konzolovém okně. Literatura [11.1] KERNIGHAN, B. W., RITCHIE, D. M. Programovací jazyk C. Brno: Computer Press, 2004. [11.2] HEROUT, P. Učebnice jazyka C. 2. díl. České Budějovice: KOOP nakladatelství, 2008. [11.3] WRÓBLEWSKI, P. Algoritmy. Datové struktury a programovací techniky. Brno: Computer Press, 2004.
FEKT VUT v Brně
38
Odpovědi ke kontrolním otázkám 1.1) Jaký je vztah mezi HostName a IP adresou? HostName je jmenné označení zařízení připojené do dané počítačové sítě, IP adresa je jeho adresa v síti. V síti Internet vztah mezi jménem zařízení a jeho adresou drží tzv. DNS server (Domain Name System). 1.2) Kolik zařízení (serverů) je možno adresovat IP adresou s protokoly IPv4 a IPv6 ? IPv4 je 32bitová adresa (čtyři dekadická čísla oddělená dvojtečkou v rozsahu 0 až 255), proto IPv4 umožňuje adresovat 232 zařízení, tedy asi 4,3 miliardy. IPv6 je 128bitová adresa (osm hexadecimálních čísel oddělených dvojtečkou v rozsahu 0000 až FFFF), proto IPv4 umožňuje adresovat 2128 zařízení, tedy asi 3,4⋅1038. 1.3) Jaký je rozdíl mezi párovou a nepárovou značkou v HTML skriptu? Párová značka definuje začátek platnosti daného atributu a taktéž jeho konec, přičemž značka pro konec je shodná se značkou pro začátek, kde před jmenovku značky je vřazeno lomítko. Naopak nepárová značka definuje jen začátek platnosti daného atributu, ten je platný do místa, kde jeho platnost je změněna jinou značkou s danm charakterovým významem. 2.1) Jaký je rozdíl mezi parametrem funkce volaným hodnotou a volaným odkazem? Parametr volaný hodnotou pouze přebírá hodnotu (konstantu nebo hodnotu proměnné platné v části programu, odkud se funkce volá) a ukládá ji do nové vnitřní proměnné volané funkce, nemůže tedy měnit hodnotu proměnné z části programu, odkud se funkce volá. Na druhou stranu parametr volaný odkazem předává do volané funkce pouze adresu proměnné z části programu, odkud se funkce volá, tzn., že hodnotu této proměnné lze bezprostředně měnit v těle volané funkce. 2.2) Co znamená #include?
#include je direktiva pro specifikaci úpravy zdrojového kódu pře kompilací a zajišťuje vložení kódu z jiného souboru, jehož jméno je uvedeno za #include, např. hlavičkového souboru xxx.h. 2.3) Kdy má funkce printf() více parametrů a co definují? Funkce printf() může mít více parametrů v případě, kdy v řetězci, který je vždy prvním parametrem, se nachází alespoň jeden zástupný znak %. Tento zástupný znak má vždy definováno následným znakem v jakém formátu bude tisknuta proměnná, která následuje za řetězcem jako druhý parametr. Pokud je v řetězci zástupných znaků více, odpovídají jim v pořadí další parametry (proměnné, případně konstanty) funkce printf(). 3.1) Proč jsou v cyklu for pro oddělení inicializace, podmínky a aktualizace použity středníky? Je tak jednoznačně odděleno, že se jedná o příkaz, a nelze jej zaměnit s funkcí, která má vždy mezi parametry použitu jako oddělovač čárku.
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
39
3.2) Co bude vytisknuto na obrazovce v případě následujícího kódu: float x; x = 3.8975; printf("\nx je %5.2f km", x);
3.89 km (před číslem je jedna mezera) 3.3) Jak by vypadala podmínka v úloze C, pokud se mají tisknout měsíce, kdy teplota přesáhla 20°C a současně byla menší než 25°C?
if (temp[y][m]>20 && temp[y][m]<25) // y je index roku (řádku), m je index měsíce (sloupce) 4.1) Proč se výsledek v příkladu A po přidání 34. členu již nemění a je rozdílný od výpočtu standardní funkcí exp()? Protože je jako typ použit double, jehož rozlišení v desítkovém vyjádření je omezeno cca na 17 platných míst (52 bitů mantisy) . 4.2) K čemu složí direktiva #define? Direktiva #define je určena definici zástupného řetězce (2. parametr) za specifikovaný řetězec (1. parametr), oba řetězce se definují bez uvozovek. Náhrada zástupným řetězcem se provede ve zdrojovém vždy před překladem. 4.3) Jaké další matematické funkce lze počítat pomocí Taylorovy řady? Např. logaritmus a všechny goniometrické funkce. 5.1)
Popište, jak pracuje funkce strncpy() a jaké má parametry?
Funkce char* strncpy(char* dest, char* source, size_t num) provede zkopírování maximálně num znaků z řetězce source do řetězce dest. num je celé číslo, pokud překračuje počet možných znaků řetězce source, budou překopírovány všechny znaky řetězce source, pokud bude počet znaků řetězce dest menší než hodnota num, překopíruje se jen počet znaků odpovídající délce dest. Návratovou hodnotou je ukazatel na řetězec dest. 5.2) Co se stane, pokud ani jeden znak v deklarovaném prostoru pro řetězec není NULL? V tomto případě bude konec řetězce dán prvním znakem NULL (tedy bytem s obsahem 0), který bude na jistém paměťovém místě za regulérním posledním znakem deklarovaného prostoru pro řetězec v paměti. Pokud se bude řetězec jen číst, bude obsahovat jen nesmyslné znaky podle obsahu paměti. Pokud se bude i zapisovat, může dojít k nespecifikované chybě, protože budeme zapisovat do paměťového prostoru pro jiné proměnné či aplikace. 5.3) Kolik bytů je vyhrazeno v paměti pro řetězec s následující deklarací
char a[] = "Brno je super mesto";? Bude vyhrazeno 20 bytů, v této konstrukci se přidělí takový paměťový prostor, aby se do něj inicializační řetězec přesně vešel, tedy 19 bytů pro znaky řetězce a 20. byte pro znak NULL.
FEKT VUT v Brně
40
6.1) Jak by vypadala deklarace 3D matice celých čísel? Např. int matice3D[10][20][30], hodnoty v hranatých závorkách definují počet elementů matice v daném rozměru, tedy postupně počet řádků, počet sloupců a počet elementů v dimenzi hloubky. 6.2) Přepište následující cyklus tak, aby využíval konstrukci cyklu while:
int n; for(n = 1; n < 100; n+=2) printf("%d ", n); int n; n = 1; while(n < 100) printf("%d ", n++); 6.3) Jaký je vztah mezi rozptylem a směrodatnou odchylkou? Směrodatná odchylka je druhou odmocninou rozptylu. 7.1) Jaký je rozdíl při přidávání knihoven do projektu direktivou #include v případě jména souboru ve špičatých závorkách
int **x?
Programování a počítače 1. Počítačová cvicení pro obor B-EST.
41
Jde o ukazatel na ukazatel typu int, tzn., že v proměnné x je adresa odkazující na paměťové místo, kde je opět adresa, která je ukazatelem na proměnnou typu int. Tímto způsobem, lze například do proměnné x vkládat ukazatel na různá pole typu int. 8.3) Jak se projeví při tisku znak \t v řetězci funkce printf()? Znak \t je horizontální tabulátor, při tisku se projeví vložení patřičného počtu mezer na řádek do „tabulátorové zarážky“. 9.1) Co se stane v případě, že již existuje soubor se stejným názvem a použijeme pro otevření souboru funkci fopen() s atributem "w"? Jeho obsah bude smazán a nahrazen obsahem, který je vkládán z dané aplikace. 9.2) Proč je v ukázkovém příkladu použit ve funkci fscanf() u x použit symbol & a co znamená? Symbol & je operátor, který vrací adresu proměnné uvedené za symbolem &. Ve funkci fscanf() je použit proto, že tato funkce ukládá načtená data do proměnné (v našem případě x), která je volána odkazem. 9.3) Proč je atribut ve funkci fopen()definován jako řetězec? Protože atribut může mít více znaků např. rozšiřující znak +. Proto je atribut deklarován jako řetězec. 10.1) Od kterého záznamu v dynamické databázi je třeba uvolňovat jednotlivé záznamy při ukončení projektu, pokud je definován mimo vazbu ze záznamu pouze ukazatel na první záznam? Nejjednodušší cestou je uvolňování od posledního záznamu, pak nevzniká problém s udržování vazby tak, aby nebyl ztracen odkaz na některý ze záznamů. 10.2) Jak lze zjistit, že záznam je poslední v systému typu lineární seznam, pokud je definován mimo vazbu ze záznamu pouze ukazatel na první záznam? Nejlépe pomocí nulové adresy v ukazateli na další záznam, obsahem tohoto ukazatele bude adresa NULL, resp. 0. 10.3) Proč je vazba mezi záznamy v dynamické databázi řešena ukazatelem? Protože po záznam může být vyhrazeno místo v paměti funkci malloc() kdekoli (definuje si např. operační systém). Pak je nutno mít proměnnou pro definici vazby, která je ukazatelem. 11.1) Kolik průchodů cykly třídění je nutných u pole 10 hodnot při použití metody bublesort? 81 (9 cyklů vnitřních x 9 cyklů vnějších). 11.2) Kolik průchodů cykly třídění je nutných u pole 10 hodnot při použití metody insertsort? Max. 81 (9 cyklů vnějších x max. 9 cyklů vnitřních při použití cyklu while). 11.3) Jak lze třídit abecedně řetězce? Podle řetězce s největší délkou je výhodné vygenerovat zástupnou hodnotu řetězce, tak že první znak bude nejvyšším řádem s vhodnou (nejvyšší) váhou, druhý znak s duhou nejvyšší
FEKT VUT v Brně
42
váhou atd. Přičemž lze využít abecední uspořádání v ASCII tabulce. Pak provést třídění podle této zástupné hodnoty. Např. mějme čtyři slova KAREL, EMIL, KARLA a EMAN s následujícími zástupnými hodnotami pro znaky dle tabulky a použijme základ 30 :
A 0
B 1
C 2
KAREL: EMIL: KARLA: EMAN:
D 3
E 4
F 5
G 6
H 7
I 8
J 9
K L M N O P Q R S … 10 11 12 13 14 15 16 17 18 …
10⋅304 + 0⋅303 + 17⋅302 + 4⋅301 + 11⋅300 = 10⋅810000 + 0⋅27000 + 17⋅900 + 4⋅30 + 11 = 8115431 4⋅304 + 12⋅303 + 8⋅302 + 11⋅301 = 4⋅810000 + 12⋅27000 + 8⋅900 + 11⋅30 = 3571530 10⋅304 + 0⋅303 + 17⋅302 + 11⋅301 + 0⋅300 = 10⋅810000 + 0⋅27000 + 17⋅900 + 11⋅30 + 0 = 8115630 4⋅304 + 12⋅303 + 0⋅302 + 13⋅301 = 4⋅810000 + 12⋅27000 + 0⋅900 + 13⋅30 = 3564390
Po uspořádání vzestupně: EMAN – EMIL – KAREL – KARLA