Cvičení z Programování I

Ve školním roce 2005/2006 vedu cvičení z předmětu Programování I [PRG030]. Cvičení se koná každý čtvrtek od 15.40 v S1.

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

Úspěšné absolvování zápočtového testu (organizuje přednášející).
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 do 28 dnů od zadání, platí počet bodů uvedený v tabulce, později 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	2	Dokažte, že máte-li n-1 mincí stejné hmotnosti a jednu těžší, je k nalezení té těžší potřeba alespoň ⌈log₃n⌉ vážení na rovnoramenných vahách. Že tolik vážení stačí, to jsme ukázali na cvičení; zbývá tedy dokázat, že na méně vážení to už nejde.
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.	nim1	1	Popište strategii pro hru s odebíráním zápalek s jednou hromádkou, ze které lze v každém tahu odebrat počet zápalek, který je mocninou dvojky. (Hrají dva hráči, pravidelně se střídají, kdo nemůže táhnout, prohrává.)
	nim2	2	Popište strategii pro odebírání zápalek se dvěma hromádkami, přičemž hráč na tahu si vždy vybere jednu hromádku a z té odebere libovolný nenulový počet zápalek. [+1 bod] Totéž pro N hromádek.
	bcvt	1	Napište program, který převádí čísla ze soustavy o základu A do soustavy o základu B. Na začátku si přečte A a B, pak čte jednotlivé číslice čísla a výstup vypisuje opět po číslicích. Můžete předpokládat, že převáděné číslo se vejde do integeru. [+1 bod] ... základ soustavy může být i záporné číslo.
	card	1	Míchání karet: navrhněte algoritmus pro generátor náhodných permutací na zadaném počtu prvků. Všechny vygenerované permutace by měly mít stejnou pravděpodobnost; můžete předpokládat, že máte k dispozici funkci Random(X), která vygeneruje náhodné číslo od 0 do X-1 s rovnoměrným rozložením pravděpodobností.
20. 10.	Cvičení se nekoná, váš cvičící je na soustředění KSP.
27. 10.	ibsr	1	Napište program pro vyhledávání půlením intervalů v nekonečně velkém ostře rostoucím poli. Na hodnoty pole se přitom bude ptát uživatele ("jaký je pátý prvek?" apod.).
	sqrt	2	Naprogramujte celočíselné odmocňování, tj. program, který pro zadané číslo N vrátí dolní celou část druhé odmocniny z N. Hint: půlení intervalu. Hint 2: nepoužívejte typ real.
	lies	3	Hrajme hru "mysli si číslo" s ne úplně čestným protihráčem. Protihráč si vymyslí nějaké číslo X od 1 do N a naším úkolem je uhodnout ho. Můžeme klást dotazy typu "je X menší než A?", jednou za hru můžeme (ale nemusíme) obdržet lživou odpověď. Váš program by měl použít méně než 2*log₂n dotazů.
3. 11.	divs	2	Napište program, který pro všechna čísla od 1 do N spočte, kolik mají dělitelů. Zkuste upravit Eratosthenovo síto. [+1 bod] ... a zachovat původní časovou složitost síta O(n*log log n).
	gold	2	Slavná Goldbachova hypotéza říká, že každé sudé číslo větší než 2 je součtem dvou prvočísel. Napište program, který ji ověřuje, přesněji nalezne pro zadané číslo rozklad na součet dvou prvočísel, existuje-li. Snažte se o časovou složitost O(x*log x) nebo lepší (kde x je zadané číslo).
	fact	2	Naprogramujte rozklad na součin prvočísel. Násobné prvočinitele vypisujte jako mocniny: `80=2^4*5`.
10. 11.	mult	3	Pro labužníky: Napište proceduru pro násobení dvou N-ciferných čísel, která bude pracovat v rychlejším než kvadratickém čase. Hint: Násobte čísla rekurzivně po blocích velikosti N/2 a využijte toho, že (A+B)*(C+D)=AC+AD+BC+BD.
10. 11.	mpow	2	Napište proceduru pro umocňování čtvercových matic, která bude efektivnější než prosté zopakování násobení. Hint: Rozmyslete si nejdříve, jak počítat A⁶⁴. 1 bod za samotné násobení matic.
17. 11.	Cvičení se opět nekoná, jeť státní svátek. Také se narodil A. F. Möbius, byl zprovozněn Suezský průplav a na Měsíci přistál první Lunochod.
24. 11.	facz	2	Napište funkci, která spočte, na kolik nul končí desítkový zápis čísla N!. [+1 bod] spočtěte navíc poslední nenulovou číslici.
	ldiv	2	Naprogramujte dělení dlouhých čísel.
	eulr	2	Naprogramujte výpočet Eulerova čísla na zadaný počet desetinných míst. Hint: e=Σ_n1/n!.
