První série třetího ročníku KSP
Tyto úlohy pocházejí z desetileté ročenky KSP. Jejich řešení bohužel nemáme v elektronické podobě, takže na ně budete muset přijít sami.Zadání úloh
3-1-1 Číselná posloupnost
Napište program, který pro zadanou posloupnost N celých, kladných i záporných čísel nalezne souvislý úsek této posloupnosti s největším součtem (souvislý znamená, že nevynecháte žádné číslo mezi začátkem a koncem vybraného úseku). U této úlohy je důležitý důkaz správnosti algoritmu.
3-1-2 Logické formule
Logický výraz je:
- velké písmeno
A…Znebo (výraz1opvýraz2), kdeopje jeden z operátorů&,^,>,=, které mají postupně význam „a zároveň“, „nevylučovací nebo“, „implikace“, „ekvivalence“, případně-výraz, kde-znamená negaci logického výrazu.
@ s významem „negace a zároveň“
(tzn. A@B neplatí, pokud platí A a B, A@B=-(A&B) ).
Příklad: ((A^B)&-C) = ((A@(C@C))@(B@(C@C))).
3-1-3 Tenisový turnaj
Je dáno rozlosování n=2k tenistů na základní nulté úrovni turnaje. Je dána matice vzájemných sil hráčů:
| 1 | pokud i porazí j | |
| aij= | 0 | není-li jasný výsledek |
| -1 | pokud j porazí i. |
Napište program, který přečte rozlosování hráčů (permutaci čísel 1… n) a pro zadanou tabulku aij vytiskne čísla hráčů, kteří mohou při daném rozlosování vyhrát.
Příklad pro k=2: Je dána matice
| ( | * | 1 | 0 | -1 | ) |
| -1 | * | -1 | -1 | ||
| 0 | 1 | * | 1 | ||
| 1 | 1 | -1 | * |
a rozlosování 1, 3, 2, 4 (tzn. v prvním kole spolu hrají 1 se 3, 2 se 4). Možnými vítězi jsou hráči 3 a 4.
3-1-4 Systém menu
Tak jako loni i letos bychom rádi vždy alespoň jednu úlohu série věnovali nějakému praktickému problému. Tentokrát jsme se rozhodli potýrat vás souborem procedur a funkcí, které umožní snadnou realizaci menu ve vašich programech.
Menu je seznam položek, řazených vertikálně nebo horizontálně.
Aktuální položka je zvýrazněna a její změna se provádí pomocí
šipek nahoru, dolů (příp. doleva, doprava). Výběr položky
a opuštění menu se provede klávesou ENTER. Při stisku klávesy ESC
se obnoví případná nastavená aktuální položka a menu se opustí.
Vytvořte si datové struktury, které vám umožní uchovávat veškeré informace o jednotlivých menu, jež považujete za užitečné. Sestavte procedury a funkce, které vám umožní zobrazení příslušného menu, jeho smazání, obsluhu zvoleného menu (pohyb kurzoru v něm a zvýraznění zvolené položky). Případným dalším nápadům se meze nekladou. Vzhledem k tomu, že program bude vyžadovat komunikaci s obrazovkou a že tuto komunikaci chceme poněkud znormalizovat, můžete pro vstup a výstup používat pouze následující procedury a funkce:
GetKey:integer– čeká na stisk klávesy a vrátí některou z číselných konstantUP,DOWN,LEFT,RIGHT,ENTER,ESC. Jejich význam v uvedeném pořadí je: pohyb kurzoru v menu nahoru, dolů, doleva, doprava, výběr položky a opuštění menu, opuštění menu beze změn.CPrint(Co:String;BarvaTisku,BarvaPozadi:integer)– na aktuální pozici kurzoru vytiskne řetězecCo.ScreenWidth:integer– vrací šířku obrazovky ve znacích.ScreenHeight:integer– vrací výšku obrazovky ve znacích.GotoXY(x,y:integer)– jsou-li data platná (to jest současně platí 1 ≤x≤ScreenWidtha 1≤y≤ScreenHeight), nastaví kurzor na příslušnou pozici na obrazovce, levý horní roh je (1,1).ClrScr(Barva:integer)– vymaže obrazovku zadanou barvou.Store(xl,yh,xp,yd:integer):^integer– funkce uloží text ze zadané části obrazovky (obdélník s levým horním rohem(xl,yh)a pravým dolním rohem(xp,yd)) do paměti a vrátí ukazatel na její začátek; jsou ukládány jak znaky, tak jejich barva.Recall(xl,yh,xp,yd:integer;Uk:^integer)– vytiskne na dané místo na obrazovce text uložený funkcíStore;Ukje ukazatel na začátek paměti, kde je text uložen.