Organizace predmetu
Programování
Úlohy
Nové: datové typy, pretypování, printf, sizeof, bitové operátory
Vytisknete na standardní výstup tabulku velikostí a rozsahu vsech celocíselných datových typu. Tabulka musí obsahovat pocet bajtu, kolik zabírá promenná daného datového typu a dále minimální a maximální hodnotu.
Jednou tuto tabulku vytisknete pomocí konstant z limits.h, podruhé tyto hodnoty vypocítejte pomocí bitových operátoru.
Pracujte samostatne.
Nové: podmínený príkaz (if), matematické operátory, scanf
Vytvorte program pro výpocet korenu kvadratické rovnice. Vstup realizujte dotazem na uzivatele.
Nové: parametry príkazového rádku, definice podprogramu, strtod
Prepiste predchozí úlohu tak, aby byla resena pomocí samostatných funkcí. Vstup nerealizujte pomocí komunikace s uzivatelem, ale pomocí parametru z príkazového rádku.
Nové: datové typy, pretypování, printf, sizeof, bitové operátory, retezce, podprogramy
Napiste funkci, která prevede zadané celé neznaménkové císlo do dvojkové soustavy a vrátí textový retezec, který bude obsahovat textovou reprezentaci tohoto císla. Otestujte tento podprogram ve funkci main.
Modifikujte tuto funkci tak, aby byla schopná prevést zadané císlo do soustavy o libovolném základu od 2 do 36.
Nápoveda: Pro jednoduchost pracujte se staticky alokovaným polem predávaným do funkce pres parametr. Zamyslete se, jakou délku musí mít toto pole, aby se do nej spolehlive vesly vsechny cifry.
Nové: ctení pomocí scanf v cyklu while
Vytvorte program, který nacte ze standardního vstupu posloupnost císel typu double a na výstup vypíse prvky s maximální a minimální hodnotou a dále prumernou hodnotu vsech prvku posloupnosti. Hodnoty vypocítejte v jediném pruchodu posloupností. Posloupnost koncí, kdyz funkce pro ctení ze vstupu detekuje konec souboru (vrátí konstantu EOF).
Nové: jednoduchý konecný automat, cyklus while, getchar, príkaz switch, výcet (enum)
Vytvorte program, který bude opisovat standardní vstup na standardní výstup, ale kazdou neprázdnou posloupnost bílých znaku nahradí práve jednou mezerou. (2 body) Predpokládejte dále, ze v textu mohou být komentáre uzavrené do slozených závorek { a } a textové retezce uzavrené do "dvojitých uvozovek". Kazdý komentár nahradte jednou mezerou (2 body). Pro text ve dvojitých uvozovkách nic z toho, co zde bylo receno neplatí. Opiste jej naprosto beze zmeny (i kdyby obsahoval posloupnost mezer nebo slozené závorky) (1 bod). Tento program implementujte pomocí konecného automatu.
Nové: intervalová aritmetika, datový typ struktura (struct), struktura jako návratový typ funkce a jako datový typ parametru, ctení hodnot pomocí scanf po dvojicích
Napiste program pro výpocet celkového odporu paralelne propojených rezistoru. Hodnoty odporu jednotlivých rezistoru budou zadány na standardním vstupu v následujícím formátu:
m1 e1 m2 e2 m3 e3 ...
kde hodnota mi predstavuje nominální hodnotou odporu daného rezistoru a hodnota ei predstavuje chybu této hodnoty v procentech (trídu presnosti daného rezistoru). Rada takto zadaných hodnot koncí, kdyz funkce pro ctení ze vstupu detekuje konec souboru (vrátí konstantu EOF). Program by mel zpracovat libovolne dlouhou radu hodnot. Výsledek vypisujte ve stejném formátu, jako vstupní hodnoty, tedy jako strední hodnotu výsledku a chybu v procentech.
Návod: Pro resení pouzijte intervalovou aritmetiku. Operace v této aritmetice lze definovat napríklad takto:
Hodnotu odporu ukládejte jako interval, tedy dvojici hodnot pomocí datového typu struktura a vytvorte si sadu podprogramu pro jednotlivé operace nad intervaly. Pomocí techto operací pak realizujte výpocet paralelní kombinace dvou rezistoru a postupne jej aplikujte na celou radu (Ricelkovy = Ri-1celkovy // Ri).
Nové: ctení formátovaných hodnot s oddelovaci, datový typ pole, ukazatel+dynamicky alokované promenné, operace modulo
Do zelezáren prijízdejí nákladní vlaky se surovinami a aby byly co nejlépe vyuzity, jsou vagóny po vylození znovu naplneny struskou a zeleznými ingoty a odvázejí je pryc. Pracovník, který má na starosti efektivitu provozu se rozhodl, ze si bude zaznamenávat, jaký cas stráví kazdý vagón v továrne od okamziku jeho príjezdu do okamziku jeho odjezdu. Pro tyto úcely slouzí pocítac, který sleduje pobyt vagónu v továrne a pri odjezdu kazdého vagónu vzdy vrátí údaj ve formátu HH:MM:SS (hodiny, minuty, sekundy) udávající dobu pobytu vagónu v továrne. Nás pracovník má následující problém: z rady techto údaju ho zajímá vzdy soucet posledních N casových hodnot (maximálne), aby mohl vypocítat prumernou dobu, kterou strávily vagóny posledního vypraveného vlaku v továrne (vlak bude mít délku N). Napiste program, který tento údaj vypocítá a vypíse opet ve formátu HH:MM:SS.
Návod: Vytvorte si sadu podprogramu pro práci s casem (soucet casových údaju, prevod trojice hodnot na pocet sekund a zpátky, a podobne). Program bude ocekávat jako parametr príkazového rádku hodnotu N a na standardním vstupu bude ocekávat radu casových údaju. Tyto údaje lze nacítat pomocí funkce scanf("%d:%d:%d", &h, &m, &s).
Protoze nás zajímá jen posledních N hodnot z rady a dopredu nevíme, jak bude rada dlouhá, nemuzeme postupne scítat vsechny hodnoty ani si nemuzeme ulozit celou radu do pole (nevíme jak by muselo být dlouhé). Vystacíme si s polem délky N, které si vytvoríme dynamicky na zacátku programu a na konci jej uvolníme. Pri nacítání rady budeme ukládat hodnoty do tohoto pole a pokud bude na vstupu více hodnot nez N, vzdy prepíseme nejstarsí údaj novejsí hodnotou. Na konci stací secíst vsechny prvky pole. (Toto pole muzeme nyní nazývat fronta.)
Pro práci casovými údaji i s nasím polem vyuzijeme operaci modulo --- zbytek po celocíselném delení, v jazyce C jde o operátor %. U casových údaju jej lze vyuzít pri prevodu mezi údajem vyjádreným v poctu sekund a údajem tvoreným trojicí hodnot (hh:mm:ss). Pro implementaci fronty vyuzijeme s výhodou toho, ze výsledek operace x%N vzdy lezí v intervalu <0, N). Pole proto budeme indexovat promennou i, jejíz hodnotu budeme inkrementovat následujícím zpusobem, címz zajistíme prepsání vzdy nejstarsího prvku v poli:
i = ++i % N; pole[i] = hodnota;
Operacemi s modulem se zabývá modulární aritmetika.
Nové: konstrukce rekurzivních podprogramu, cyklus for, princip pulení intervalu
Vytvorte funkci realizující binární vyhledávání v jednorozmerném poli celých císel, která vrátí index hledaného prvku nebo zápornou hodnotu, pokud prvek v poli nenalezne. Otestujte tuto funkci na vzestupne serazené posloupnosti císel, která budou ulozena v poli dynamicky alokovaném na hromade. Zamyslete se, jak byste úlohu resili bez pouzití rekurze.
Nové: Fibonacciho posloupnost, Fibonacciho králíkárna, prevod rekurzivního algoritmu na iteracní algoritmus
Vytvorte dva programy (funkce), které vypísí prvních N clenu Fibonacciho posloupnosti. Jednou rekurzivne, podruhé nerekurzivne. Odhadnete (nebo vypocítejte) pocet kroku, které musí jednotlivé algoritmy vykonat v závislosti na zadané hodnote N.
Nové:
Vytvorte dva programy (funkce), které vypísí prvních N rádku Pascalova trojúhelníku. Jeden výpocet bude probíhat rekurzivne a druhý iteracne.
Poznámka: vytvorte rekurzivní funkci, která vypocte hodnotu n-tého prvku na k-tém rádku.
Nové: výpocet mocniny s lepsí nez lineární slozitostí
Vytvorte funkci, která bude provádet výpocet mocniny s logaritmickou místo s lineární slozitostí.
Návod: Zapiste výpocet mocniny jako rekurzivní problém, vzpomente si na vzorecky pro práci s mocninami o stejném základu a skombinujte je se znalostí principu pulení intervalu.
Nové: modulární aritmetika, princip kongruence
Vytvorte funkci, která vrátí posledních N císlic faktoriálu z císla X. Predpokládejte, ze císlo X bude typu long long a velikost císla N nebude vetsí nez 19. Funkce musí být schopna pracovat s celým rozsahem vstupního datového typu. Muzete pracovat pouze s celocíselnými datovými typy.
Nové: Algoritmus Hanojské veze, zkoumání slozitosti algoritmu
Vytvorte program, který bude vypisovat posloupnost akcí, které je nutné udelat pro presun N disku z první na poslední Hanojskou vez.
Problém Hanojských vezí: Máme tri jehly a na první z nich je polozeno N disku ruzných velikostí. Nikdy nesmí být polozen disk s vetsím prumerem na disku s mensím prumerem. V jednom kroku lze z jehly sundat jediný disk a nasadit jej na jinou jehlu, pokud tím nebude poruseno predchozí pravidlo. Úlohou je v co nejmensím poctu kroku premístit vsechny disky z první jehly na poslední jehlu, pricemz muzeme vyuzít prostrední jehly pro odkládání.
Nové: dynamická alokace vícerozmerného pole
Vytvorte program, který z parametru príkazové rádky precte celé císlo N, které udává pocet rádku Pascalova trojúhelníka. Alokujte dynamicky na hromade dvojrozmerné pole velikosti NxN a vytvorte funkci, která do nej ulozí prvky Pascalova trojúhelníka - prvky, které do trojúhelníka nepatrí, naplnte hodnotou 0. Dále vytvorte funkci, která tuto matici vytiskne na standardní výstup.
Nové: soubory
Vytvorte program, kterému uzivatel zadá jako parametr z príkazové rádky jméno souboru. V tomto souboru se bude nacházet matice celých císel ve formátu:
R S a11 a12 .... a1S a21 a22 .... a2S . . . . aR1 aR2 .... aRS
Na prvním rádku jsou rozmery matice (R - rádky, S - sloupce) a na dalsích rádcích se nachází prvky matice oddelené bílými znaky. Napiste funkci, která pro tuto matici alokuje 2D pole správné velikosti a vrátí nactenou matici. Dále vytvorte funkci, která nactenou matici vypíse na standardní výstup ve stejném formátu, jako vstupní soubor. Detekujte prípadné chyby ve vstupním souboru.
Nové: Pouzití vsech dosud nabytých znalostí dohromady.
Navazte na predchozí úlohu. Vytvorte funkce, které provedou nad maticí (maticemi) následující operace a pouzijte je v programu, který je bude volat podle zadaného parametru príkazové rádky:
Matice nacítejte ze souboru zadaných jako parametry príkazového rádku. Funkce samy o sobe nebudou nic vypisovat. Budou vracet výsledek nebo chybový kód. Výsledky tisknete na standardní výstup stejným zpusobem jako v predchozí úloze. Prípadná chybová hlásení se vypísí mimo ne (ideálne ve speciální funkci pro výpis chybových hlásení). Celkový návrh programu bude hodnocen az 4 body.
Nové: prefixový zápis výrazu, speciální forma define
Napiste proceduru (dve procedury), která vypocte obsah trojúhelníku pomocí Heronova vzorce:
s = (a+b+c)/2
P = odmocnina( s(s-a)(s-b)(s-c) )
Kazdý vzorec implementujte jako jednu proceduru. Existují dve moznosti, jak to udelat. Která z nich je efektivnejsí a proc?
Nové: speciální forma if
Vytvorte dve procedury pro výpocet korenu kvadratické rovnice. Osetrete situace, kdy zadaná rovnice nemá zádné resení a kdy má nekonecne mnoho resení.
Nové: rekurze, koncová rekurze (tail rekurze)
Vytvorte proceduru pro výpocet hodnoty faktoriálu. Vytvorte dve verze této funkce, kdy první verze bude vyuzívat obycejnou prímou rekurzi a druhá verze bude pouzívat koncovou rekurzi. Pomocí ladícího nástroje sledujte, jak se lisí výpocetní proces obou techto verzí.
Pomucka: Pro sledování hloubky zanorení testované procedury, vlozte na zacátek svého programu príkaz
(require (lib "trace.ss"))
Pred zavoláním samotné testované funkce zapnete trasování príkazem
(trace faktorial)
(faktorial 10)
Podobne jako v predchozí úloze vytvorte rekurzivní a koncove rekurzivní verzi procedury pro výpocet Fibonacciho císel. Pomocí trasování otestujte oba algoritmy pro mensí hodnoty argumentu (do cca 10). Vypocítejte hodnotu tisícího Fibonacciho císla (fib 1000). Chovají se obe verze algoritmu stejne? Proc?
Vytvorte procedury pro:
Nové: vedlejsí efekty funkcí, speciální forma begin, zelví grafika ve Scheme, pojem fraktál
Seznamte se s techpackem pro zelví grafiku (podle pokynu vyucujícího). Realizujte
Realizujte proceduru pro výpocet posloupnosti, která vede k resení problému Hanojských vezí.
Vypoctete nejvetsího spolecného delitele pomocí Euklidova algoritmu: r = x mod y : NSD(x, y) = NSD(y, r)
Nové: funkce time pro merení doby behu procedur
Realizujte procedury, které budou umocnovat celá císla s lineární a s logaritmickou casovou slozitostí (exp base exponent), (expl base exponent). Pomocí funkce time overte jejich casovou slozitost pro zvolený konstantní základ a vetsí hodnoty exponentu (sestavte tabulku pro hodnotu exponentu 25000 - 250000).
Zamyslete se, jak funguje modulární aritmetika. Realizujte funkci, která bude schopna efektivne a správne vypocítat výraz:
105072^2019799098211 mod 101 (mocnina modulo 101)
Realizujte dalsí základní aritmetické operace v modulární aritmetice. Lze ke vsem najít inverzní funkce?
Nové: teckové páry (cons, car, cdr), modulární aritmetika, quotient, remainder
Vytvorte sadu podprogramu, které budou umet scítat, odecítat a prevádet casové údaje vyjádrené pomocí teckových páru s touto podobou: (hodiny . minuty). Pocet hodin výsledku nesmí být vetsí nez 23 a pocet minut výsledku nesmí být nikdy vetsí nez 59 a mensí nez nula (pocítejte v aritmetice modulo 24 a modulo 60). Údaje na vstupu tuto podmínku splnovat nemusí. Implementujte tyto podprogramy:
Demonstrujte funkcnost techto podprogramu na vhodne zvolených úlohách. Napr.:
Zamyslete se nad tím, jak byste rozsírili zadanou úlohu, aby bylo mozné pocítat i s dny a sekundami.
Upravte funkce v predchozí úloze bez pouzití teckových páru (a seznamu). Hlavicky funkcí musí zustat beze zmeny, jen parametry a výsledky jiz nebudou teckové páry, ale nová reprezentace casového údaje. Na stejných úlohách, jako minule, demonstrujte funkcnost nové implementace.
Nové: lineární seznam, list, null?, list?
Vytvorte funkce pro otocení prvku v lineárním seznamu. Funkce realizujte pomocí koncové rekurze. Demonstrujte jejich funkcnost na vhodne zvolených datech.
Pomocí teckových páru realizujte abstraktní datový typ interval se základními aritmetickými operacemi (viz podobná úloha výse, kterou jste resili v jazyce C). Vytvorte i prevodní funkce mezi zápisem intervalu v notaci (min . max) a (stred . +-procenta). Pomocí tohoto abstraktního datového typu spocítejte výsledný odpor paralelní kombinace dvou rezistoru: R1 = 100 Ohm +-10%, R2 = 250 Ohm +-5%. Pouzijte tyto dva vztahy pro výpocet výsledného odporu: R = (R1 * R2)/(R1 + R2) a R = 1 / (1/R1 + 1/R2). Jsou získané výsledky pro oba vzorce stejné? Proc?
Pomocí seznamu vytvorte abstraktní datový typ mnozina. Realizujte alespon tyto operace: vlození prvku, odstranení prvku, sjednocení mnozin, prunik mnozin, rozdíl mnozin. Demonstrujte jejich funkcnost na vhodných príkladech.
Pomocí ADT mnozina, realizovaném v minulé úloze najdete vsechna prvocísla mensí nez zadané císlo N. Vyhledávání reste algoritmem Eratosthenovo síto.
Napiste skript pro príkazový shell bash, který bude vypisovat obsah aktuálního adresáre a bude reagovat na tri parametry príkazové rádky:
Skript implementujte pomocí funkcí.
Nové: príkazy sort, printf, presmerování souboru
Vytvorte v jazyce C jednoduchý program, který spocítá pocet rádku na standardním vstupu a vytiskne jejich pocet. Pokud bude nekterý rádek delsí nez rozumný pocet znaku (odhadnete), program bude vstup povazovat za binární a vrátí jako návratovou hodnotu programu (exit kód) hodnotu 1, jinak jej bude povazovat za textový a vrátí hodnotu 0. Dále vytvorte skript v BASHi, který projde vsechny soubory v aktuálním adresári a na výstup vytiskne tabulku vsech souboru a poctu jejich rádku. Soubory, které vás program oznací za binární z výpisu vynechte.
Zkuste s kombinací konvencního programu a skriptu experimentovat. Napríklad muzete doplnit parametry céckového programu tak, aby prepínaly pocítání rádku, slov, vet a podobne - exit kód pak muze detekovat i spatné parametry. Pomocí programu sort zkuste vámi vyprodukovanou tabulku seradit podle poctu rádku (slov, vet) jednotlivých souboru.
Nápoveda:
man printf
$? - exit kód posledního provedeného príkazu
man sort
Nové: príkazy grep, tar, (gzip), date
Napiste skript, který v aktuálním adresári vyhledá vsechny soubory, které obsahují text vaseho jména vytvorí z nich archiv moje-soubory-datum.tar.gz (datum v názvu souboru musí skript nahradit aktuálním datem).
Nápoveda:
man grep
$? - exit kód posledního provedeného príkazu
man tar
man date
date '+%d.%m.%Y'
Napiste skript, který provede nejméne 5 testu nad programem, který jste resili jako pololetní projekt v jazyce C. Skript ulozí do souboru protokol o kompilaci programu a poté údaje o vykonaných testech (napr. porovnání se soubory se vzorovými výsledky). Skript musí pouzívat podprogramy (napríklad kazdý test v jednom podprogramu) a musí pouzívat rídící struktury (podmínený príkaz, cykly, atd.). Snazte se celý skript a jednotlivé testy navrhnout tak, aby bylo snadné pridávat dalsí testy, a abyste odhalili co nejvíce potenciálních chyb v programu (testy nelegálních parametru, testy extrémních vstupních hodnot - prázdný soubor, nula, obrovské vstupní hodnoty, atd.).
Doplnte predchozí úlohuo sadu skriptu, které budou umet provádet tyto akce:
POZOR! Skripty musí být konfigurovatelné. Veskeré veci, které by bylo dobré menit soustredte do konfiguracního souboru.
Nové:Získávání parametru príkazové rádky, ctení znaku standardního vstupu metodou System.in.read(), zápis na standardní výstup metodami System.out.println(), System.out.printf().
Napiste jazyce Java program, který ze standardního vstupu opíse z kazdého rádku prvních N znaku na standardní výstup. Parametr N bude zadáván z príkazového rádku.
Nápoveda:
Nejprve vytvorte program, který bude mít hodnotu N zabudovánu napevno, teprve potom ji nactete z príkazového rádku.
Naucte se hledat dulezité informace na stránce Java API.
Retezec prevedete na hodnotu pomocí metody Integer.valueOf() - podrobnosti najdete na stránce Java API.
Pro správnou funkci metody System.in.read je potreba odchytit výjimku IOException pomocí konstrukce:
try
{
// ctení pomocí System.in.read();
}
catch (IOException e)
{
e.printStackTrace();
}
Nové: Trídy, balíky, zapouzdrení.
Vytvorte abstraktní datový typ (trídu) Interval nad typem double, který bude obsahovat tyto operace:
Funkcnost výsledného ADT overte na výpoctech s elektrickými soucástkami se zadanými trídami presnosti.
Nové: Tvorba balíku, tvorba tríd, metody, promenné objektu.
Napiste trídu Histogram a umístete ji do balíku vpi.histogram. Pri konstrukci trídy musí jít specifikovat, kolik hodnot bude trída schopna pojmout (predpokládejte, ze se bude zaznamenávat cetnost kladných hodnot velikosti integer). Objekt této trídy musí být schopen následujících cinností:
Vytvorte trídu Main, která otestuje funkcnost trídy Histogram tak, ze precte po znacích standardní vstup a na výstup vypíse relativní cetnosti znaku, které se vyskytly na vstupu v procentech. Znaky, které na vstupu nebyly do výpisu nezahrnujte. Dále vypiste samostatne necetnejsí znak a pocet jeho výskytu + relativní cetnost a pocet vsech prectených znaku. Výstup prehledne naformátujte.
Nápoveda:
System.in.read()
System.out.printf()
Nové: Abstraktní trídy, dedicnost.
Modifikujte predchozí úlohu tak, ze vytvoríte abstraktní trídu vpi.histogram.Histogram a její potomky, kterí budou pracovat nad datovými typy byte a integer. Overte správnou funkcnost implementovaných tríd pomocí vhodného programu, který bude ovládaný pomocí parametru príkazového rádku. Pro získání bodu musí jít o funkcní obecný program, který bude zpracovávat data ze standardního vstupu nebo ze zadaného souboru. Jednorázové programy nebudou uznávány.
Prémie c.1: Zamyslete se, jak by tento program vypadal, kdyby se místo abstraktní trídy pouzilo rozhraní (interface). Pokuste se tuto variantu implementovat. Jaké má toto resení výhody a jaké nevýhody?
Prémie c.2: Zamyslete se, jak by tento program vypadal s vyuzitím genericity (od verze Javy 1.5). Pokuste se tuto variantu implementovat. Jaké má toto resení výhody a jaké nevýhody?
Nové: diagram tríd, objektový návrh
Nakreslete diagram tríd popisující implementaci hry "Clovece, nezlob se!". Vytvorte textový popis úlohy, vyberte kandidáty na trídy, zakreslete dedicnost a kooperaci jednotlivých tríd.
Nové: Slovní úlohy.
Vytvorte trídu simulující opravnu automobilu. V opravne se budou uchovávat záznamy o práve opravovaných autech (typ, spz, cena za opravu, ...). Opravna má urcitou maximální kapacitu - maximální pocet soucasne opravovaných aut. Pokud prijde zákazník a je plno, bude odmítnut. Trída reprezentující opravnu bude mít metodu pro tisk údaju o vsech práve opravovaných autech.
Napiste jednoduchý program, který bude demonstrovat vsechny schopnosti implementovaných tríd.
Modifikujte resení predchozí úlohy tak, aby opravna byla schopna prijímat jedno i dvoustopá vozidla (motocykly, auta). Cena za opravu se bude pocítat pro automobily a pro motocykly odlisne. Stejne tak se bude vypisovat odlisným zpusobem záznam o vozidle. Pri implementaci vyuzijte dedicnost a polymorfismus.
Správnou funkcnost demonstrujte pomocí vhodného testovacího programu.
Poslední modifikace: 8. February 2010. Pokud v tomto dokumentu narazíte na chybu, dejte mi prosím vedet.