1. 12.	absu	1	Napište proceduru, která vypíše všechny posloupnosti a-ček a b-ček obsahující právě A a-ček a B b-ček. Rekurzivní řešení jsme vymysleli na cvičení, zde naprogramujte nerekurzivní založené na nalezení lexikografického následníka.
	gray	2	Napište program, jenž vypíše všechny poslupnosti nul a jedniček délky N v takovém pořadí, aby se každé dvě sousední (i poslední a první) posloupnosti lišily na právě jedné pozici.
	brac	1	Dobře uzávorkovaná posloupnost (DUP) je definována takto: prázdná posloupnost je DUP jsou-li X a Y DUP, pak také XY a (X) jsou DUP. Napište program, který o zadané posloupnosti rozhodne, zda je to DUP.
	brag	2	Napište program, jenž vygeneruje všechny DUP zadané délky.
8. 12.	pgry	2	Naprogramujte proceduru, která vypíše všechny permutace n-prvkové množiny v takovém pořadí, aby se dvě sousední lišily jen transpozicí (tj. prohozením dvou prvků). [+1 bod] ... pokud se bude takto lišit i první a poslední permutace.
	pnxt	2	Opět vypisování permutací, tentokrát v libovolném pořadí, ale bez použití rekurze.
	domi	2	Mějme šachovnici o m řádcích a n sloupcích, na níž jsou některé políčka zakázaná, a neomezenou zásobu kostek 1x2. Váš program nechť vypíše všechny možnosti, jak šachovnici pokrýt kostkami bez děr a překryvů. 1 bod za řešení pro obdélník 2xn.
15. 12.	eval	2	Napište program pro vyhodnocování výrazů se závorkami a prioritami operátorů v lineárním čase. Chybně zapsané výrazy by program měl odmítnout. [+1 bod] ... a s unárními operátory.
15. 12.	sums	2	Naprogramujte proceduru, která vypíše všechny možnosti, jak zadané číslo rozložit na součet kladných celých čísel. Za různé se nepovažují rozklady lišící se pouze pořadím sčítanců.
22. 12.	pow2	2	Vymyslete, jak v konstantním čase o zadaném kladném čísle rozhodnout, zda je mocninou dvojky.
22. 12.	xmas	2	Santa Clausovi se při doručování dárků porouchalo sobí spřežení, takže dokáže jezdit jenom rovně a zatáčet doprava. Abyste situaci zachránili, napište Santovi program, který dostane mapu města (amerického, takže je to čtvercová síť s překážkami) a souřadnice dvou bodů a odpoví nejkratší trasou pro porouchané soby mezi těmito dvěma body.
5. 1.	wlay	2	Bílá paní Perchta se už k stáru trochu bojí procházet zdí. Naprogramujte pro ni algoritmus, jenž najde mezi dvěma políčky na mapě hrady (čtverečková síť se zdmi) cestu, která projde zdí co nejméněkrát, a z takových cest tu nejkratší. Tento a následující příklady lze odevzdávat za plný počet bodů do konce zkouškového období.
	alge	2	Jsou dána čísla N a K. Rozhodněte, jak čísla 1...N opatřit znaménky +/- tak, aby jejich součet byl právě K, případně odpovězte, že to není možné.
	thes	3	V jednom labyrintu žili-byli Théseus hrdina a Minotaurus obluda. Cílem Théseovým je uniknout z labyrintu (čtverečkové bludiště), cílem Minotaurovým je Théseus. V každém tahu udělá Théseus jeden krok dle svého vlastního výběru a Minotaurus dva kroky směrem k Théseovi: to znamená, že může-li se posunout v x-ové souřadnici tak, aby se přiblížil k Théseovi, učiní tak; nemůže-li, zkusí totéž v y-ové; pokud nelze ani to, stojí na místě. Napište program, který po zadání plánu bludiště a počátečních poloh Thésea a Minotaura poradí Théseovi trasu, po které může uniknout (lze-li to).
12. 1.	isub	2	Napište program, který v zadané posloupnosti nalezne v polynomiálním čase nejdelší neklesající vybranou podposloupnost. [+1 bod] ... v čase O(n*log n).
	elec	2	V jakýchsi volbách hlasovalo N voličů, každý odevzdal jeden hlas pro jednoho z kandidátů očíslovaných od 1 do 10⁹. Vyhraje ten kandidát, pro nějž hlasovala více než polovina voličů. Napište program, který co nejefektivněji tohoto kandidáta najde.
	sumi	2	Je dána posloupnost. Nalezněte v lineárním čase souvislý úsek posloupnosti, jehož součet je největší. Dokažte, že vaše řešení funguje.

Libovolný příklad můžete poslat vícekrát, vždy platí nejvyšší dosažené skóre.