Cvičení z Programování I

Ve školním roce 2003/2004 vedu cvičení z předmětu Programování I [NPRG030]. Cvičení se koná každé pondělí od 15.40 v posluchárně E1.

Podmínky k získání zápočtu jsou:

Vypracování domácích úkolů za alespoň 8 bodů. Domácí úkoly budou zadávány v průběhu semestru na cvičeních a rovněž se budou objevovat na těchto stránkách. Pokud úkol vyřešíte během semestru, platí počet bodů uvedený v tabulce, jinak se redukuje na polovinu.
Vypracování zápočtového programu v Pascalu
Požadavky:
- Téma: libovolné, jaké si vymyslíte, má-li odpovídající obtížnost. Nabízím poměrně rozsáhlý seznam témat (na skladě též zdrojový text v TeXu a pěkně vysázená verze v PDF), přiměřené pro zimní semestr jsou úlohy obtížnosti 3 a vyšší, ostatní berte jako návnadu pro vaši fantazii; vlastní nápady jsou ovšem vřele vítány. Jinými zajímavými zdroji inspirace mohou být: archiv programátorského korespondenčního semináře, archiv Matematické Olympiády kategorie P, stránka Roberta Špalka, stránka Dana Kráľe.
- Odevzdání specifikace programu do konce listopadu. Tím mám na mysli krátký popis toho, co všechno by program měl umět. Vyhnete se tak tomu, že by váš zápočtový program odevzdaný den před koncem zkouškového období byl odmítnut jako příliš triviální nebo příliš podobný programu někoho z vašich kolegů.
- Nedílnou součástí zápočtového programu je dokumentace, a to jak uživatelská (vysvětující, jak se program ovládá), tak programátorská (ta popisuje, jak program uvnitř funguje; postrádá smysl popisovat každou funkci či proměnnou, zaměřte se spíš na celkový návrh programu a použité algoritmy, pokud jste je sami nevymysleli, je moudré uvést odkazy na zdroje, z nichž jste čerpali).
- Specifikaci i dokumentaci odevzdávejte buďto v papírové podobě nebo chcete-li šetřit naše lesy, elektronicky v libovolném otevřeném formátu (tím se myslí formát, jehož struktura je všeobecně známa a na jehož prohlížení není potřeba žádný komerční software; speciálně tedy ne MS Word!), nejlépe jako čistý text, HTML, PostScript či PDF.
- Hotový program mi mužete předat buďto na cvičení nahraný na disketě či CD nebo jej poslat po Internetu, buďto e-mailem nebo (pokud je poněkud větších rozměrů, řekněme nad 0.5MB) uploadem do ftp://atrey.karlin.mff.cuni.cz/pub/priv/ (ale pak mi pošlete mail se jménem souboru). Pokud se zápočťák skládá z většího množství souborů, raději jej předtím zabalte ZIPem nebo TARem (RAR, prosím, ne).
- Zápočtový program musí mít přiměřeně ošetřené vstupy. Tím se myslí, že komunikuje-li s uživatelem, měl by počítat s tím, že uživatel je nešika a občas zadá špatný vstup a nenechat se tím zmást a bez zaváhání je odmítnout. Naopak, pokud programujete knihovnu funkcí, můžete předpokládat, že všechny vstupy jsou korektní.

Domácí úkoly

