Zápočtové programy z jazyka C++

Zápočtové programy

Programy existují ve variantě základ a variantě náročnější. Každý, kdo má ke dni zadání dvě a méně absencí, přičemž každé dva neodevzdané domácí úkoly (symbol w v docházce) se počítají jako jedna absence, dělá základní variantu. Všichni ostatní musí udělat náročnější zápočtový program.

Program musí při odevzdání fungovat, musí jít přeložit a musí mít bezchybnou práci s pamětí – nástroj Valgrind nesmí najít únik paměti (úniky paměti mohou být detekované v použitých externích knihovnách). Narazíte-li na komplikaci či chybu v zadání, neváhejte se na mě obrátit prostřednictvím mailu. Nekonzultujte, prosím, programy mezi sebou. Při opisování nebude zápočet udělen.

Základ – Fraktálovač 9000

Jako vývojář u světoznámého dodavatele výukového softwaru máte za úkol přiblížit žákům problematiku fraktálů. Rozhodnete se proto vytvořit demo aplikaci, na které byste si mohli vyzkoušet možné postupy. Vaše aplikace, kterou jste pracovně pojmenovali Fraktálovač 9000, bude umožňovat vykreslování dvou různých fraktálů s různou přesností a různými barvami. Výsledná aplikace bude vypadat podobně jako ta na obrázku.

Okno aplikace Fraktálovač 9000

Implementace

Program bude využívat knihovny Qt pro vykreslené hlavního okna. V programu je možné používat třídy ze standardní šablonové knihovny jazyka C++. Kostra programu a bodový soupis úkolů je k dispozici níže.

Stáhněte si zdrojový kód. Zkuste si program přeložit a zobrazit si okno aplikace.
Implementujte třídu Color, která bude reprezentovat barvu v lineárním prostoru RGB. Třída bude podporovat sčítání barev, odčítání barev a násobení barvy necelým číslem. Každou složku barvy reprezentujte jako necelé číslo typu float. Doplňte do třídy metody getRed(), getGreen() a getBlue(), které budou mapovat necelé číslo na celé číslo z intervalu 0 až 255 tak, že nule bude odpovídat hodnota 0.0 a 255 hodnota 1.0. Ostatní hodnoty budou lineárně dopočítané, přičemž záporné hodnoty a hodnoty větší než 1.0 se budou ořezávat na minimální, resp. maximální povolené celé číslo.
Implementujte třídu LinearPalette, která bude potomkem abstraktní palety. Třída obdrží v konstruktoru dvě barvy a v metodě color() bude vracet lineární interpolaci těchto barev v závislosti na parametru metody.
Implementujte třídy Newton a Mandelbrot, které budou potomky třídy AbstractFractal. Třída Newton bude reprezentovat Newtonův fraktál pro polynom x^3 - 1. Třída bude v konstruktoru očekávat rozlišení obrazu (v pixelech na jednu jednotku), hranici přesnosti výpočtu a ukazatel na paletu, která bude použita pro vykreslení této instance fraktálu.
Třída Mandelbrot bude představovat Mandelbrotovu množinu. Třída bude v konstruktoru očekávat rozlišení obrazu podobně jako třída Newton, dále počet iterací výpočtu a ukazatel na paletu.
Metody draw() obou výše zmíněných tříd dostávají ukazatel na třídu FractalPainter, která se stará o vykreslování plátna na hlavní okno. Tato třída má metodu canvas(), která vrací ukazatel na objekt QImage. Do tohoto objektu je možné kreslit jednotlivé body s použitím metody scanLine(). Každý bod obrázku zabírá tři bajty pro svou červenou, zelenou a modrou složku.
Plátno má omezenou velikost na 512 pixelů. Aby se mohly fraktály správně vykreslovat, je nutné jim sdělit, kolik pixelů zabírá jeden dílek na ose. Pro oba fraktály je vhodné zvolit rozlišení tak, aby 512 pixelů představovalo interval od -2 do 2.

