Cvičení z programování I
Ve školním roce 2006/2007 vedu cvičení z předmětu Programování I [PRG030]. Cvičení se koná každé pondělí od 15.40 v S10.
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ů
- vypracování zápočtového programu
Ve zkouškovém období určitě budu na katedře zkoušet každé úterý od 10:00, což je také ideální čas k zapisování zápočtů a předvádění programů. Pokud byste chtěli přijít jindy nebo na konsultaci, můžeme se domluvit mailem.
Zápočtový program
- 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 a archiv Matematické Olympiády kategorie P.
- Jazyk: nejlépe Pascal; pokud máte dobrý důvod použít něco jiného, ozvěte se, lze se domluvit.
- 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
- 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 polovic.
- Pokud není v zadání řečeno jinak, řešení úkolu by měl být odladěný program v Pascalu s textovým vstupem a výstupem. Nepoužívejte, prosím, unity graph a crt.
- Řešení, prosím, zasílejte mailem, a to buďto v těle zprávy nebo jako textovou přílohu.
- U některých úkolů je v hranatých závorkách zmíněna časová složitost, které (případně lepší) byste měli dosáhnout.
| Datum | ID | Body | Příklady | |||
|---|---|---|---|---|---|---|
| 2. 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ěžší. | |||
| 13k | 1 | 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. | ||||
| div3 | 1 | Popište, jak u čísla zapsaného v dvojkové soustavě určit, zda je dělitelné třemi. Zdůvodněte, proč váš postup funguje. | ||||
| 9. 10. | mnam | 1 | Hrajme hru Ňam s jednou hromádkou lentilek, ze které je možné v každém tahu odebrat 2 nebo 3 lentilky a prohraje ten, kdo už nemůže táhnout. Na cvičení jsme rozebrali, které jsou vyhrávající pozice. Navrhněte, jak hrát tak, abychom nejen vyhráli, ale také snědli co nejvíce lentilek. Soupeř se vám samozřejmě (když už ví, že stejně nevyhraje) snaží v mlsání bránit. | |||
| nam2 | 1 | Ňam se dvěma hromádkami, v každém tahu si lze vybrat hromádku a odebrat z ní
libovolný počet lentilek, prohraje opět ten, kdo nemůže táhnout. Vymyslete
vyhrávající strategii.
[+1 bod] ... s K hromádkami. | ||||
| 16. 10. | dokc | 1 | Přirozené číslo X nazveme dokonalým, jestliže součet všech jeho přirozených dělitelů menších než X dá přesně X. Napište program, který vypíše všechna dokonalá čísla menší než zadaná mez. | |||
| 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). | ||||
| 23. 10. | sums | 2 | Je dána posloupnost celých čísel. Napište program pro nalezení úseku s největším součtem a vypsání jeho součtu i polohy v posloupnosti. [O(N)] | |||
| spou | 2 | Jako vždycky program. Tentokrát pro nalezení nejdelšího společného úseku dvou
řetězců (posloupností znaků), tedy co nejdelšího řetězce, který se
vyskytuje v obou zadaných řetězcích a ne nutně na stejném místě. [O(N2)]
[+2 body] … v čase O(N). | ||||
| srot | 1 | Napište program pro cyklycké posunutí posloupnosti o daný počet prvků. [O(N)] | ||||
| 30. 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.). [O(log(pozice_nalezeneho_prvku))] | |||
| 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 v této množině čísel?", jednou za hru můžeme (ale nemusíme) obdržet lživou odpověď. Váš program by měl použít méně než log2n + f(n) dotazů, kde f(n) je nějaká funkce rostoucí asympotitcky pomaleji než log2n. | ||||
| 6. 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 a zachovat jeho původní časovou složitost O(n*log log n). | |||
| msrt | 2 | Naprogramujte mergesort (třídění sléváním). [O(n*log n)] | ||||
| 13. 11. | isub | 1 | 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). | |||
| ksub | 2 | Totéž, ale pro podposloupnost s nejvýše K poklesy. | ||||
| fibc | 2 | Naprogramujte výpočet n-tého Fibonacciho čísla Fn v čase O(log n). Výsledek počítejte
modulo 1000000000, aby se vešel do longintu.
Hint: použijte algoritmus ze cvičení pro rychlé umocňování matic a vztah ( x y ) × (
[+1 bod] Podobným způsobem počítejte n-tý člen obecné lineární rekurence řádu k (je dáno prvních k členů, každý další je lineární kombinací k předchozích). | ||||
| 20. 11. | ldiv | 2 | Naprogramujte dělení dlouhých čísel. (Buďto ve dvojkové soustavě nebo použitím triku ze cvičení, tedy vynásobením obou čísel vhodnou mocninou dvojky tak, aby první číslice dělitele byla alespoň polovina základu soustavy.) | |||
| 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. | ||||
| 27. 11. | eulr | 2 | Napište program pro výpočet Eulerova čísla na zadaný počet desetinných míst. Základ jsme dělali na cvičení, pokud jste nestihli výpočty sledovat, můžete si přečíst textík o odhadu chyb. | |||
| gray | 2 | Napište proceduru, která vypíše všechny N-prvkové posloupnosti nul a jedniček v takovém pořadí, aby se každé dvě sousední lišily jen na jedné pozici a stejně tak poslední posloupnost od první. | ||||
| 4. 12. | tlac | 2 | Důmyslnost architektů občas překvapuje i matematiky. V nově rekonstruované posluchárně jedné
nejmenované fakulty zřídili osvětlení tvořené N žárovkami a ovládané M tlačítky. Každému
tlačítku je pevně přiřazena nějaká množina žárovek a kdykoliv ho zmáčknete, stav těchto žárovek
se změní (ty, které nesvítily, se rozsvítí, a naopak ty původně rozsvícené zhasnou). Jedna
žárovka může být ovládána i více tlačítky.
Po chvíli experimentování jste se dopátrali přiřazení mezi tlačítky a žárovkami a nyní byste se rádi naučili, jak rozsvítit libovolnou kombinaci žárovek, případně dokázat, že některé kombinace rozsvítit nelze. [O(polynom v M a N)] | |||
| pnxt | 2 | Naprogramujte proceduru, která k zadané permutaci vypíše jejího lexikografického následníka. Využijte pro nerekurzivní vygenerování všech permutací N prvků. [O(délka výstupu)] | ||||
| pgry | 3 | Naprogramujte výpis všech permutací N prvků v takovém pořadí, aby se každé dvě sousední (bráno cyklicky) lišily právě jednou transpozicí (prohozením dvojice prvků). [O(délka výstupu)] | ||||
| brag | 2 | Napište program, který pro zadané N vygeneruje všechny dobře uzávorkované posloupnosti s N levými a N pravými závorkami. [O(délka výstupu)] | ||||
| 11. 12. | prsq | 3 | Najděte všechny čtverce 5×5, jejichž prvky jsou číslice 0-9 a každý řádek i sloupec dává pětimístný desítkový zápis prvočísla. Nejlépe tak, že napíšete program, který takové čtverce generuje :) | |||
| domi | 3 | 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 2×n. | ||||
| 18. 12. | 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). [O(plocha2)]
Jiné varianty: Minotaurus se snaží utéci Théseovi; Théseus chce co nejrychleji potkat Minotaura. | |||
| hobb | 2 | Na jedné šachovnici žil jest jeden kulhavý kůň. Toť figurka, která se v liché tahy pohybuje jako šachový jezdec, v sudé pak jako pěšec (o jedno pole vpřed). Napište program, který najde mezi dvěma zadanými body na šachovnici nejkratší cestu kulhavým koňem. [O(plocha)] | ||||
| 8. 1. | bala | 2 | Vybalancovaná poslopnost je taková, v niž je stejný počet kladných čísel jako záporných.
Napište funkci, která v zadané posloupnosti najde nejdelší vybalancovaný úsek. [O(n)]
Tento a následující příklady lze odevzdávat za plný počet bodů do konce zkouškového období. | |||
| prnk | 1 | Napište program, který pro zadanou permutaci řekne, kolikátá je v lexikografickém pořadí všech permutací. [O(n2), +1 bod za lepší složitost] | ||||
| hans | 2 | Naprogramujte doskládání Hanojských věží: je dána nějaká legální konfigurace věží (disky na až třech trnech, nikdy neleží větší na menším), vygenerujte co nejkratší posloupnost tahů, která přemístí všechny disky na jeden trn. |
Libovolný příklad můžete poslat vícekrát, vždy platí nejvyšší dosažené skóre.