Datum	ID	Body	Příklady
6. 10.	9k	1	Dokažte, že máte-li 3^k kuliček, z nichž jedna je těžší než ostatní, je na její nalezení potřeba k vážení na rovnoramenných vahách (že to jde na k, jsme ukázali na cvičení, takže stačí ukázat, že to nelze na méně).
6. 10.	12k	2	Dostali jste 12 kuliček, z nichž jedna je lehčí nebo těžší než ostatní. Popište, jak trojím vážením na rovnoramenných vahách zjistit, která to je a jestli je lehčí nebo těžší. (*) [+1 bod] Dokažte, že s více než 12ti kuličkami už jsou potřeba 4 vážení a že vzdáte-li se požadavku na zjištění lehčí/těžší (tedy bude stačit jen zjistit, která kulička to je), pak to lze i pro 13, ale pro více už ne.
13. 10.	wts	2	Sestrojte sadu závaží, pomocí kterých je možno na rovnoramenných vahách odvážit všechny celočíselné hmotnosti od 0g do 999g: a) v případě, že je možno závaží pokládat jen na jednu misku vah, b) je-li možné pro závaží používat obě misky. Dokažte, že vaše sada je optimální, tedy že to s méně závažími není možné.
13. 10.	2hrom	3	Hrajme odebírání zápalek pro dva hráče a dvě hromádky. Hráči se na tazích pravidelně střídají a mohou vždy odebrat libovolný počet zápalek z libovolné jedné hromádky; kdo nemůže táhnout, prohrál. Vymyslete strategii na tuto hru a dokažte, že funguje.
20. 10.	ffib	3	Napište program, který spočte n-té Fibonacciho číslo v čase lepším než lineárním. Můžete předpokládat, že máte k dispozici celočíselný typ, do kterého se čísla této velikosti vejdou.
	fact	1	Napište program, jenž zadané přirozené číslo rozloží na součin mocnin prvočísel (tedy např. 24=2^3*3^1). Formát výstupu podle vlastního výběru.
	dokc	1	Číslo N nazveme dokonalým, pokud je rovno součtu všech svých dělitelů menších než N (například čísla 6 a 28). Napište program, který najde všechna dokonalá čísla mezi 1 a zadaným číslem. (*) [+1 bod] Napište program, který bude co nejefektivněji hledat další a další dokonalá čísla (nemusí najít všechna, ale měl by jich umět vygenerovat neomezeně [tedy omezeně jen rozsahem integeru] mnoho).
	miss	2	Na vstupu je dáno N a posloupnost N-1 přirozených čísel, ve které je každé číslo od 1 do N právě jednou až na jedno, které chybí. Napište program, který chybějící číslo najde. Ovšem pozor: N je tak velké, že se posloupnost nevejde do paměti.
	twox	2	Na vstupu je dáno N a posloupnost 2N+1 přirozených čísel (libovolně velkých), v níž je tentokrát každé číslo právě dvakrát, až na jedno, které tam je právě jednou. Napište program, který chybějící číslo najde. Ani tato posloupnost se nevejde do paměti.
	comb	2	Kombinační číslo C(n,k) je nadefinováno jako n!k!/(n-k)!. Ovšem počítáme-li jej podle této definice, může se snadno stát, že ačkoliv výsledkem je poměrně malé číslo, mezivýsledky jsou natolik velké, že se již do longintu nevejdou. Napište program, který pro zadané n,k spočte C(n,k) a funguje pokaždé, když se výsledek* vejde do longintu.
27. 10.	Cvičení se nekonalo (soustředění KSP).
3. 11.	incr	2	Je dána posloupnost přirozených čísel ukončená -1. Nalezněte nejdelší vybranou neklesající podposloupnost. () [+1 bod] zkuste to v čase O(nlog n).
	bala	2	Je dána posloupnost celých čísel ukončená nulou. Nalezněte v ní nejdelší vybalancovaný úsek (to znamená takový, v němž je stejně kladných jako záporných čísel). Za řešení v kvadratickém čase 1 bod, za O(n*log n) 2 body, za lineární řešení 3 body.
	eggs	2	Žijete v N-patrovém domě a chcete zjistit, jaké je nejnižší patro, ze kterého když hodíte vajíčko, tak se rozbije. Chcete to zjistit na co nejmenší počet pokusů, ovšem máte pouze dvě vajíčka. Napište program, který bude tento problém řešit: dostane zadáno N a pak vám bude radit, jaké pokusy máte provést (tj. ze kterých pater házet) a vy mu budete odpovídat, jak to dopadlo. (*) [+1 bod] Máte k dispozici k vajíček.
10. 11.	minx	1	Napište program, který pro zadanou setříděnou posloupnost čísel a číslo X v logaritmickém čase nalezne nejmenší prvek posloupnosti, který je větší nebo roven X.
	inbs	1	Napište program pro vyhledávání v nekonečně velkém setříděném poli reprezentovaném funkcí, která pro každé n umí vrátit n-tý prvek pole. (Lze to v čase logaritmickém vzhledem k poloze nalezeného prvku.)
	pow2	2	Naprogramujte funkci, která pro zadané kladné celé číslo X zjistí, je-li X mocninou dvojky, a stihne to v konstantním čase.
