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

Domácí úkoly

DatumIDBodyPříklady
7. 10. 9k1Dokažte, že máte-li 3k 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í.
12k2Dostali 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. base2Nalezně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í.
nim21Hra 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. pokl1Napište program, který v zadané posloupnosti přirozených čísel najde nejdelší úsek s maximálně jedním poklesem.
kmin1Napiš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í.
pow21Vymyslete, jak o zadaném čísle v konstantním čase rozhodnout, zda je to mocnina dvojky.
11. 11. bmi22Naprogramujte převod celého čísla do minus-dvojkové soustavy (čísla se zapisují číslicemi 0, 1 a i-tý řád má váhu (-2)i).
fff12Mě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.
gold2Slavná 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. mis22Na 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ý.]
even1Na 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ěť.
sqrt2Napiš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. minc2Napište funkci, která v zadané posloupnosti najde nejdelíš rostoucí vybranou podposloupnost. Za libovolné polynomiální řešení 2 body, za lepší než kvadratické +1.
mbai2Napiš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).
isum2Napište funkci, která v zadané posloupnosti najde interval se zadaným součtem, pokud existuje.
ndiv2Upravte Eratosthenovo síto tak, aby každému číslu spočetlo počet dělitelů. Zachovejte původní časovou složitost.
rmq2Vytvoř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. fact2Napiš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.
eulr3Naprogramujte výpočet Eulerova čísla na zadaný počet desetinných míst. Hint: e=1/0!+1/1!+1/2!+...
eggs2Ž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. divi2Naprogramujte dělení dlouhých čísel.
fibb1Naprogramujte výpočet n-tého Fibonacciho čísla Fn (F0=0, F1=1, Fn=Fn-1+Fn-2). Jelikož Fibonacciho čísla rostou velmi rychle, je nutné použít dlouhá čísla.
fibc2Naprogramujte výpočet n-tého Fibonacciho čísla Fn v O(log n). Výsledek počítejte modulo 1000000000, aby se vešel do longintu.
Hint: ( x y ) × (
01
11
) = ( 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. gray2Napiš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í.
brac1Dobř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.
brag2Napište program, jenž vygeneruje všechny DUP zadané délky.
perg2... který vygeneruje všechny permutace na N-prvkové množině.
pery3... tak, aby se dvě sousední lišily právě jednou transpozicí (prohozením dvou prvků).
6. 1. wlay2Bí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í.
wobb2Kulhavý 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.
auto2Na 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. alge2Jsou 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.
prsq3Napište program, který vygeneruje všechny čtverce 5x5 vyplněné číslicemi 1...9 tak, aby každý řádek i sloupec tvořil prvočíslo.
fass2Jsou dány nádoby objemů v1, v2, v3 (vi<=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.

Stránku spravuje Martin Mareš