Cvičení z Programování I

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

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 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

7. 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ě).
Řešení už jsme ukázali na cvičení.

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.

14. 10. Cvičení se nekonalo kvůlivá imatrikulaci.

21. 10. base 2 Nalezněte sadu co nejmenšího počtu závaží, pomocí kterých půjdou odvážit všechny celočíselné hmotnosti od 1g do 1000g: (a) v případě, že závaží lze klást pouze na jednu misku vah, (b) bez tohoto omezení.

nim2 1 Hra s odebíráním zápalek: 2 hromádky se známými počty zápalek, v každém tahu hráč odebere libovolný počet zápalek z jedné hromádky. Popište vyhrávající strategii pro jednoho z hráčů.
[+2 body] Totéž pro obecný počet hromádek.

28. 10. Sláva Ti, Václave, vévodo náš...

4. 11. pokl 1 Napište program, který v zadané posloupnosti přirozených čísel najde nejdelší úsek s maximálně jedním poklesem.

kmin 1 Napište program hledající v zadané posloupnosti n přirozených čísel k-té nejmenší číslo.
1 bod za řešení v čase n*k, 2 body za n*log k, 3 body za lineární řešení.

pow2 1 Vymyslete, jak o zadaném čísle v konstantním čase rozhodnout, zda je to mocnina dvojky.

11. 11. bmi2 2 Naprogramujte převod celého čísla do minus-dvojkové soustavy (čísla se zapisují číslicemi 0, 1 a i-tý řád má váhu (-2)ⁱ).

fff1 2 Mějme funkci f(x) přiřazující přirozeným číslům přirozená čísla. Uvažme posloupnost 1, f(1), f(f(1)), f(f(f(1))), ... a předpokládejme, že je periodická. Napište program, který nalezne délku periody, má-li k dispozici pouze konstantně velký prostor.

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 co nejlepší časovou složitost.

18. 11. mis2 2 Na vstupu je posloupnost obsahující čísla 1...N, každé právě jednou až na dvě, která chybí. Napište program, který v lineárním čase a konstantní paměti zjistí, která. [Pro jedno jsme dělali na cvičení, trik je podobný.]

even 1 Na vstupu je opět posloupnost přirozených čísel, ovšem v libovolném rozsahu. Každé číslo, které se v ní vyskytuje, se vyskytuje dvakrát, až na jedno, které je tam právě jednou. Které? Opět máte k dispozici lineární čas a konstantní paměť.

sqrt 2 Napište funkci pro výpočet celočíselné odmocniny – to je největší přirozené číslo, jehož druhá mocnina je <= zadanému číslu.

25. 11. minc 2 Napište funkci, která v zadané posloupnosti najde nejdelíš rostoucí vybranou podposloupnost. Za libovolné polynomiální řešení 2 body, za lepší než kvadratické +1.

mbai 2 Napište funkci, která v zadané posloupnosti najde nejdelší vyvážený interval (to je taková souvislá podposloupnost, ve které je stejně kladných jako záporných čísel).

isum 2 Napište funkci, která v zadané posloupnosti najde interval se zadaným součtem, pokud existuje.

ndiv 2 Upravte Eratosthenovo síto tak, aby každému číslu spočetlo počet dělitelů. Zachovejte původní časovou složitost.

rmq 2 Vytvořte program, který v čase O(n*log n) předzpracuje zadanou posloupnost celých čísel a potom bude schopen v konstantním čase schopen odpovídat na dotazy typu "jaké je minimum intervalu <x,y> v této posloupnosti?".
+2 body za řešení s předzpracováním v čase O(n); -0.5 bodu za dotaz v čase O(log n).

2. 12. fact 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.

eulr 3 Naprogramujte výpočet Eulerova čísla na zadaný počet desetinných míst. Hint: e=1/0!+1/1!+1/2!+...

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.

9. 12. divi 2 Naprogramujte dělení dlouhých čísel.

fibb 1 Naprogramujte výpočet n-tého Fibonacciho čísla F_n (F₀=0, F₁=1, F_n=F_n-1+F_n-2). Jelikož Fibonacciho čísla rostou velmi rychle, je nutné použít dlouhá čísla.

fibc

Naprogramujte výpočet n-tého Fibonacciho čísla F_n v O(log n). Výsledek počítejte modulo 1000000000, aby se vešel do longintu.
Hint: ( x y ) × (

0	1
1	1

) = ( y 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).

16. 12. gray 2 Napište program, který vygeneruje všechny posloupnosti N nul a jedniček v takovém pořadí, aby se dvě sousední lišily na právě jedné pozici.
[+1 bod] za nerekurzivní řešení.

brac

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.

perg 2 ... který vygeneruje všechny permutace na N-prvkové množině.

pery 3 ... tak, aby se dvě sousední lišily právě jednou transpozicí (prohozením dvou prvků).

6. 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í.

wobb 2 Kulhavý kůň je šachová figurka, která se v lichých tazích pohybuje jako jezdec, zatímco v sudých jako pěšec. Nalezněte nejkratší cestu kulhavým koněm mezi dvěma zadanými políčky na šachovnici s překážkami.

auto 2 Na cestě jedním nejmenovaným americkým městem (čtvercová síť ulic, některé přerušeny zátarasem) se vám porouchalo auto, takže teď je schopno na křižovatkách pouze jezdit rovně nebo zatáčet doleva. Nalezněte nejkratší cestu ze zadaného políčka do servisu.

13. 1. alge 2 Jsou dána čísla N a K. Nalezněte rozmístění znamének +, - a * mezi čísla 1, 2, ..., N takové, aby výsledek byl právě K.

prsq 3 Napište program, který vygeneruje všechny čtverce 5x5 vyplněné číslicemi 1...9 tak, aby každý řádek i sloupec tvořil prvočíslo.

fass 2 Jsou dány nádoby objemů v₁, v₂, v₃ (v_i<=100) a objemy x, y (všechno celá čísla v litrech). Na počátku je v největší nádobě x litrů vody a chceme postupným přeléváním odměřit y litrů vody v některé z nádob. Povolené operace jsou přelití vody mezi nádobami ukončené tím, že zdrojovou nádobu vyprázdníme nebo cílovou naplníme po okraj, a vylití veškeré vody z nádoby na trávníček před domem.

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