Při vykreslování obou fraktálů je nutné si určit, jaký údaj bude použit pro obarvení bodu. U Mandelbrotovy množiny půjde o počet iterací, které byly nutné k tomu, abychom opustili kruh o poloměru 2 v komplexní rovině. Pokud toto číslo vydělíme limitem na počet iterací, které jsme obdrželi v konstruktoru, dostaneme číslo od 0.0 do 1.0. To lze již použít jako index do palety barev.

U Newtonova fraktálu je situace o něco složitější. Pro každý bod můžeme spočítat počet iterací, které byly potřeba pro dosažení zadané přesnosti. Jelikož ale nemáme maximální počet iterací jako v předchozím případě, je nejprve nutné spočítat iterace pro všechny body a nalézt maximum. Při znalosti maxima již obarvení probíhá stejně jako u Mandelbrotovy množiny.

Náročnější – Autobus 176

Jako vývojáři jste byli přijati do Dopravního podniku po nedávném prohlášení jeho vedení, že outsourcing se nevyplácí. V sekci IT, kde pracujete, se zaměřují na optimalizaci dopravy. Vám, jako čerstvým absolventům, byl svěřen úkol zoptimalizovat množství autobusů na lince 176. K úkolu jste přistoupili vědecky a rozhodli jste se napsat program, který bude simulovat dopravu studentů do školy.

Vytvořte aplikaci, která bude simulovat příchod studentů na zastávku na Strahově a odjezdy autobusů. Na problém lze nahlížet jako na systém s frontou. Studenti přicházejí na zastávku, kde čekají, než přijede autobus. Autobus vždy odveze určité množství studentů a tím zpracuje část fronty. Uvažujte následující předpoklady:

Máte k dispozici celkem n autobusů.
Studenti přicházejí na zastávku s exponenciálním rozdělením se střední hodnotou, která je volitelná.
Je-li na Strahově volný autobus, vyjíždí k zastávce v předepsaném intervalu, který je volitelný.
Autobus, který odjel za Strahova, má dobu návratu danou exponenciálním rozdělením s volitelnou střední hodnotou.
Zastávka má kapacitu 60 studentů. Pokud na plnou zastávku dorazí další student, usoudí, že taková tlačenice nemá smysl a půjde si znovu lehnout, následkem čehož bude vyhozen ze školy pro liknavý přístup ke studiu.
Simulace poběží od 7.00 do 12.00.
Od 7.00 do 9.00 je největší nával studentů. Uvažujte proto střední dobu příchodu studenta na zastávku za poloviční proti normálu.
Od 8.00 do 10.00 je dopravní špička. Uvažujte střední dobu návratu autobusu o 15 minut delší.
Každý autobus má kapacitu 35 lidí. Jelikož jsou ale studenti skladní, uvažujte kapacitu náhodnou v intervalu 35 až 45 lidí.
Měření bude probíhat v intervalech daným exponenciálním rozdělením se střední hodnotou 30 sekund.
Autobusy by neměly jezdit málo naplněné. Každý autobus, jehož obsazenost bude menší než deset studentů, bude zaznamenán jako prázdný.
Pokud podle jízdního řádu má vyjíždět autobus, ale přitom žádný není na Strahově k dispozici, bude toto zaznamenáno jako nedostatečný počet autobusů.

Úkolem je nalézt optimální počet autobusů tak, aby pokud možno žádný nejezdil skoro prázdný a aby studenti vydrželi na škole alespoň do druhého semestru. Výstupem programu by měla být textová statistika různých veličin a též textový soubor, který bude obsahovat data vykreslitelná programem gnuplot. Vzorové výstupy jsou ukázány níže.

measurements: 599
total waiting students: 1309
total measured students: 9534
dropped students: 5
empty busses: 1
insufficient busses: 11
waiting students mean: 15.92
dropped percentage: 0.4 %

Výsledky simulace zobrazené v programu Gnuplot