17. 11.	Cvičení se nekonalo (svátek)
25. 11.	matr	2	Je dána čtvercová matice n*n, která je v každém řádku i sloupci rostoucí, a číslo X. Napište funkci, která v čase O(n) zjistí, zda se X v matici vyskytuje.
25. 11.	anag	2	Napište program, který v zadaném slovníku najde všechny přesmyčky – tj. rozdělí slovník na co největší skupiny slov takové, že v každé skupině je každé slovo přesmyčkou všech ostatních.
1. 12.	gray	2	Napište proceduru, která pro zadané n vygeneruje všechny nula-jedničkové posloupnosti délky n v takovém pořadí, aby se dvě sousední lišily na právě jedné pozici.
1. 12.	lotr	2	Do fronty na lístky na nový díl Pána prstenů přišlo T trpaslíků a H hobitů. Trpaslíci jsou tvorové hašteřiví, takže nesmí stát dva těsně za sebou. Napište program, který vypíše všechny možnosti, jak se hobiti a trpaslíci mohou při splnění této podmínky seřadit.
8. 12.	pgry	3	Naprogramujte funkci, která vypíše všechny permutace čísel 1..N v takovém pořadí, aby se každé dvě sousední lišily pouze prohozením dvou prvků.
	nxtp	2	Napište funkci, jež pro zadanou permutaci najde v lineárním čase permutaci následující v lexikografickém uspořádání.
	parc	1	Závorkové posloupnosti (ZP) si nadefinujme takto: prázdná posloupnost je závorková, jsou-li posloupnosti P a Q závorkové, pak PQ (jejich spojení) a (P) (tedy uzávorkování libovolné z nich) jsou také ZP. žádné jiné ZP neexistují. Tedy např. posloupnosti `()` a `(())()` jsou závorkové, zatímco `(()))(` nikoliv. Napíšte co nejjednodušší program, který o zadané posloupnosti zjistí, zda je závorková, a dokažte o něm, že opravdu přijímá pouze ZP podle zmíněné definice. Program by si neměl celou posloupnost pamatovat.
	parg	3	Naprogramujte funkci, jež vypíše všechny ZP zadané délky a dokažte to o něm.
15. 12.	lspl	1	Jest dán jednosměrný spojový seznam integerů. Napište funkci, která tento seznam rozdělí na dva seznamy obsahující všechna sudá, resp. lichá čísla z původního seznamu v původním pořadí. Vyvarujte se kopírování prvků, vždy jen přepojujte prvky mezi seznamy.
	lrev	1	Opět jest dán jednosměrný spojový seznam. Tentokráte máte za úkol seznam obrátit, to jest vytvořit z něj jiný seznam (z těchže prvků, opět nic nekopírujte), v němž budou prvky v přesně opačném pořadí.
	lsrt	2	Pro změnu je dán jednosměrný spojový seznam integerů. Tentokrát je vaším úkolem naprogramovat funkci, která jej v čase O(n*log n) setřídí, tj. přepojí prvky v seznamu tak, aby byly uspořádány vzestupně. (Hint: Zkuste použít mergesort.)
	loop	2	Ještě jednou je dán jednosměrný spojový seznam, ovšem tentokrát muže být zacyklený, tj. poslední prvek bude za svého následníka místo nilu prohlašovat některý z předchozích prvků. Napište funkci, která o zadaném seznamu rozhodne, je-li zacyklený či normální. Funkce by ovšem měla pracovat v lineárním čase a konstantní paměti a neměla by seznam nijak modifikovat.
5. 1.	succ	2	Napište funkci pro nalezení následníka prvku v binárním vyhledávacím stromu (BVS), tj. nemenšího z prvků, které jsou větší než prvek, na který ukazuje zadaný pointer. Můžete předpokládat, že strom je vyvážený, všechny prvky jsou navzájem různé a každý prvek ukazuje na svého otce. Očekávaná složitost: O(log n). (*) [+1 bod] Vypište pomocí této funkce všechny prvky stromu v čase O(n). Tento a následující příklady lze odevzdávat za plný počet bodů do konce zkouškového období.
	balt	1	Naprogramujte konstrukci dokonale vyváženého BVS ze setříděné posloupnosti. (Dokonale vyváženým nazveme takový strom, ve kterém pro každý vrchol platí, že počet prvků jeho levého a pravého podstromu se liší maximálně o jedna.)
	deep	1	Napište funkci, která pro daný obecný zakořeněný strom (OZS; takové stromy například můžete ukládat pomocí kanonické reprezentace binárními stromy – viz přednáška) spočte jeho hloubku.
	ival	2	Napište proceduru, která vypíše všechny prvky daného BVS, které leží v daném uzavřeném intervalu, a to v čase O(hloubka stromu + velikost výstupu).
	mist	3	Maximální nezávislá množina v grafu je největší (co do počtu) množina vrcholů grafu takových, že mezi nimi nevede žádná hrana. Napište funkci, která spočte velikost maximální nezávislé množiny v zadaném OZS. Složitost: lineární.
	invs	3	Spočítejte inverze v zadané posloupnosti (o indexech i,j řekneme, že tvoří inverzi, pokud i<j a současně x_i > x_j. Složitost: n*log n.