PRM044 - cvičení 1. ročník matematika
skupina 55 ZS 2009/10 - úterý 17:20 K11

  • důležité : zaregistrujte se v systému Codex
    1. cvičení 6.října
    2. cvičení 13.října
    3. cvičení 20.října
    4. cvičení 27.října
    5. cvičení 2.listopadu
    6. cvičení 9.listopadu
    7. cvičení 16.listopadu
    8. cvičení 23.listopadu
    9. cvičení 30.listopadu
    10. cvičení 7.prosince
    11. cvičení 14.prosince
    12. cvičení 21.prosince
    13. cvičení 4.ledna
    14. cvičení 11.ledna

    Obsah cvičení

    1. cvičení 6.října
      • Kdo jsme a odkud jsme přišli, co zde očekáváme
      • Hledání největšího prvku z N prvků, včetně důkazu, že nejde rychleji
      • Hledání druhého největšího prvku z 8 prvků
        obecně z N prvků - vzoreček
        můžete zkusit dokázat, že nejde rychleji (je to těžší)
      • Dva kameny
        Dva hráči hrají následující deskovou hru. Hracím plánem je jedna řada tvořená 1000 políčky, pole jsou očíslována zleva doprava přirozenými čísly od 1 do 1000. Na začátku hry na náhodně zvolených dvou různých polích leží hrací kameny. Výchozí situaci hry lze tedy popsat dvojicí různých celých čísel od 1 do 1000. Oba hráči se ve hře pravidelně střídají. Hráč, který je na tahu, zvolí jeden z kamenů a přemístí ho o libovolný počet polí směrem doleva. Musí přitom kámen posunout alespoň o jedno políčko a zároveň svým tahem nesmí přeskočit jiný hrací kámen ani nesmí umístit přesouvaný kámen na již obsazené políčko. (Tah tedy nelze provést s kamenem stojícím na políčku číslo 1 ani s kamenem stojícím na políčku i, je-li políčko číslo i-1 právě obsazené.) Hra končí ve chvíli, kdy už nelze provést žádný tah, tzn. až se dostanou oba hrací kameny na políčka s čísly 1 a 2. Zvítězil ten z hráčů, který svým tahem dosáhl této koncové situace. Určete, jaké pozice jsou vyhrané a jaké prohrané. Úlohu jsme vyřešili.
      • Najděte pro zadané startovní pole cestu věže, která projde přes každé pole právě jednou resp. takovou, která je "uzavřená" (skončí na sousedním políčku stratovního pole) pro šachovnici 8 x 8
      • lámání čokolády
      • Rozmyslet:
        1. Čtyři kameny
          Stejná úloha jako byla úloha se dvěmi kameny, ale se čtyřmi hracími kameny. Výchozí situace hry je tedy popsána čtveřicí různých celých čísel od 1 do 1000 (čísla políček, na nichž leží kameny). Hra končí ve chvíli, kdy se hrací kameny dostanou na pole s čísly 1, 2, 3 a 4. Úkolem je opět určit, pro které výchozí situace hry si může zajistit výhru začínající hráč, a nalézt vítěznou strategii hry.
        2. Obdobně tři kameny
        3. Najděte pro zadané startovní pole cestu věže, která projde přes každé pole právě jednou resp. takovou, která je "uzavřená" (skončí na sousedním políčku stratovního pole).
          • na šachovnici bez rohového pole a1
          • na šachovnici bez dvou protilelehlých rohových polí (např. a1 a h8)
        4. Máme N podezřelých koulí, mezi nimi je nejvýše jedna špatná (tj. lehčí nebo těžší). Pomocí rovnoramenných vah máme na co nejmenší počet vážení zjistit která ze 2*N+1 možností nastala (buď jsou všechny koule správné nebo je jedna z nich špatná a musíme zjistit nejen, která to je, ale i zda je lehčí či těžší než správné koule).
        5. Minimalizujte počet cest nahoru a dolů elektřikáře, který má za úkol spárovat dolní a horní konce žil kabelu s n žílami (popište algoritmus elektřikáře a vyjádřete nutný počet cest jako funkci počtu žil). Řešte např. pro n=27, ale raději obecně.
    2. cvičení 13.října
      • Řešení úlohy s elektrikářem - domyslete
      • Opakování pojmů vyhraná, prohraná pozice, opakování řešení úlohy s dvěma kameny
      • Úlohy s tahy věží po šachovnici. Nedořešili jsme ze kterých políček jde začít neuzavřenou cestu na šachovnici s jedním chybějícím rohem
      • Dílčí řešení úlohy o nalezení případné nesprávné koule, je třeba dodělat !
      • Rozmyslet:
        1. Na políčcích pásky sudé délky jsou napsána nějaká kladná čísla. Dva hráči se střídají ve hře. Hráč na tahu si může vybrat, které z krajních políček pásky si ustřihne. Po skončení hry vyhrál ten z hráčů, kterému se podařilo ustříhat políčka s větším součtem.
          Nalezněte jednoduchou neprohrávající strategii pro hráče, který začíná.
        2. Mladík se uchází o princeznu. Získá ji, pokud uspěje v následující zkoušce.
          Mladíka postaví se zavázanýma očima před otáčecí čtvercový stůl, v jehož rozích stojí 4 sklenice. Každá sklenice může být v jedné ze dvou poloh - dnem vzhůru a dnem dolů. Mladík může v každém kole šáhnout na kterékoli dvě sklenice a podle své vůle případně změnit polohu některých z nich. Účelem je, aby všechny 4 sklenice byly ve stejné poloze. Pokud se to stane - princezna mu to oznámí, on v zkoušce obstál a mohou se chystat zásnuby. Pokud princezna neoznámí úspěch, hra pokračuje dalším kolem. Před tím však sluha stolkem otočí (mladík neví jak).
        3. Na stůl tvaru odélníka pokládají dva hráči střídavě mince (všechny jsou stejné). Mince musí ležet celá na stole, nesmí ležet na druhé. Prohraje ten, který už další minci nemůže položit. Je hra pro začínajícího hráče vyhraná nebo prohraná?
        4. Kulový blesk
          Jistých N rodin bydlí v bytech, které označíme celými čísly od 1 do N. Rodiny se dohodly provést cyklickou N-směnu bytů (viz též film Kulový blesk). Rodina z bytu číslo 1 chce do bytu číslo 2, rodina z bytu číslo 2 do bytu číslo 3, atd., až rodina z bytu číslo N se bude stěhovat do bytu číslo 1. Výsledné záměny bytů je třeba dosáhnout postupným prováděním dvojsměn. Některé rodiny se tudíž budou během celé akce stěhovat vícekrát. Každá rodina se ale může přestěhovat nejvýše jednou za den. V jednom dni může samozřejmě probíhat souběžně více dvojsměn bytů. Určete, jaký nejmenší počet dní postačí pro dané N k uskutečnění celé zamýšlené akce. Sestavte rozpis, podle něhož je třeba při výměnách bytů postupovat, aby se tohoto minimální počtu dní dosáhlo (tzn. rozpis určující, kdo se který den stěhuje kam).
        5. Velbloud má nosnost 1000 banánů a spotřebu 1 banán na 1 km. Na hromadě je 3000 banánů, najděte způsob, jak do co největší vzdálenosti přepravit 1000 banánů.
    3. cvičení 20.října
      • Verze eklektrikáře nefunguje pro vsechna data, návod na jiné řešení pro liché počty - doplňte řešení pro sudý počet.
      • Velbloud a banány. Pro konkrétní zadání vyřešeno, zkuste řešit obecně (jak daleko lze donést dané množství banánů a jaké množství banánů jde donést do zadané vzdálenost, oboje pro zadanou nosnost a spotřebu velblouda a velikost hromady na startu)
      • Návod pro úlohu s princeznou: Mladík má v každé kole na vybranou jen mezi dvěma možnostmi - sáhnout na stranu stolu nebo sáhnout na diagonálu
      • Páska sudé délky
      • Kulový blesk
      • Mrkev a petržel
      • Rozmyslet:
        1. vše, co jsme nedodělali
        2. jakákoli nová tvrzení o problému vážení
        3. Vězni, žalářníci a lampa
          Ve vězení je N vězňů odsouzených na doživotí a každý z nich má svou vlastní celu bez oken. Každý den je jeden z vězňů odveden do speciální místnosti, kde je vyslýchán. V této místnosti je na stropě žárovka a na zdi vypínač. Před prvním výslechem je žárovka zhasnutá. Během výslechu může vězeň žárovku pomocí vypínače libovolně rozsvěcet a zhasínat. Když další den přivedou do místnosti dalšího vězně na výslech, tak je žárovka v takovém stavu (rozsvícená nebo zhasnutá), v jakém ji nechal předchozí vězeň. Vězni jsou vyslýcháni v libovolném pořadí a každý z vězňů může být vyslechnut i vícekrát – pokud by výslechy probíhaly po nekonečně mnoho dní, tak by byl každý z vězňů vyslechnut nekonečně krát. Od určitého okamžiku tedy určitě nastane stav, že každý z vězňů byl vyslechnut alespoň jednou. Pokud pak kdykoliv potom kterýkoliv z vězňů během výslechu řekne: „nyní jsme byli všichni vyslechnuti alespoň jednou“, tak budou všichni vězni propuštěni. Pokud někdo tuto větu řekne dříve než je to pravda, tak budou všichni vězni popraveni. Před začátkem výslechů se vězni mohou půl hodiny společně procházet po vězeňském dvoře a domluvit si strategii, jak rozsvěcet a zhasínat žárovku a kdy má někdo pronést propouštěcí formuli. Vaším úkolem je pro vězně tuto strategii vymyslet. K výslechům mohou vězně vodit zcela libovolně, jediným pravidlem, které vyšetřovatelé musí dodržet je, že v libovolném okamžiku musí platit:
          " Každý vězeň bude ještě v budoucnu vyslechnut, pokud celý proces neskončí popravou či propuštěním vězňů"
        4. Synchronizace automatů:
          Navrhnout konečné automaty G(enerál), Z(adák) a V(oják) tak, aby libolně dlouhá posloupnost vojáků začínající generálem a končící zadákem dokázala vydat salvu za nějakou dobu po generálově rozkazu.
          Nejde o přesný popis automatů, ale o myšlenku jejich komunikace
    4. cvičení 27.října
      • Úloha s princeznou
      • Nová fakta o úloze s koulemi:
        1. Bez správné koule jde vyřešit s 12 koulemi na 3 vážení.
        2. Důkaz toho, že na k vážení můžeme úlohu (i s případně správnými koulemi) nejde vyřešit pro více než Nk = (3k-1)/2
        3. Pro Nk koulí nelze úlohu vyřešit na k vážení
      • Základy práce s prostředím Borland Pascalu,
        pohrajte si s ním (můžete si nainstalovat Free Pascal)
      • Zkuste si vyřešit úlohy, které jsou ve Vaší skupině v systému CodEx
        budou-li problémy, nevadí, jen si je zapamatujte, abyste se mohli zeptat
      • Písemný domácí úkol: Popište způsob, který najde prostřední z 5 číselna co nejmenší počet porovnání.
        Soustřeďte se nejen na minimalizaci, ale především na co nejjednodušší popis algoritmu
        Buď mi pošlete na mail se subjectem "PRM044-1" do pondělka nebo přineste písemně na cvičení
      • Rozmyslet: vše, co jsme nedodělali
    5. cvičení 2.listopadu
      • Úloha s vězni
      • Hra se čtyřmi kameny, hra se třemi kameny
      • Synchromizace automatů pomocí nalezení poloviny řady jako místa, kde se setkají signály vyslané rychlostmi 1 a 1/3
      • Obecná úloha o velbloudech - snažte se o formulaci
      • Komentář k úlohám v CodExu
      • Samostatná práce s překladačem
      • Domácí úkoly:
        1. staré a nové úlohy v CodExu
        2. rozmyslet úlohu o koulích - najít nová tvrzení (jejich mnoho, která jsme dodud neformulovali
        3. zopakovat si část jazyka, kterou jsme probrali
        4. pohrát si s kompilátorem
        5. formulovat dotazy
    6. cvičení 9.listopadu
      • komentář ke CodExu
      • práce s textovými soubory
        • je třeba
          1. deklarovat proměnnou (např. F) typu text
          2. zavolat proceduru assign(F, jméno souboru v OS)
          3. soubor otevřít buď ke čtení příkazem reset(F) nebo pro zápis příkazem rewrite(F)
          4. výstupní soubor je dobré před koncem programu uzavřít příkazem close(F)
        • všechny příkazy pro standarní vstup/výstup můžeme použít, jen jim musíme přidat první parametr F
      • jednoduché příklady práce s textovými soubory, kopírování souboru
      • vyčíslování částečných součtů mocninných řad
      • rozmyslet: hra NIM Na hromádce je na počátku N sirek. Hráči střídavě odebírají přípustný počet sirek. Hráč, který vezme poslední prohrál.
        Najděte, které počáteční konfigurace jsou vyhrané resp. prohrané pro hráče, který začíná:
          když hráč na tahu smí vzít K sirek
        1. 1<=K<=3
        2. K je jedno z čísel {1,2,4,5}
        3. K je jedno z čísel {1,3,5}
        4. K je libovolné liché číslo
      • Domácí úkol č.2.
        Napište funkci pro vyčíslení součtu prvních N členů zadané mocninné řady
        pošlete email se subjectem Dcv2 nebo přineste na cvičení
    7. cvičení 16.listopadu
      • dvě z úloh v CodExu potřebují znalosti práce s textovými soubory, které jsme dosud neprobírali, proto jsem jejich první termín k odevzdání posunul až za čtrnáct dní, příště si potřebné informace řekneme
      • typ record a příkaz with
      • typická reprezentace tabulky jako recordu se složkami pole a velikost jeho zaplněné části
      • podprogram pro hledání posledního výskytu čísla X v tabulce T
        • hledání while cuklem odzadu
        • totéž se zarážkou
      • podprogram pro nalezení prostředního výskytu čísla X v tabulce T,
        verze s pomocnou tabulkou indexů výskytů čísla X
      • řešení úlohy s 13 koulemi a jednou správnou na 3 vážení
      • hledání následující permutace v lexikografickém uspořádání
      • kolikátá je zadaná permutace v lexikografickém uspořádání
        • Rozmyslet:
      • Provázky
        Mám naolejovaný provázky. Když některý z nich na jednom konci zapálím, bude postupně odhořívat, až za 1 hodinu dohoří na druhý konec (a zhasne). Žádný provázek však není všude stejně široký, a proto ani nehoří stále stejně rychle. Nelze tedy tvrdit, že např. polovina provázku shoří za půl hodiny. Lze splnit následující úkoly ?
        1. mám jeden provázek a potřebuji změřit půl hodiny
        2. mám dva provázky a potřebuji změřit čtvrt hodiny
        Pozn: okamžik, od kdy začínám měření, si mohu zvolit sám
      • Cihly
        Máme k dispozici neomezenou zásobu cihel, všechny cihly jsou stejné. Na stůl budeme pokládat cihly na sebe jednu na druhou. Každá cihla musí ležet na cihle předchozí, může ji ovšem částečně přesahovat do strany. Není však povoleno umístit více cihel do stejné výšky nad deskou stolu. Zjistěte, jak nejdále od hrany stolu se se svou stavbou z cihel dokážete dostat.
      • Zkuste najít postup jak na k vážení vyřešit úlohu s koulemi pro Nk = (3k-1)/2 podezřelých koulí
        (můžete použít správné koule - již ksme dokázali, že be nich to nejde, kolik jich budete potřebovat?)
      • Hledání K-té permutace z prvků 1..N
      • Domácí úkol č.3.
        napiště proceduru pro nalezení prostředního výskytu čísla X v tabulce T založenou na střídavém hledání odpředu a odzadu
        Pošle maile se subjctem Dcv3 nebo přineste na cvičení