K implementaci

Program na standardním vstupu bude očekávat parametry simulace v následujícím formátu.

busses  3
student_arrival_time    20
timetable_interval      300
roundtrip_time  3600

Každé klíčové slovo na vstupu bude od hodnoty oddělené tabulátorem. Všechny časové údaje budou v sekundách. Podle tohoto zadání přibude na zastávce jeden student v průměru za 20 sekund, autobus bude vyjíždět ze zastávky každých 5 minut a jeho cesta včetně návratu zabere v průměru jednu hodinu.

Jádrem programu bude systém s frontou. Ten se dá modelovat pomocí událostí. Každá událost bude mít čas v sekundách, kdy nastane, a typ značící, o kterou událost se jedná. Mějme frontu událostí, vždy vezmeme nejbližší nadcházející událost, vyjmeme ji z fronty a necháme ji zpracovat. Při zpracování může dojít k vytvoření nové události, která musí být do fronty umístěna na správné místo. Dejte pozor, neboť se může stát, že budou existovat dvě události se stejným časem.

Frontu modelujte jako šablonovou třídu reprezentující multimapu. Interně bude multimapa binární strom, kde v každém uzlu bude pole hodnot. Typ klíče bude pevně celé číslo reprezentující čas události v sekundách od počátku měření. Hodnota bude libovolná šablona. Třída musí podporovat vložení páru klíč–hodnota, musí umět vyjmout minimální položku, mít kopírovací konstruktor a poskytovat dopředný iterátor pro seřazené procházení položkami.

Pro pochopení simulace následuje krátká ukázka.

Na začátku je fronta prázdná, jsme v globálním čase nula (v naší simulaci v 7.00 ráno). Do fronty vložíme událost příchodu prvního studenta, např.

event
{
  type = STUDENT_ARRIVAL;
  // čas je vždy v budoucnu
  time = global_time + exponential(student_arrival);
}

Dále vygenerujeme událost pro příjezd prvního autobusu.

event
{
  type = BUS_ARRIVAL;
  time = global_time + bus_arrival;
}

Tato událost bude reprezentovat odjezdy podle jízdního řádu. Pokud je k dispozici autobus, odečte se z čítače studentů jeho náhodná kapacita, spočítá se jeho obsazenost a vygeneruje se událost představující jeho návrat.

event
{
  type = BUS_READY;
  time = global_time + exponential(bus_travel);
}

Pokud autobus nebyl k dispozici v době plánovaného výjezdu, zvýší se čítač nedostatku autobusů a žádný autobus nevyjede.

Dále je dobré mít událost MEASURE, při které se zjistí aktuální počet čekajících studentů. Lze si to představit tak, že v určený čas se dostaví na místo jeden ze zaměstnanců dopravního podniku, spočte stojící a zaznamená si data. Na konci akce se vydělí suma všech čekajících počtem měření a výsledek je průměrný počet čekajících.

Soubor se statistikou bude obsahovat čtyři sloupce. První sloupec bude čas měření v sekundách od začátku simulace. Ve druhém sloupci bude počet aktuálně čekajících studentů na zastávce, ve třetím počet dostupných autobusů v době měření a konečně ve čtvrtém bude počet studentů vyhozených ze školy od posledního měření.

Ke generování exponenciálně rozdělené veličiny lze využít generátor rovnoměrně rozdělených náhodných veličin.

V tomto programu je povolenou používat ze standardní šablonové knihovny pouze datové proudy a třídu std::string.

Odevzdání programu

Řádně fungující program je nutné odevzdat do 30.6.2013, 23.59 SELČ. Jiný termín odevzdání ze závažných důvodů je nutné dopředu domluvit mailem. Jen a pouze zdrojový kód výsledného programu (nikoliv projektové soubory a další pomocné soubory včetně spustitelného programu) pokud možno zabalený v archivu odešlete na mou mailovou adresu.

Navigace

Zápočtové programy z jazyka C++