První série sedmé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

7-1-1 Vybalancovaný úsek čísel

Je dána konečná posloupnost celých čísel. Řekneme, že souvislý úsek této posloupnosti je vybalancovaný, jestliže obsahuje stejný počet kladných a záporných čísel. Napište program, který v zadané posloupnosti celých čísel vyhledá nejdelší vybalancovaný úsek a vypíše jeho délku (tzn. kolika čísly je tento úsek tvořen). Například pro posloupnost čísel 4, 6, 8, -3, -5, 7, 0, 8, -6, 9, 9, 1, 0, -4 bude výsledkem výpočtu číslo 7, neboť nejdelší vybalancovaný úsek posloupnosti má sedm členů (je to úsek 8, -3, -5, 7, 0, 8, -6 nebo také -3, -5, 7, 0, 8, -6, 9).

7-1-2 Vyhodnocení výrazu

Napište program na vyhodnocení jednoduchého aritmetického výrazu. Výraz je tvořen celočíselnými konstantami, běžnými binárními aritmetickými operátory +, -, *, / (znak / představuje celočíselné dělení) a kulatými závorkami s libovolnou možností vnoření. Výraz je vytvořen podle obvyklých pravidel používaných v matematice a v programovacích jazycích. Vyhodnocuje se rovněž obvyklým způsobem, tj. nejprve podle závorek, pak podle priorit operátorů (operátory násobení a dělení mají vyšší prioritu, operátory sčítání a odčítání mají prioritu nižší) a nakonec operátory téže priority zleva doprava. Můžete předpokládat, že výraz zadaný na vstupu je syntakticky správný.

Příklad správně zapsaných výrazů a jejich hodnot:

100-(5+7*3) = 74
(20-10-18)+0 = -8
2*(((1+4))-2) = 6

7-1-3 Hammingova čísla

Kladné celé číslo nazýváme Hammingovým číslem, pokud ho můžeme zapsat ve tvaru 2a ·3b ·5c pro nějaká nazáporná celá čísla a, b, c. Uveďme pro ilustraci prvních patnáct Hammingových čísel: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24. Napište program, který pro dané n co nejrychlejším způsobem vyhledá a vypíše prvních n Hammingových čísel. Hodnotí se nejen správnost programu, ale i rychlost výpočtu.

7-1-4 Výběr souborů v DOSu

Pokud pracujete na PC pod operačním systémem MS-DOS, víte z vlastní zkušenosti, jak vypadají jména souborů a jaké lze použít masky pro vyhledávání souborů například v příkazu DIR. Pro ostatní si nyní řekneme alespoň to nejdůležitější: Jméno souboru je tvořeno jedním až osmi znaky (pro jednoduchost: písmeny nebo číslicemi). Bezprostředně po něm následuje tečkou oddělená přípona, která je tvořena nejvýše třemi znaky a může také zcela chybět. Soubor se tedy může jmenovat například DOPIS.TXT nebo 12091994.DAT nebo třeba DATA1.1. Maska pro vyhledávání souborů je tvořena podle stejných pravidel, může ale navíc obsahovat zvláštní znaky ? a *. Otazník nahrazuje jeden libovolný znak, hvězdička představuje libovolný řetězec znaků jakékoliv délky (třeba i prázdný).

Příklad správně utvořených masek:

Úloha: Je dána jedna maska pro vyhledávání souborů a seznam jmen souborů, mezi nimiž se má vyhledávat. Napište program, který na základě těchto vstupních údajů vybere všechna jména souborů vyhovující zadané masce a vypíše je.