Cvičení z programování, PRG030


Cvičení se koná v úterý v 9:00 v M4 na Karlově 3.

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

Informace o zápočtovém programu

Domácí úkoly (07. 03. 2006)

Datum
cvičení
IDBodyPopis
4. říjnaZac Začátek cvičení. Úkoly začnou být vypisovány někdy na začátku listopadu.
1. listopaduPrvc1Napište program, který rozloží zadané číslo na prvočinitele (pro 84 by měl vypsat "84=2^2*3*7").
Fact1Napište program, který pro zadané N spočte, kolik nul je na konci čísla N!. Pozor na to, že N! může mít stovky cifer a nevejde se tedy do žádného celočíselného typu! Můžete předpokládat, že N se vejde do typu longint.
Fdig2Napište program, který pro zadané N zjistí, jaká je poslední nenulová cifra čísla N!. Pokud to nebude zřejmé, měli byste dokázat, že Váš program funguje správně. Pozor na to, že N! může mít stovky cifer a nevejde se tedy do žádného celočíselného typu! Můžete opět předpokládat, že N se vejde do longintu.
3Mat1Na třech hromádkách se nachází (a,b,c) sirek. Hrají dva hráči, pravidelně se střídají. Hráč na tahu si vybere hromádku a odebere z ní libovolný nenulový počet sirek. Prohrává hráč, který už nemůže táhnout [(0,0,0) sirek]. Vymyslete strategii pro začínajícího hráče, aby vyhrál, kdykoliv je to možné, a dokažte to o ní.
KMin1-4Napište program hledající v zadané posloupnosti N přirozených čísel K-té nejmenší číslo.
Řešení v čase O(N*K): 1 bod.
Řešení v čase O(N*log K): 2 body.
Řešení v čase O(N): 4 body.
8. listopaduSSum1-4Na vstupu dostanete posloupnost N čísel a ještě číslo K. Máte zjistit, zda se v zadané posloupnosti vyskytuje souvislá podposloupnost (interval), jejíž součet by byl roven zadanému číslu K.
Kvadratické řešení: 1 bod.
Řešení v čase O(N * log N): 2 body.
Lineární řešení: 4 body.
Usek1-5Napište program, který dostane na vstupu posloupnost N čísel a vypíše délku nejdelší souvislé podposloupnosti, která má nezáporný součet svých členů.
Kvadratické řešení: 1 bod.
Řešení v čase O(N * log N): 3 body.
Lineární řešení: 5 bodů.
15. listopaduBVyh2První písemka, jejíž cílem byla implementace binárního vyhledávání v Pascalu.
Rost1-2Napište program, který dostane na vstupu posloupnost N čísel a vypíše nejdelší rostoucí podposloupnosti (nemusí být souvislá). Použijte k tomu jeden z algoritmů popsaných na cvičení. Za kvadratický dostanete jeden bod, za O(N log N) dostanete body dva.
23. listopaduPetr1Na zahradě je N záhonů, na jeden celý záhon se dá vysadit buď mrkev, nebo petržel. Nicméně petržel se nesmí vyskytovat na dvou sousedních záhonech. Napište program, který pro zadané N vypíše všechna možná osázení N záhonů.
Zvse1Posloupnost, která se skládá ze znaků '(' a ')' nazveme dobře uzávorkovanou, pokud je
  • prázdná
  • '(X)', kde X je dobře uzávorkovaná
  • 'XY', kde X a Y jsou dobře uzávorkované posloupnosti
Napište program, který pro zadané N vypíše všechny různé dobře uzávorkované posloupností, které se skládají z N levých a N pravých závorek.
Zpoc1Posloupnost, která se skládá ze znaků '(' a ')' nazveme dobře uzávorkovanou, pokud je
  • prázdná
  • '(X)', kde X je dobře uzávorkovaná
  • 'XY', kde X a Y jsou dobře uzávorkované posloupnosti
