Pokyny: Snažte se ve vlastním zájmu (příprava na zkoušu, procvičení) používat (účelně) pokročilejších metod programování, tj. vhodná struktura podprogramů, vhodné datové struktury (dynamické), objektové programování. Některé úlohy mají více variant. Vyberte si tu, která vám připadá nejzajímavější a přitom odpovídá vašim časovým možnostem.
Důležité: Více lidí může klidně odevzdat stejnou úlohu, ale musí ji každý napsat sám. Při udělování zápočtu budu klást dotazy na drobné úpravy v pogramu, které prověří vaše porozumění programu.

Poznámka: Tady je pár úloh. Pokud máte nápad na jinou úlohu podobného rozsahu, je možné ji po předchozí domluvě použít.

Posledni změna: 11. 9. 2001 Martin Čížek - cizek@mbox.troja.mff.cuni.cz
Zpět na hlavní stranu

Úloha (práce s funkcemi):

Napište program obsahujíci proceduru pro výpočet integrálů funkcí, přičemž funkce budou moci být reprezentovány následujícími způsoby:
polynom, tabulka hodnot+interpolace, řada (koeficienty zadány jako TYPE ifc=FUNCTION(n:integer):real), integrál od 0 do x z jiné reálné funkce
(např ERF(x)=Integral od 0 do x z exp(-x*x)). Vyzkoušejte proceduru pro každý typ funkce na vhodném příkladu.

Napište pogramovou jednotku (unit) pro sčítání, násobení a násobení reálným číslem obecných objektů a v ní výpočet funkcí sin(x), cos(x) a exp(x) (Taylorovou řadou). Potom napište program který tuto jednotku využije k výpočtu těchto funkcí pro matice a komplexní čísla.
(Měl pravdu starý pan generál, který pravil: "Když mi jsme bojovali, tak jsme stříleli pod takovými úhly, že kosínus byl větší než 1" ? Nápověda: kolik je cos(5i)?)
Možná rozšíření: 1) Vyzkoušejte si, že rotaci v rovině kolem počátku o úhel Fi lze spočíst následovně:
                                  (x',y') =exp(i*Fi*L).(x,y),  kde i je imaginární jednotka tečka značí násobení matice vektorem
                                   a L je hermitovská matice s řádky (0,i) a (-i,0) nazývaná "generátor rotace". (pozn: dá se zobecnit pro 3D prostor i horší entity.)
                            2) Můžete program rozšířit o práci s QUATERMIONY.

V Izraeli jezdí síť autobusových linek na základě následujícího systému: Autobus přijede prázdný na první zastávku a čeká až někdo nastoupí. Řidič se zeptá kam kdo jede a podle počtu cestujících určí cenu pro každého tak, aby pokryl náklady na cestu včetně přiměřeného zisku. Když je cena moc velká, takže ji některý z cestujících nemůže akceptovat, čeká se, až přijde další člověk na zastávku. Napište program simulující takovýto systém. Předpokládejte kruhovou trasu autobusu. Na vstupu budou data pro autobusy a pro příchody cestujících a jejich cestovní plány:

Příklad vtupního souboru:
{Trasa:}
{     Delka    poc. zast.    na kterem kilometru jsou zastavky}
T      100             8        0      5      20      27      36      87      89      94

{Autobusy: V=prum.rychl., Nakl=naklady vcetne zisku, od,do= pracovni doba,
      P=pocet sedadel, C=cislo zastavky kde zacina pracovni dobu}
{           ID         V.         Nakl.    od       do           P       C   }
A       1001        60           10.5    6:00   14:00      12       5
A       1002        80           15.1    8:00   16:00      10       1
.
.atd

{Cestujici: max.c= maximalni akceptovatelna cena za jeden kilometr}
{          ID         odkud   kam     max. c.     cas prichodu}
C        2001         1          5            1.5          7:00

Výstup: průběžné informace o situaci + na závěr kolik který autobus ujel a vydělal, kolik cestujících přepravil a kolik jich zůstalo na zastávkách.

Možná zobecnění:

1) U každého člověka se roste maximální akceptovatelná cena vhodným způsobem s časem po který musí čekat.
2) Lidi nečte ze souboru, ale generuje náhodně podle vhodného modelu (na některé zastávce je továrna takže tam budou pravděpodobněji jezdit ráno a odtud večer atd.)

Úloha (Simulace dálničního okruhu):

Napište program simulující dálniční okruh. Dálniční okruh je zadán svojí délkou, počtem pruhů a počtem odboček. Pro každou odbočku je uvedeno na kterém kilometru okruhu se nachází. Na vstupu jsou zadány příjezdy automobilů (je též možné je generovat automaticky dle nějakých pravidel). Každý automobil je charakterizován svojí maximální rychlostí, délkou a údajem o času příjezdu a odkud kam směřuje. Při simulaci předpokládejte, že rychlost je dána celým číslem (v metrech za sekundu) a čas plyne po sekundách. Bezpečná vzdálennost mezi auty je vzdálennost, kterou auto ujede za deset sekund. Je třeba dávat přednost při přejíždění z pruhu do pruhu. Odbočovat je povoleno jen z pravého pruhu. Pro jednoduchost můžete předpokládat, že auto může měnit rychlost okamžitě. Možná rozšíření: můžete zkusit zobrazit situaci schematicky na obrazovku (stačí pomocí písmenek, ale možná i grafika) dále můžete zkusit započítat, že každé auto může vyvinout jen jisté maximální zrychlení, či zpomalení.

