Organizace předmětu
Programování
Úlohy
Nové: datové typy, přetypování, printf, sizeof, bitové operátory
Vytiskněte na standardní výstup tabulku velikostí a rozsahů všech celočíselných datových typů. Tabulka musí obsahovat počet bajtů, kolik zabírá proměnná daného datového typu a dále minimální a maximální hodnotu.
Jednou tuto tabulku vytiskněte pomocí konstant z limits.h, podruhé tyto hodnoty vypočítejte pomocí bitových operátorů.
Pracujte samostatně.
Nové: podmíněný příkaz (if), matematické operátory, scanf
Vytvořte program pro výpočet kořenů kvadratické rovnice. Vstup realizujte dotazem na uživatele.
Nové: parametry příkazového řádku, definice podprogramů, strtod
Přepište předchozí úlohu tak, aby byla řešena pomocí samostatných funkcí. Vstup nerealizujte pomocí komunikace s uživatelem, ale pomocí parametrů z příkazového řádku.
Nové: datové typy, přetypování, printf, sizeof, bitové operátory, řetězce, podprogramy
Napište funkci, která převede zadané celé neznaménkové číslo do dvojkové soustavy a vrátí textový řetězec, který bude obsahovat textovou reprezentaci tohoto čísla. Otestujte tento podprogram ve funkci main.
Modifikujte tuto funkci tak, aby byla schopná převést zadané číslo do soustavy o libovolném základu od 2 do 36.
Nápověda: Pro jednoduchost pracujte se staticky alokovaným polem předávaným do funkce přes parametr. Zamyslete se, jakou délku musí mít toto pole, aby se do něj spolehlivě vešly všechny cifry.
Nové: čtení pomocí scanf v cyklu while
Vytvořte program, který načte ze standardního vstupu posloupnost čísel typu double a na výstup vypíše prvky s maximální a minimální hodnotou a dále průměrnou hodnotu všech prvků posloupnosti. Hodnoty vypočítejte v jediném průchodu posloupností. Posloupnost končí, když funkce pro čtení ze vstupu detekuje konec souboru (vrátí konstantu EOF).
Nové: jednoduchý konečný automat, cyklus while, getchar, příkaz switch, výčet (enum)
Vytvořte program, který bude opisovat standardní vstup na standardní výstup, ale každou neprázdnou posloupnost bílých znaků nahradí právě jednou mezerou. (2 body) Předpokládejte dále, že v textu mohou být komentáře uzavřené do složených závorek { a } a textové řetězce uzavřené do "dvojitých uvozovek". Každý komentář nahraďte jednou mezerou (2 body). Pro text ve dvojitých uvozovkách nic z toho, co zde bylo řečeno neplatí. Opište jej naprosto beze změny (i kdyby obsahoval posloupnost mezer nebo složené závorky) (1 bod). Tento program implementujte pomocí konečného automatu.
Nové: intervalová aritmetika, datový typ struktura (struct), struktura jako návratový typ funkce a jako datový typ parametrů, čtení hodnot pomocí scanf po dvojicích
Napište program pro výpočet celkového odporu paralelně propojených rezistorů. Hodnoty odporů jednotlivých rezistorů budou zadány na standardním vstupu v následujícím formátu:
m1 e1 m2 e2 m3 e3 ...
kde hodnota mi představuje nominální hodnotou odporu daného rezistoru a hodnota ei představuje chybu této hodnoty v procentech (třídu přesnosti daného rezistoru). Řada takto zadaných hodnot končí, když funkce pro čtení ze vstupu detekuje konec souboru (vrátí konstantu EOF). Program by měl zpracovat libovolně dlouhou řadu hodnot. Výsledek vypisujte ve stejném formátu, jako vstupní hodnoty, tedy jako střední hodnotu výsledku a chybu v procentech.
Návod: Pro řešení použijte intervalovou aritmetiku. Operace v této aritmetice lze definovat například takto:
Hodnotu odporu ukládejte jako interval, tedy dvojici hodnot pomocí datového typu struktura a vytvořte si sadu podprogramů pro jednotlivé operace nad intervaly. Pomocí těchto operací pak realizujte výpočet paralelní kombinace dvou rezistorů a postupně jej aplikujte na celou řadu (Ricelkovy = Ri-1celkovy // Ri).
Nové: čtení formátovaných hodnot s oddělovači, datový typ pole, ukazatel+dynamicky alokované proměnné, operace modulo
Do železáren přijíždějí nákladní vlaky se surovinami a aby byly co nejlépe využity, jsou vagóny po vyložení znovu naplněny struskou a železnými ingoty a odvážejí je pryč. Pracovník, který má na starosti efektivitu provozu se rozhodl, že si bude zaznamenávat, jaký čas stráví každý vagón v továrně od okamžiku jeho příjezdu do okamžiku jeho odjezdu. Pro tyto účely slouží počítač, který sleduje pobyt vagónů v továrně a při odjezdu každého vagónu vždy vrátí údaj ve formátu HH:MM:SS (hodiny, minuty, sekundy) udávající dobu pobytu vagónu v továrně. Náš pracovník má následující problém: z řady těchto údajů ho zajímá vždy součet posledních N časových hodnot (maximálně), aby mohl vypočítat průměrnou dobu, kterou strávily vagóny posledního vypraveného vlaku v továrně (vlak bude mít délku N). Napište program, který tento údaj vypočítá a vypíše opět ve formátu HH:MM:SS.
Návod: Vytvořte si sadu podprogramů pro práci s časem (součet časových údajů, převod trojice hodnot na počet sekund a zpátky, a podobně). Program bude očekávat jako parametr příkazového řádku hodnotu N a na standardním vstupu bude očekávat řadu časových údajů. Tyto údaje lze načítat pomocí funkce scanf("%d:%d:%d", &h, &m, &s).
Protože nás zajímá jen posledních N hodnot z řady a dopředu nevíme, jak bude řada dlouhá, nemůžeme postupně sčítat všechny hodnoty ani si nemůžeme uložit celou řadu do pole (nevíme jak by muselo být dlouhé). Vystačíme si s polem délky N, které si vytvoříme dynamicky na začátku programu a na konci jej uvolníme. Při načítání řady budeme ukládat hodnoty do tohoto pole a pokud bude na vstupu více hodnot než N, vždy přepíšeme nejstarší údaj novější hodnotou. Na konci stačí sečíst všechny prvky pole. (Toto pole můžeme nyní nazývat fronta.)
Pro práci časovými údaji i s naším polem využijeme operaci modulo --- zbytek po celočíselném dělení, v jazyce C jde o operátor %. U časových údajů jej lze využít při převodu mezi údajem vyjádřeným v počtu sekund a údajem tvořeným trojicí hodnot (hh:mm:ss). Pro implementaci fronty využijeme s výhodou toho, že výsledek operace x%N vždy leží v intervalu <0, N). Pole proto budeme indexovat proměnnou i, jejíž hodnotu budeme inkrementovat následujícím způsobem, čímž zajistíme přepsání vždy nejstaršího prvku v poli:
i = ++i % N; pole[i] = hodnota;
Operacemi s modulem se zabývá modulární aritmetika.
Nové: konstrukce rekurzivních podprogramů, cyklus for, princip půlení intervalu
Vytvořte funkci realizující binární vyhledávání v jednorozměrném poli celých čísel, která vrátí index hledaného prvku nebo zápornou hodnotu, pokud prvek v poli nenalezne. Otestujte tuto funkci na vzestupně seřazené posloupnosti čísel, která budou uložena v poli dynamicky alokovaném na hromadě. Zamyslete se, jak byste úlohu řešili bez použití rekurze.
Nové: Fibonacciho posloupnost, Fibonacciho králíkárna, převod rekurzivního algoritmu na iterační algoritmus
Vytvořte dva programy (funkce), které vypíší prvních N členů Fibonacciho posloupnosti. Jednou rekurzivně, podruhé nerekurzivně. Odhadněte (nebo vypočítejte) počet kroků, které musí jednotlivé algoritmy vykonat v závislosti na zadané hodnotě N.
Nové:
Vytvořte dva programy (funkce), které vypíší prvních N řádků Pascalova trojúhelníku. Jeden výpočet bude probíhat rekurzivně a druhý iteračně.
Poznámka: vytvořte rekurzivní funkci, která vypočte hodnotu n-tého prvku na k-tém řádku.
Nové: výpočet mocniny s lepší než lineární složitostí
Vytvořte funkci, která bude provádět výpočet mocniny s logaritmickou místo s lineární složitostí.
Návod: Zapište výpočet mocniny jako rekurzivní problém, vzpomeňte si na vzorečky pro práci s mocninami o stejném základu a skombinujte je se znalostí principu půlení intervalu.
Nové: modulární aritmetika, princip kongruence
Vytvořte funkci, která vrátí posledních N číslic faktoriálu z čísla X. Předpokládejte, že číslo X bude typu long long a velikost čísla N nebude větší než 19. Funkce musí být schopna pracovat s celým rozsahem vstupního datového typu. Můžete pracovat pouze s celočíselnými datovými typy.
Nové: Algoritmus Hanojské věže, zkoumání složitosti algoritmů
Vytvořte program, který bude vypisovat posloupnost akcí, které je nutné udělat pro přesun N disků z první na poslední Hanojskou věž.
Problém Hanojských věží: Máme tři jehly a na první z nich je položeno N disků různých velikostí. Nikdy nesmí být položen disk s větším průměrem na disku s menším průměrem. V jednom kroku lze z jehly sundat jediný disk a nasadit jej na jinou jehlu, pokud tím nebude porušeno předchozí pravidlo. Úlohou je v co nejmenším počtu kroků přemístit všechny disky z první jehly na poslední jehlu, přičemž můžeme využít prostřední jehly pro odkládání.
Nové: dynamická alokace vícerozměrného pole
Vytvořte program, který z parametru příkazové řádky přečte celé číslo N, které udává počet řádků Pascalova trojúhelníka. Alokujte dynamicky na hromadě dvojrozměrné pole velikosti NxN a vytvořte funkci, která do něj uloží prvky Pascalova trojúhelníka - prvky, které do trojúhelníka nepatří, naplňte hodnotou 0. Dále vytvořte funkci, která tuto matici vytiskne na standardní výstup.
Nové: soubory
Vytvořte program, kterému uživatel zadá jako parametr z příkazové řádky jméno souboru. V tomto souboru se bude nacházet matice celých čísel ve formátu:
R S a11 a12 .... a1S a21 a22 .... a2S . . . . aR1 aR2 .... aRS
Na prvním řádku jsou rozměry matice (R - řádky, S - sloupce) a na dalších řádcích se nachází prvky matice oddělené bílými znaky. Napište funkci, která pro tuto matici alokuje 2D pole správné velikosti a vrátí načtenou matici. Dále vytvořte funkci, která načtenou matici vypíše na standardní výstup ve stejném formátu, jako vstupní soubor. Detekujte případné chyby ve vstupním souboru.
Nové: Použití všech dosud nabytých znalostí dohromady.
Navažte na předchozí úlohu. Vytvořte funkce, které provedou nad maticí (maticemi) následující operace a použijte je v programu, který je bude volat podle zadaného parametru příkazové řádky:
Matice načítejte ze souborů zadaných jako parametry příkazového řádku. Funkce samy o sobě nebudou nic vypisovat. Budou vracet výsledek nebo chybový kód. Výsledky tiskněte na standardní výstup stejným způsobem jako v předchozí úloze. Případná chybová hlášení se vypíší mimo ně (ideálně ve speciální funkci pro výpis chybových hlášení). Celkový návrh programu bude hodnocen až 4 body.
Nové: prefixový zápis výrazů, speciální forma define
Napište proceduru (dvě procedury), která vypočte obsah trojúhelníku pomocí Heronova vzorce:
s = (a+b+c)/2
P = odmocnina( s(s-a)(s-b)(s-c) )
Každý vzorec implementujte jako jednu proceduru. Existují dvě možnosti, jak to udělat. Která z nich je efektivnější a proč?
Nové: speciální forma if
Vytvořte dvě procedury pro výpočet kořenů kvadratické rovnice. Ošetřete situace, kdy zadaná rovnice nemá žádné řešení a kdy má nekonečně mnoho řešení.
Nové: rekurze, koncová rekurze (tail rekurze)
Vytvořte proceduru pro výpočet hodnoty faktoriálu. Vytvořte dvě verze této funkce, kdy první verze bude využívat obyčejnou přímou rekurzi a druhá verze bude používat koncovou rekurzi. Pomocí ladícího nástroje sledujte, jak se liší výpočetní proces obou těchto verzí.
Pomůcka: Pro sledování hloubky zanoření testované procedury, vložte na začátek svého programu příkaz
(require (lib "trace.ss"))
Před zavoláním samotné testované funkce zapněte trasování příkazem
(trace faktorial)
(faktorial 10)
Podobně jako v předchozí úloze vytvořte rekurzivní a koncově rekurzivní verzi procedury pro výpočet Fibonacciho čísel. Pomocí trasování otestujte oba algoritmy pro menší hodnoty argumentu (do cca 10). Vypočítejte hodnotu tisícího Fibonacciho čísla (fib 1000). Chovají se obě verze algoritmu stejně? Proč?
Vytvořte procedury pro:
Nové: vedlejší efekty funkcí, speciální forma begin, želví grafika ve Scheme, pojem fraktál
Seznamte se s techpackem pro želví grafiku (podle pokynů vyučujícího). Realizujte
Realizujte proceduru pro výpočet posloupnosti, která vede k řešení problému Hanojských věží.
Vypočtěte největšího společného dělitele pomocí Euklidova algoritmu: r = x mod y : NSD(x, y) = NSD(y, r)
Nové: funkce time pro měření doby běhu procedur
Realizujte procedury, které budou umocňovat celá čísla s lineární a s logaritmickou časovou složitostí (exp base exponent), (expl base exponent). Pomocí funkce time ověřte jejich časovou složitost pro zvolený konstantní základ a větší hodnoty exponentů (sestavte tabulku pro hodnotu exponentu 25000 - 250000).
Zamyslete se, jak funguje modulární aritmetika. Realizujte funkci, která bude schopna efektivně a správně vypočítat výraz:
105072^2019799098211 mod 101 (mocnina modulo 101)
Realizujte další základní aritmetické operace v modulární aritmetice. Lze ke všem najít inverzní funkce?
Nové: tečkové páry (cons, car, cdr), modulární aritmetika, quotient, remainder
Vytvořte sadu podprogramů, které budou umět sčítat, odečítat a převádět časové údaje vyjádřené pomocí tečkových párů s touto podobou: (hodiny . minuty). Počet hodin výsledku nesmí být větší než 23 a počet minut výsledku nesmí být nikdy větší než 59 a menší než nula (počítejte v aritmetice modulo 24 a modulo 60). Údaje na vstupu tuto podmínku splňovat nemusí. Implementujte tyto podprogramy:
Demonstrujte funkčnost těchto podprogramů na vhodně zvolených úlohách. Např.:
Zamyslete se nad tím, jak byste rozšířili zadanou úlohu, aby bylo možné počítat i s dny a sekundami.
Upravte funkce v předchozí úloze bez použití tečkových párů (a seznamů). Hlavičky funkcí musí zůstat beze změny, jen parametry a výsledky již nebudou tečkové páry, ale nová reprezentace časového údaje. Na stejných úlohách, jako minule, demonstrujte funkčnost nové implementace.
Nové: lineární seznam, list, null?, list?
Vytvořte funkce pro otočení prvků v lineárním seznamu. Funkce realizujte pomocí koncové rekurze. Demonstrujte jejich funkčnost na vhodně zvolených datech.
Pomocí tečkových párů realizujte abstraktní datový typ interval se základními aritmetickými operacemi (viz podobná úloha výše, kterou jste řešili v jazyce C). Vytvořte i převodní funkce mezi zápisem intervalu v notaci (min . max) a (střed . +-procenta). Pomocí tohoto abstraktního datového typu spočítejte výsledný odpor paralelní kombinace dvou rezistorů: R1 = 100 Ohm +-10%, R2 = 250 Ohm +-5%. Použijte tyto dva vztahy pro výpočet 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é? Proč?
Pomocí seznamů vytvořte abstraktní datový typ množina. Realizujte alespoň tyto operace: vložení prvku, odstranění prvku, sjednocení množin, průnik množin, rozdíl množin. Demonstrujte jejich funkčnost na vhodných příkladech.
Pomocí ADT množina, realizovaném v minulé úloze najděte všechna prvočísla menší než zadané číslo N. Vyhledávání řešte algoritmem Eratosthenovo síto.
Napište skript pro příkazový shell bash, který bude vypisovat obsah aktuálního adresáře a bude reagovat na tři parametry příkazové řádky:
Skript implementujte pomocí funkcí.
Nové: příkazy sort, printf, přesměrování souborů
Vytvořte v jazyce C jednoduchý program, který spočítá počet řádků na standardním vstupu a vytiskne jejich počet. Pokud bude některý řádek delší než rozumný počet znaků (odhadněte), program bude vstup považovat za binární a vrátí jako návratovou hodnotu programu (exit kód) hodnotu 1, jinak jej bude považovat za textový a vrátí hodnotu 0. Dále vytvořte skript v BASHi, který projde všechny soubory v aktuálním adresáři a na výstup vytiskne tabulku všech souborů a počtu jejich řádků. Soubory, které váš program označí za binární z výpisu vynechte.
Zkuste s kombinací konvenčního programu a skriptu experimentovat. Například můžete doplnit parametry céčkového programu tak, aby přepínaly počítání řádků, slov, vět a podobně - exit kód pak může detekovat i špatné parametry. Pomocí programu sort zkuste vámi vyprodukovanou tabulku seřadit podle počtu řádků (slov, vět) jednotlivých souborů.
Nápověda:
man printf
$? - exit kód posledního provedeného příkazu
man sort
Nové: příkazy grep, tar, (gzip), date
Napište skript, který v aktuálním adresáři vyhledá všechny soubory, které obsahují text vašeho jména vytvoří z nich archiv moje-soubory-datum.tar.gz (datum v názvu souboru musí skript nahradit aktuálním datem).
Nápověda:
man grep
$? - exit kód posledního provedeného příkazu
man tar
man date
date '+%d.%m.%Y'
Napište skript, který provede nejméně 5 testů nad programem, který jste řešili jako pololetní projekt v jazyce C. Skript uloží do souboru protokol o kompilaci programu a poté údaje o vykonaných testech (např. porovnání se soubory se vzorovými výsledky). Skript musí používat podprogramy (například každý test v jednom podprogramu) a musí používat řídící struktury (podmíněný příkaz, cykly, atd.). Snažte se celý skript a jednotlivé testy navrhnout tak, aby bylo snadné přidávat další testy, a abyste odhalili co nejvíce potenciálních chyb v programu (testy nelegálních parametrů, testy extrémních vstupních hodnot - prázdný soubor, nula, obrovské vstupní hodnoty, atd.).
Doplňte předchozí úlohuo sadu skriptů, které budou umět provádět tyto akce:
POZOR! Skripty musí být konfigurovatelné. Veškeré věci, které by bylo dobré měnit soustřeďte do konfiguračního souboru.
Nové:Získávání parametrů příkazové řádky, čtení znaků standardního vstupu metodou System.in.read(), zápis na standardní výstup metodami System.out.println(), System.out.printf().
Napište jazyce Java program, který ze standardního vstupu opíše z každého řádku prvních N znaků na standardní výstup. Parametr N bude zadáván z příkazového řádku.
Nápověda:
Nejprve vytvořte program, který bude mít hodnotu N zabudovánu napevno, teprve potom ji načtěte z příkazového řádku.
Naučte se hledat důležité informace na stránce Java API.
Řetězec převedete na hodnotu pomocí metody Integer.valueOf() - podrobnosti najděte na stránce Java API.
Pro správnou funkci metody System.in.read je potřeba odchytit výjimku IOException pomocí konstrukce:
try
{
// čtení pomocí System.in.read();
}
catch (IOException e)
{
e.printStackTrace();
}
Nové: Třídy, balíky, zapouzdření.
Vytvořte abstraktní datový typ (třídu) Interval nad typem double, který bude obsahovat tyto operace:
Funkčnost výsledného ADT ověřte na výpočtech s elektrickými součástkami se zadanými třídami přesnosti.
Nové: Tvorba balíků, tvorba tříd, metody, proměnné objektu.
Napište třídu Histogram a umístěte ji do balíku vpi.histogram. Při konstrukci třídy musí jít specifikovat, kolik hodnot bude třída schopna pojmout (předpokládejte, že se bude zaznamenávat četnost kladných hodnot velikosti integer). Objekt této třídy musí být schopen následujících činností:
Vytvořte třídu Main, která otestuje funkčnost třídy Histogram tak, že přečte po znacích standardní vstup a na výstup vypíše relativní četnosti znaků, které se vyskytly na vstupu v procentech. Znaky, které na vstupu nebyly do výpisu nezahrnujte. Dále vypište samostatně nečetnější znak a počet jeho výskytů + relativní četnost a počet všech přečtených znaků. Výstup přehledně naformátujte.
Nápověda:
System.in.read()
System.out.printf()
Nové: Abstraktní třídy, dědičnost.
Modifikujte předchozí úlohu tak, že vytvoříte abstraktní třídu vpi.histogram.Histogram a její potomky, kteří budou pracovat nad datovými typy byte a integer. Ověřte správnou funkčnost implementovaných tříd pomocí vhodného programu, který bude ovládaný pomocí parametrů příkazového řádku. Pro získání bodů musí jít o funkční 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 č.1: Zamyslete se, jak by tento program vypadal, kdyby se místo abstraktní třídy použilo rozhraní (interface). Pokuste se tuto variantu implementovat. Jaké má toto řešení výhody a jaké nevýhody?
Prémie č.2: Zamyslete se, jak by tento program vypadal s využitím genericity (od verze Javy 1.5). Pokuste se tuto variantu implementovat. Jaké má toto řešení výhody a jaké nevýhody?
Nové: diagram tříd, objektový návrh
Nakreslete diagram tříd popisující implementaci hry "Člověče, nezlob se!". Vytvořte textový popis úlohy, vyberte kandidáty na třídy, zakreslete dědičnost a kooperaci jednotlivých tříd.
Nové: Slovní úlohy.
Vytvořte třídu simulující opravnu automobilů. V opravně se budou uchovávat záznamy o právě opravovaných autech (typ, spz, cena za opravu, ...). Opravna má určitou maximální kapacitu - maximální počet současně opravovaných aut. Pokud přijde zákazník a je plno, bude odmítnut. Třída reprezentující opravnu bude mít metodu pro tisk údajů o všech právě opravovaných autech.
Napište jednoduchý program, který bude demonstrovat všechny schopnosti implementovaných tříd.
Modifikujte řešení předchozí úlohy tak, aby opravna byla schopna přijímat jedno i dvoustopá vozidla (motocykly, auta). Cena za opravu se bude počítat pro automobily a pro motocykly odlišně. Stejně tak se bude vypisovat odlišným způsobem záznam o vozidle. Při implementaci využijte dědičnost a polymorfismus.
Správnou funkčnost demonstrujte pomocí vhodného testovacího programu.
Poslední modifikace: 8. February 2010. Pokud v tomto dokumentu narazíte na chybu, dejte mi prosím vědět.