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ěžší)
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
udělali jsme
obyčejná šachovnice 8x8
šachovnice 8x8 v níž chybí jedno rohové pole
zbývá k rozmyšlení
šachovnice 8x8 v níž chybí dvě rohová pole ležící na jedné diagonále
Rozmyslet:
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ňů"
Nalezněte na co nejmenší počet porovnání třetího z pěti.
Minimalizujte počet cest nahoru a dolů elektrikář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ě. Elektrikář má k dispozici baterii (zdroj proudu) a žárovku, může spojovat, rozpojovat a popisovat konce žil
cvičení 8.října
Cesty na šachovnici, na které chybí dva protilehlé rohy
Úloha s vězni
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.
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.
"obecná" definice vyhraných a prohraných pozic - rozmyslete důkladně!
(Griesova) úloha o tahání koulí z urny - pojem invariantu
Rozmyslet: ¨
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á
Č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
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).
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ě.
Písemný úkol:(přineste na cvičení, pokud jste již odevzdali nemusíte znovu, ale můžete, máte-li lepší řeš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í
cvičení 15.října
Zřiďte si účet v Karlínských laboratořích a zaregistrujte se do Codexu - příště to již budeme potřebovat!!
mince na stole
stříhání z pásky sudé délky
úloha o princezně
velbloud
úloha pro tři kameny je speciálním případem úlohy pro čtyři kameny
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).
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
Udělali jsme několik speciálních případů, zkuste zjistit co nejvíce faktů o tomto problému - buď další speciální případy nebo obecný algoritmus, případně i s důkazem, že lépe to nejde
Na rozmyšlení:
Velbloud obecně
čtyři kameny
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
cvičení 22.října
čtyři kameny
upřesnění úlohy o synchronizaci automatů
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).
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
Udělali jsme:
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
snažte se najít jakékoli nové tvrzení o tomto problému - případně obecný algoritmus
Nim - v jednom tahu je možno vzít 1-3 sirky, prohraje ten, kdo vezme poslední zápalku
Rozmyslet:
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.
Vyřešte hru NIM pokud hráč na tahu může vzít
2,3 nebo 5 sirek vyhraje ten, kdo už nemůže táhnout
liše sirek
cvičení 29.října
Čtyři kameny
kulový blesk
prostřední z 5 na 6 - zápis pomocí stavů
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
řešte problémy, které jsme dosud nevyřešili
cvičení 5.listopadu
synchronizace automatů
Rozbor úloh v Codexu
Ladění v Borland Pascalu - watches, breakpointy
Rozmyslet:
zůstávají všechny nevyřešené úlohy
Všichni se zamyslí nad úlohou s koulemi a pokusí se zformulovat a dokázat nějaké nové tvrzení.
Vyřešte další úlohy v Codexu - pokud možno, odevzdejte řešení do pondělí večer, abych si mohl připravit komentář k nim
Písemný domácí úkol:
Obecné řešení úlohy s velbloudy - pošlete soubor s řešením, který se bude jmenovat "Vaseprijmeni" nejpozději do půlnoci jako přílohu mailu se subjectem "Velbloud".
I v samotném spouboru by mělo být vaše jméno.
cvičení 12.listopadu
výsledky v Codexu - pochvala většině
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é.
NIM pokud hráč na tahu může vzít
2,3 nebo 5 sirek vyhraje ten, kdo už nemůže táhnout
krátká písemka - úloha s koulemi, kdy máme k dispozici 3 vážení
Lexikografické uspořádání
analýza hledání pořadového čísla permutace v lexikografickém uspořádání
Rozmyslete inverzní úlohu - nalezení permutace, která má zadané pořadové číslo
Algoritmus hledání následující permutace v lexikografickém uspořádání
Komentář k úlohám v CodExu
Dvě reprezentace permutací:
vektor obrazů skuste naprogramovat skládání permuací v této reprezenaci
seznam (netriviálních) cyklů, rozmyslete algoritmy
převodů mezi těmito dvěma reprezentacemi
umocňování v reprezentaci pomocí cyklů
cvičení 19.listopadu
Komentář k úlohám v CodExu
opakování předávání parametrů
hledání pořadového čísla permutace v lexikografickém uspořádání
reprezentace permutace jako záznamu obsahující délku permutace a pole obrazů prvků
Deklarace tabulky, vytváření podprogramů pro rostoucí tabulky:
slévání
průnik
rozdíl
Deklarujte vhodný zúsobem typ pro reprezentaci funkce zadané jako posloupnost dvojic (vzor, obraz), uspořádaná podle hodnot vzorů
a rozmyslete si realizaci podporamů realizujících vzor a obraz množiny (zadaných jako rostoucí posloupnost prvků)
pomocí zadané funkce - tak, abyste tyto podprogramy mohli příště předvést
cvičení 3.prosince
první nabídka témat na zápočtové úlohy
Nejpozději do konce výuky před Vánoci je nutné dohodnout se na tématu zápočtové úlohy.
termín prodloužen do 7.1.2013
Nejpozději do 10. ledna je potřeba napsat a mailem poslat specifikaci.
Zápočtovou úlohu spolu s dokumentací je potřeba odevzdat do konce února
Na zápočet bude potřeba 360 bodů v Codexu
Komentář k úloze o slévání souborů - je nesmyslné používat pole!!!. U praktického testu by takový postup nemohl být uznán.
Komentář k úlohám v Codexu, domácím cvičení a hodnocení písemky
jednoduchá rekursivní procedura pro generování všech kombinací s opakováním