Příklad možného vstupního souboru:

{ Dalnice }
       delka(v metrech)     pocet pruhu     počet odboček
D         10000                       3                       5
O                0
O          2000
O          4000
O          7000
O          8000

{Auta }
       ID       prijezd(s)     max rychlost(km/¨h)   delka(m)  odkud  kam (cisla odbocek)
A   1001           1                  60                          12            1               5
A   1002      100                 120                            3            1               4
.
.
.(pokracuje dále-musí obsahovat dost aut, aby se něco dělo - předjíždění, dávání přednosti při vjezdu na okruh)
 

Vzor výstupu:

CAS      ID     pruh   kilometr          co se deje
1         1001      0          0             vjizdim na dalnici
1         1001      1          0             zarazuji se
100     1002      0         0             vjizdim na dalnici
100     1002      1          0             zarazuji se
195     1002      2       3.120         prejizdim z pruhu 1 do pruhu 2
203     1002      2       3.330         prejizdim z pruhu 2 do pruhu 1
250     1002      2       8.000         vyjizdim z dalnice
.
.
.
 

Polynom je reprezentován pomocí lineárního spojového seznamu tak, že v každém prvku seznamu jsou uloženy hodnoty koeficientu a exponentu jednoho členu polynomu. Prvky seznamu jsou uspořádány sestupně podle hodnot exponentu. Členy s nulovým koeficientem se do seznamu neukládají. Napište program, který přečte ze souboru sloupec polynomů s celočíselnými koeficienty a provede s nimi zadané operace. Definice operací jsou od definic polynomů odděleny řádkem začínajícím znakem # a podobně jsou ukončeny definice operací. V definicích operací se na polynomy odkazuje symboly p1,p2,...,pn, kde n je počet vstupních polynomů. Operace jsou složeny z elementárních operací + - * a závorek. Při vyhodnocování výrazů respektujte priority operací a závorky.

Vzor vstupního souboru:

5x^2+18x^23+5
13x^22-6x^15
4x+2x^2+1
##### Konec definice polynomu, zacatek definice operaci #####
p1+p2+p3
p1*p3-p2
p1*p2+p2*p3+p1*p3
p1*p2*p3
(p1-p2)*(p2-p3)*(p3-p1)
##### Konec dat #####

Vzor výstupu:

p1=18x^23+5x^2+5
p2=13x^22-6x^15
p3=2x^2+4x+1
p1+p2+p3=18x^23+13x^22-6x^15+7x^2+4x+6
p1*p3-p2=...
...

Úloha (Cyklisti):

Uvažujme město zadané stejným způsobem jako v úloze o cyklistovi na cvičení (viz též zde). Předpokládejte, že doba, kterou potřebuje cyklista na překonání vzdálennosti mezi sousedními křižovatkami je T=(p+10) minut, kde p je převýšení vezi těmito křižovatkami, vždy však nejméně jedna minuta (když je klesání strmější než 10 stejně musí cyklista brzdit). Mějme několik cyklistů, jezdících v tomto městě. Každý má svoje pravidla, např. Bloudička se rozhoduje na každé křižovatce náhodně kam pojede, Lenoch jede vždy tam kde je to nejméně do kopce, Sportovec naopak, Cílevědomec tak, aby směřoval co nejvíce k zadanému cíli, ... Všichni cyklisti dodržují jednosměrky a kromě toho pokud dojedou na křižovatku dávají si přednost podle pravidla pravé ruky.
Vymyslete si několik cyklistů (jejich pravidla pro rozhodování) a napište program, který bude simulovat závod. Na začátku si uživatel vybere ze seznamu, kteří cyklisti pojedou a zadá start a cíl. Během závodu poběží čas a program bude sledovat činnost každého cyklisty. Závod skončí, jakmile některý cyklista dorazí do cíle. Program poté vypíše dráhu nejrychlejšího cyklisty a polohy ostatních. Pro srovnání též nejrychlejší možnou trasu (návod: nejrychlejší trasu naleznete algoritmem vlny jako na cvičení, ale s použitím prioritní fronty, aby se zohlednily různé rychlosti mezi křižovatkami).

Naprogramujte Conwayovu hru Life. Vyřešte vstup úvodní pozice (počáteční konfigurace), zadání požadovaného počtu generací, výpis každé generace a překročení mezí hrací plochy. Můžete využít grafiky, ale stačí mi vhoné zobrazení textovými znaky (případně obarvenými).

