P-II-1 Druhý večírek
Na večírku se sešlo několik hostů. Víme, kteří z nich se vzájemně
znají a kteří ne. Vztah "znát se" uvažujeme zásadně jako
symetrický, tzn. o libovolné dvojici lidí platí, že buď se
navzájem znají, nebo ani jeden z nich nezná toho druhého. Hosté
se rozhodli vytvořit takové taneční páry, aby spolu tančili vždy
muž se ženou, kteří se spolu znají. Navrhněte algoritmus, který
určí, kolik párů nejvýše může tančit zároveň.
Vstupem programu je počet mužů M, M <= 100, a počet žen Z, Z <= 100, a dále seznam těch dvojic hostí, kteří se spolu znají. Pro jednodušší zadávání vstupu si jednotlivé muže označíme kladnými celými čísly od 1 do M a ženy zápornými celými čísly od -1 do -Z, takže na vstupu bude zadán seznam dvojic celých čísel. Výsledkem bude jediné číslo udávající maximální počet současně tančících párů.
P-II-2 Pokleslá podposloupnost
Budeme zkoumat konečné posloupnosti celých čísel. Podposloupností
délky K vybranou ze zadané posloupnosti rozumíme libovolnou
uspořádanou K-tici čísel takovou, že všechna její čísla se
nacházejí v původní posloupnosti a navíc pořadí čísel v K-tici je
stejné jako pořadí těchto čísel v původní posloupnosti.
O posloupnosti čísel a1, a2, ..., aN řekneme, že je nejvýše s jedním poklesem, jestliže buď ai <= ai+1 pro všechna i od 1 do N-1, nebo pokud existuje jediný index j z rozmezí od 1 do N-1, pro který platí aj > aj+1.
Napište program, který určí délku nejdelší takové podposloupnosti vybrané ze zadané posloupnosti celých čísel, aby byla nejvýše s jedním poklesem. Při návrhu programu se zaměřte na dosažení co největší rychlosti výpočtu.
P-II-3 Maximální okno
Na počítači máme nainstalován operační systém MO-P-Windows
pracující v grafickém rozlišení 300 x 200 bodů. Momentálně máme
spuštěno několik aplikací a na obrazovce je zobrazeno jejich
N oken. Každé okno je obdélníkové (příp. čtvercové), známe přesné
umístění jednotlivých oken. Okna se mohou na obrazovce částečně
nebo úplně překrývat.
Chceme spustit další aplikaci, která potřebuje zobrazit jedno nové okno. Požadujeme přitom, aby nové okno na obrazovce nezakrylo ani část žádného z oken, která jsou tam již zobrazena. Napište program, který určí, jaké největší nové okno lze na obrazovku umístit a kam. Velikostí okna rozumíme jeho plochu.
Na vstupu programu je nejprve zadán počet již zobrazených oken N. Následuje specifikace velikosti a umístění jednotlivých oken. Pro každé z oken jsou zadána čtyři celá čísla x1, y1, x2, y2 představující souřadnice bodu na obrazovce [x1,y1], který tvoří levý horní roh okna, a bodu [x2,y2], v němž leží pravý dolní roh okna. Souřadnice bodů na obrazovce se zadávají tak, že bod v levém horním rohu celé obrazovky má souřadnice [0,0] a bod v pravém dolním rohu má souřadnice [299,199]. První souřadnice nějakého bodu na obrazovce znamená vodorovnou vzdálenost tohoto bodu od levého okraje obrazovky, druhá souřadnice určuje svislou vzdálenost bodu od horního okraje obrazovky.
Výsledkem výpočtu programu bude čtveřice čísel, která představuje souřadnice levého horního a pravého dolního rohu přípustného umístění pro nové okno maximální velikosti (libovolného jednoho umístění, je-li více možností). Pokud již žádné okno nelze na obrazovku umístit, program vypíše čtyři nuly. Požadavek, aby se nové okno nepřekrývalo s žádným z ostatních oken znamená, že žádný hraniční bod nového okna nesmí ležet v jiném okně ani na jeho hranici.
P-II-4 Kombinační sítě
Abeceda je konečná neprázdná množina symbolů, s nimiž kombinační
síť pracuje. Obsahuje vždy speciální symbol @ (prázdný symbol).
Základním stavebním prvkem kombinačních sítí jsou kombinační hradla (dále jen hradla). Každé z nich má dva vstupy a jeden výstup a je jednoznačně určeno svou přechodovou funkcí. Ta každé kombinaci možných hodnot na vstupech hradla (což jsou některé ze symbolů abecedy) jednoznačně přiřazuje hodnotu na výstupu. Symbol @ je funkcí přiřazen právě tehdy, když je přítomen tentýž symbol na kterémkoliv ze vstupů hradla.
Kombinační síť se skládá ze vstupů I1 až In, výstupů O1 až Oma hradel H1 až Hk. Každý ze vstupů hradla Hi je přímo připojen na některý ze vstupů sítě nebo na výstup nějakého hradla Hj, j < i (v síti tedy nemohou vzniknout cykly), případně na něj může být trvale připojen libovolný ze symbolů abecedy (konstanta). Stejným způsobem jsou připojeny i výstupy sítě.
Výpočet kombinační sítě probíhá v taktech. V nultém taktu jsou na všech vstupech sítě vstupní data a na výstupech všech hradel symboly @. V každém dalším taktu se nastaví výstupy všech hradel podle toho, jaké hodnoty byly na jejich vstupech v taktu předchozím. Tímto způsobem se pokračuje tak dlouho, dokud na alespoň jednom z výstupů sítě je symbol @. Poté se výpočet sítě zastaví a její výstupy obsahují výsledek výpočtu.
Podle toho, jak probíhá výpočet, je možné síť rozdělit do hladin. Do i-té hladiny zařadíme ta hradla, která v i-tém taktu mají na svém výstupu platnou hodnotu (tedy jiný symbol abecedy než @) a o krok dříve ještě tuto podmínku nesplňovala. Výpočet tedy bude probíhat tolik taktů, kolik má síť hladin.
Navrhnout kombinační síť řešící danou úlohu znamená zvolit abecedu, popsat přechodové funkce všech použitých hradel (například tabulkou) a určit propojení sítě (tj. vzájemné propojení hradel, vstupů a výstupů). Při návrhu sítě se snažíme dosáhnout co nejrychlejšího výpočtu, což znamená minimalizovat počet hladin sítě.
Kombinační sítě můžeme pro větší přehlednost znázorňovat graficky - jednotlivá hradla jsou reprezentována obdélníčky (nahoře jsou zakresleny vstupy, dole výstup), přičemž hradla v téže hladině se umisťují vedle sebe. Uvnitř každého obdélníčku je označení příslušné přechodové funkce. Nad všemi hladinami jsou zakresleny vstupy sítě, zcela dole pak výstupy sítě.
Hodnotí se nejen správnost, ale také rychlost výpočtu navržené sítě - snažte se tedy dosáhnout co nejmenšího počtu hladin.