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ěžší)
Najděte pro tabulku čokolády o K řádcích a L sloupcích způsob, který ji na co nejmenší počet lámání nakouskuje na K*L kousků o jednom dílku.
Nalézt cestu věže, která
projde přes každé políčko šachovnice právě jednou
projde přes každé políčko šachovnice právě jednou a navíc končí na políčku sousedním se startovním políčkem
obě úlohy pro následující šachovnice
obyčejná šachovnice 8x8
šachovnice 8x8 v níž chybí jedno rohové pole
šachovnice 8x8 v níž chybí dvě rohová pole ležící na jedné diagonále
Hráči pokládají střídavě stejné mince na obdélníkový stůl. Ten, který už nemůže minci položit, prohrál.
Najděte vyhrávající strategii pro hráče, který začíná
Písemný úkol:(přineste na cvičení)
Najděte prostřední z pěti čísel.
Snažte se:
o co nejjednodušší zápis algoritmu
o co nejmenší počet porovnání
Rozmyslet:
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á.
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).
cvičení 12.října
Ti, kdo nepřinesli úkol, mi ho pošlou e-mailem.
Text úkolu pošlete jako přílohu mailu s předmětem "PRMDCV1" podepište se i v tomto souboru
Řešení úlohy s princeznou a skleničkamim
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.
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).
Udělali jsme:
Ze tří koulí na jedno vážení
Z 9 koulí na dvě vážení
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
Umíme na jedno vážení ze čtyř pokud máme k dispozici jednu správnou kouli
Uvažujte dvě varianty zadání: buď máme na počátku jen podezřelé koule nebo máme na počátku i nějaké správné koule
Rozmyslet: ¨
Č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.
Obdobně tři kameny
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ňů"
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ě.
Uvažujme dvě varianty úlohy s koulemi: buď máme k dipozici správné koule nebo ne.
Jaký je vztah těchto dvou úloh? Zkuste najít jakýkoli nový poznatek.
Zkuste najít algoritmus pro obecný počet koulí.
cvičení 19.října
suplováno
cvičení 26.října
Úloha s vězni
třetí z pěti
práce s prostředím Borland Pascalu a Codexem
vytváření jednoduchých programů viz Codex
Na příště:
rozmyslete si otázky k prostředí a Codexu
vyřešte úlohy zadané v Codexu
Rozmyslet:
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ů.
Zkuste úlohu řešit obecně.
zůstávají tři a čyři kameny, elektrikář, koule
cvičení 2.listopadu
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)
Čtyři kameny - jak je to pro tři?
Elektrikář
Rozmyslet:
zůstávají koule
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).
Spočítejte počet osevních plánů N záhonů, pro něž platí:
na každém záhonu je buď mrkev nebo petržel
Na žádných dvou sousedních záhonech nesní být petržel
Snažte se o efektivní výpočet.
Komentář k úlohám v CodExu
Vyřešte další úlohy v Codexu - pokud možno, odevzdejte řešení do středy večer, abych si mohl připravit komentář k nim
Pokud za ostatními v řešení úloh z Codexu zaostáváte, snažte se najít příčinu. Asi to bude chtít víc úsilí a možná i nějakou konzultaci. Nenechte si to utéct, je to zbytečné.
cvičení 9.listopadu
Mrkev a petržel -rozmyslete si způsob, kterým jsme úlohu vyřešili.
Kulový blesk
Všichni si rozmyslete problematiku předávaní parametrů, abychom se k tomu mohli vrátit
Rozmyslet:
Všichni se zamyslí nad úlohou s koulemi a pokusí se zformulovat a dokázat nějaké nové tvrzení.
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
Hra Nim -najděte vyhrané a prohrané pozice. Hráči střídavě odebírají sirky, v každém tahu hráč na tahu odebere z jedné hromádky
K sirek. Ten, kdo vezme poslední, prohrál.
zkusí všichni:
Jedna hromádka, K je jedno z čísel {1,2,3}
Jedna hromádka, K je jedno z čísel {1,3,4}
Jedna hromádka, K je jedno z čísel {1,3,5}
Jedna hromádka, K je jedno z čísel {1,2,..,N}
další případy jsou obtížnější
Dvě hromádky, v jednom tahu je možno vzít 1..3 sirek, zobecnění pro N
Více hromádek, v jednom tahu je možno vzít 1..N sirek
Na stůl stavíme věž ze stejných cihel, v každém patře věže je jedna cihla. Jak daleko od hrany stolu se můžeme dostat.
Rozbor úloh v Codexu
krátká písemka
cvičení 16.listopadu
obecné řešení úlohy s velbloudem
úloha s koulemi:
na k vážení s jednou správnou koulí jde pro Nk = (3k-1)/2 koulí
bez správné kole jde pro Nk-1 koulí
zbývá dokázat, že pro Nk koulí na k vážení je jedna správná koule nutná
opakování předávání parametrů
Lexikografické uspořádání
Algoritmus hledání následující permutace v lexikografickém uspořádání
analýza hledání pořadového čísla permutace v lexikografickém uspořádání
Komentář k úlohám v CodExu
zůstává NIM a synchronizace automatů
cvičení 23.listopadu
Komentář k úlohám v CodExu
Práce s textovými soubory
zůstává NIM
Upozornění na soutěž studentů v prvního ročníku v programování - pátek 30.11.2012, 15-18 hod.,
doporučuji Vám, abyste se soutěže zúčastnili. Pokud by Vám v tom bránilo to, že cvičení končí až v 13:50, můžete odejít dřív resp. se omluvit z celého
cvičení 30.listopadu
hledání vyhraných a prohraných pozic ve hře NIM
synchronizace automatů
stručné shrnutí aspektů práce se soubory, které mohou být "nebezpečné"
řešení úloh v Codexu snímá z programátora nutnost volit vstupní a výstupní data
zásady jak navrhovat vstupní a výstupní data programů tak, aby
byly užitečné a
maximálně podporovaly ladění programů,
konkrétní příklady
úloha fronta před kinem
Rozmyslete si důkladně řešení úlohy o nezávislosti dam, která byla na předášce i ostatní algorimy, které budu na příští přednášce
cvičení 7.prosince
první nabídka témat na zápočtové úlohy
prohledávání do hloubky a došířky
rekurze
úloha o frontě před kinem
algoritmus vlny
komentář k úlohám v Codexu
cvičení 14.prosince
rozpoznávání správně uzávorkovaných výrazů s jedním či více typy závorek - různé algoritmy
rozbor nových úloh v Codexu
heuristika minimálního stupně volnosti při obeskákání šachovnice koněm
opakování algoritmu faktorové množiny
úvod k počítání s ůdlouhými" čísly
krátká písemka
cvičení 21.prosince ze zdravotních důvodů odpadlo
cvičení 4.ledna
témata na zápočtové úlohy každý by měl nejpozději do 15. ledna být domluven na tématu zápočtové úlohy (je lepší osobně) a nejpozději do
20. ledna mailem odevzdat specifikaci
k zápočtu je třeba mít minimálně 350 bodů v Codexu - většina má, pokud byste měli závažné důvody proč to nemůžete splnit je třeba si co nejdříve
domluvit náhradní plnění
zápočtový program je potřeba odevzdat do konce února (nejp. do 10. března) ve stavu, kdy jste s ním již sami spokojeni, a s dokončenou dokumentací.
Pochopitelně možné v průběhu práce konzultovat. Pokud budete potřeba, dám vám cca 14 dní na provedení potřebných úprav.
písemka dopodla velmi zle - viz Codex (max. 50 bodů, za účast 3 body)