Hra Life je model života bakterií. Hraje se vrovině ve čtverečkové síti. Každé políčko sítě představuje buňku, která může být živá nebo mrtvá (tj. bakteri v ní žije nebo nežije). Počáteční konfigurací je výchozí rozmístění živých buněk v této síti. Stav buňky v následujícím kroku závisí na počtu živých buněk v jejím okolí (okolím buňky rozumíme 8 sousedních políček) a je dán tzv. zákony života: živá buňka přežije do následujícího kroku, jestliže v jejím okolí jsou dvě nebo tři živé buňky, jinak zahyne na osamocení (jestliže v jejím okolí nejsou živé buňky nebo je tam jen jedna živá buňka), nebo na přemnožení (jestliže v jejím okolí jsou aspoň čtyři živé buňky). V mrtvé buňce vznikne nová bakterie, jestliže jsou v jejím okolí přesně tři živé buňky. V jednom kroku mění svůj stav všechny buňky najednou - tak vznikne nová generace.

Poznámka: Hru lze upravit mnoha způsoby. Nápady, které je třeba domyslet (pokud se rozhodnete pro upravenou variantu):
1) Více druhů bakterií (nutno stanovit vhodná pravidla - zákony života!).
2) Možno doplnít prostředí ovlivňující život (např potrava tekoucí z jednoho rohu, kterou bakteri spotřebovávají).
3) Možno dovolit, aby některá pravidla byla určena "geneticky" a genetická informace se vhodně mixovala při vzniku nové bakterie.
4) Možná vás napadne ještě jiná varianta. Pamatujte na to, že pravidla musí být pokud možno jednoduchá a přehledná a musíte je vyzkoušet, jestli dávají něco rozumného (aby například všechno nevymřelo po pár tazích).

Naprogramujte hru na motivy hry PacMan, tj. v bludišti je symbol hráče a pak několik příšer, které ho můžou sežrat. Hráč má za úkol posbírat nějaké předměty v co nejkratším čase a při tom se nenechat sežrat. Symbol hráče je ovládán z klávesnice, příšery se hýbou samy podle vhodně zvolené strategie. Přitom je nutno vyřešít co se stane když se potkají.
Hru je možno celkem libovolně upravit. Záleží jen na vaší fantazii. Zajímavé je udělat náhodné generování "rozumného" bludiště, tj. bez uzavřených prostor znichž se nelze dostat. Nezapomeňte používat co jste se naučili na přednášce! Grafický výstup není nutností, hru lze naprogramovat i pomocí textových symbolů.

OBTÍŽNĚJŠÍ ÚLOHY:

Úloha (Mnohostěny):

Platónovská tělesa jsou pravidelné mnohostěny složené z pravidených mnohoúhelníků tak, že v každém vrcholu se stýká stejný počet hran. Když si předepíšeme, z kterého mnohoúhelníku a jakým způsobem (kolik hran vychází z vrcholu) má být mnohostěn sestaven, můžeme počet stěn najít následujícím způsobem:

1) Začneme s jedním mnohoúhelníkem a zapamatujeme si jeho obvod.
2) Na existující obvod přilepíme další mnohoúhelník a vynecháme z obvodu co tam už nepatří.
3) Opakujeme bod 2 dokud obvod sám netvoří jednoduchý mnohoúhelník

Příklad: Z rovnostraných trojúhelníků stavíme tak, že v každém vrcholu se stýkají tři. K prvnímu trojúhelníku přilepíme další - obvod má 4 hrany a 4 vrcholy. Z toho ze dvou vrcholú už vycházejí tři hrany. Do jednoho z nich přilepíme další trojúhelník. Obvod se redukuje na tři hrany, z nichž všechny už jsou "nasycené", tj. algoritmus končí přilepením posledního trojúhelníku.
Úkol: Napište program, který tento algoritmus realizuje pomocí vhodých dynamických datových struktur.
Poznámka: Funkční program v této podobě mi bude stačit, ale pokud chcete udělat něco zajímavějšího (ve třech dimenzích existují jiné efektivnější metody na něž nepotřebujeme počítač), zkuste zobecnit program do čtyř dimenzí (Kolik těles by asi našel 4D-Platón?), nebo pro hledání Archimédovských mnohostěnů (více typů mnohoúhelníků, ale všechny vrcholy stejné).

Napište program pro nalezení algoritmu hledajícího kuličku s daným pořadím (podle hmotnosti) na rovnoramenných vahách na co nejmenší počet vážení. Vstupem bude počet kuliček a pořadové číslo kuličky, kterou chceme naléz. Nápověda: Informaci o kuličkách můžete reprezentovat pomocí orientovaného grafu, v němž každá hrana ukazuje z těžší na lehčí kuliču. Hledání nejrychlejšího algritmu vážení pak probíhá prohledáváním prostoru takovýchto grafů algoritmem vlny. Pozor na: rozpoznání ekvivalence dvou grafů, správnou úpravu grafu po provedení dalšího vážení (nezapomeňte na tranzitivitu operace <).

Napište programovou jednotku (unit) pro reprezentaci abstraktní grupy. V rámci této jednotky napište proceduru, která zjistí zda lze ze zadaného prvku A grupy dostat prvek B grupovým násobením posloupnosti prvků grupy patřícím do předem zadané množiny {P1,P2,..,Pn}. Aplikujte tuto proceduru na skládání malé Rubikovy kostky 2x2x2.

---