Napište program, který pro zadané N spočte, kolik existuje různých dobře uzávorkovaných posloupností, které se skládají z N levých a N pravých závorek.Váš program musí fungovat rychleji než exponenciálně (čili nemáte dost času na to si všechny tyto posloupnosti vytvořit.
Pods1Na vstupu dostanete N celých čísel s1,s2,...,sN a celé číslo K. Vaším úkolem je vypsat VŠECHNY podposloupnosti si1,si2,...,sik takové, že součet jejích prvků je právě K.
Podp3Na vstupu dostanete N tentokrát nezáporných čísel s1,s2,...,sN a nezáporné číslo K. Vaším úkolem je v čase O(N*K) spočítat, KOLIK existuje podposloupností si1,si2,...,sik takových, že součet jejich prvků je právě K. Tyto podposloupnosti nevypisujte (to byste v čase O(N*K) nestihli), vypište jen jejich počet.
Příklad: Pro N=3, posloupnost 1, 1, 1 a K=2 je správný výsledek 3 (jsou to podposloupnosti 11 12; 11 13; 12 13).
30. listopaduPsmk2+2Hodinová písemka na vypsání všech permutací a všech posloupností, které v součtu dají dané číslo.
13. prosinceZbyt1-3Na vstupu dostanete k různých prvočísel p1,...,pk a dále čísla n1<p1,n2<p2,...,nk<pk. Máte vypočítat takové číslo N, že N je menší než součin všech zadaných prvočísel a zbytek po dělení čísla N prvočíslem pi je ni pro každé i.
Jinak řešeno máte převést číslo zadané pomocí zbytkových tříd do desítkového zápisu. Body dostanete podle časové složitosti.
Blud2Na vstupu dostanete bludiště velikosti N x M. Každé políčko bludiště je buď volné, zeď, start, nebo cíl. Start a cíl je vždy právě jeden. Vaším úkolem je najít a vypsat nejkratší cestu ze startu do cíle. Hýbat se můžete v jednom kroku dolů, nahoru, doleva nebo doprava.
Časová složitost celého algoritmu musí být O(N*M).
20. prosince  Následující úlohy jsou testové obtížnosti, zkuste si je alespoň rozmyslet.
TNas2V souboru je uloženo nespecifikované množství dlouhých čísel (max. 50 cifer na číslo). Každé je uloženo na jednom řádku. Úkolem je vynásobit je všechny. Je zaručeno, že výsledné číslo nebude mít více než 1000 cifer.
TDes2Veškerá data se načítají ze souboru. Máme šachovnici MxN a figurku z kouzelného šachu. Ta figurka chodí v lichém tahu jako střelec a v sudém jako věž. Na šachovnici jsou nějaká zakázaná políčka, je udáno startovní a cílové políčko šachovnice a úkol je najít nejkratší cestu (pokud není, tak vypsat hlášku, že to nejde) a vypsat ji.
TKal2Pracovní cyklus muže je 2x ranní, 2x odpolední, 2x noční, 2x volno. Pracovní cyklus ženy je 5x ranní, 2x volno. Udělejte kalendář pro zloděje, milence, milenku a přítele (obou).
TMor2Napište program pro převod z a do morseovky (program musí umět oba převody). Z klávesnice načtěte, zda se bude převádět z nebo do morseovky, ale vlastní vstup čtěte ze souboru a výsledek vypisujte do jiného souboru. Pokud neznáte morseovku, můžete si vymyslet vlastní variantu.
Tooo2Na vstupu je textový soubor z písmenek anglicke abecedy a n≤13. Máte tento soubor přepsat do jiného tak, že zachová úpravu (mezery, entery) a pokud nějaké slovo obsahuje sudý výskyt znaku 'o' (počítáno od začátku souboru) a některé z následujících n slov neobsahuje 'a', tak se jeho znaky mají nahradit hvezdickami '*'.
TLat2Vypsat do souboru všechny možné latinské čtverce řádu N≤10. Latinský čtverec je matice typu N x N, v níž v každém sloupci, řádku a na obou úhlopříčkách jsou různa čísla od 1 do N.
TCif2Je zadaná posloupnost až 8 cifer a číslo X. Úkolem je vypsat (do souboru) všechny možnosti jak vložit mezi cifry znaménka (+-*/) nebo NIC, tak aby se vzniklý výraz rovnal X. Na prioritu +-/* se nehraje, počítá se odleva (např. pro vstup 5 0 5 0, X=100, je řešení například 50+50).
TSif2Monte Christova šifra. Máte mřížku (matici) 2N x 2N, ve které je vyříznuto N otvorů. Do nich po řádcích vpisujete písmena textu, který chcete zašifrovat. Když zaplníte všechny otvory, matici pootočíte o devadesát stupňů a jedete znova (tudíž je jasné, že matice musí být volena tak, aby se otvory nepřekrývaly po pootočení, že :). Takto pokračujete, dokud neotočíte matici potřetí. Pokud je text delší a nevešel se celý, jedete další blok textu stejným způsobem. Napište šifrátor a dešifrátor daného textu. (Při psaní uvažujte optimalizaci pro dlouhé úseky textu, například Babičku:)
10. lednaLabT2Test v labu, ulohy na fox.matfyz.cz/test.

Stav (23. 03. 2006)

JménoÚkolyZápočťákZápočet
OdevzdanéBodů
celkem
SpecifikaceHodnocení
Nemanja DjošičPrvc(1), Fact(1), 3Mat(2), Petr(1), Zbyt(1:O[součin pi]), Zvse(1)7Dlouhá číslaNeodevzdánoNe
Braňo MalešZvse(1), Prvc(1), Fact(1), Petr(1), Fdig(2)6ŽádnáNeodevzdánoNe
Lukáš MalýSSum(1), Fact(1), Prvc(1), Petr(1), KMin(1)5KartotékaNeodevzdánoNe
Maryna MarchenkoVlastní_domácí_úkoly(1), Psmk(2), Fact(1), Avg(1), KMin(2), TCif(2), Zvse(1)10KalkulajdaOdevzdáno, OKAno
Jakub MarekPrvc(1), Rost(2), SSum(1), Psmk(2), Fact(1), Fdig(2), Blud(2)11AkordovátkoOdevzdáno, OKAno
Michal MarkoPrvc(1), Fdig(2), Petr(1), TKal(2), Zvse(1), Fact(1), Blud(2)10HangmanOdevzdáno, OKAno
Petr MašekPrvc(1), KMin(1)2LifeNeodevzdánoNe
Karel NěmejcKMin(2), Prvc(1), Petr(1), Zvse(1), Fact(1)6KalendářOdevzdáno, OKNe
Ondřej OdcházelBVyh(1), Prvc(1), Psmk(1), KMin(1), Petr(1), Podp(3), SSum(1), Fact(1)10Rozpoznávání jazykaOdevzdáno, OKAno
Michal PapežPsmk(4), KMin(4), Blud(2), Fact(1), Fdig(2)13KompresítkoOdevzdáno, OKAno
Jan PavlíkBVyh(2), Prvc(1), Fact(1), Rost(1), Psmk(4), Petr(1), Zvse(1), LabT(2)13Fish filletsOdevzdáno, OKAno
Šimon RajčanFact(1), KMin(1), Blud(1), Petr(1), Prvc(1), TKal(2), Usek(1), Zvse(1), SSum(1)10MefistoOdevzdáno, OkAno
Václav RemešPrvc(1), BVyh(1), Psmk(1), KMin(1), Fact(1), Fdig(2), Petr(1), Zvse(1), Rost(2), LabT(2)13OrganizátorOdevzdáno, OKAno
Jan SequensBVyh(1), Prvc(1), TMor(2), TKal(2), Rost(1), Fact(1), Blud(2)10IqOdevzdáno, OKAno
Tomáš SkalickýPrvc(1), Fact(1), KMin(2), Fdig(2), Petr(1), Zvse(1), TLat(2), TKal(2)12MathematikoOdevzdáno, OKAno
Lukáš SlivkaPrvc(1), Fact(1), Zvse(1), Petr(1), LabT(2), KMin(1), Fdig(2), Pods(1)10PočítátkoOdevzdáno, OKAno
Petr SobotkaPrvc(1), Fact(1), Psmk(1), Petr(1), Zvse(1), Rost(2), 3Mat(3), Pods(1), TCif(2), Blud(2)15PiškvorkyOdevzdáno, OKAno
Tomáš StarýPrvc(1), Fact(1), Fdig(2), KMin(1), TNas(2), Petr(1), TMor(2), TKal(2)12UpomínátkoOdevzdáno, OKAno
Radomir TarabičPrvc(1), Fact(1), 3Mat(3), KMin(1), SSum(1), Usek(1), TCif(2), Zbyt(1)11MaticeOdevzdáno, OKAno

Pokud byste něco potřebovali, napište mi na fox {zavináč} ucw {tečka} cz.


Zpět